Prime Numbers

Once upon a time I wrote some functions for finding and checking prime numbers. In this library of functions you'll find the following:

• getPrimes() - finds prime numbers up to a specified limit
• isPrime() - checks if a number is prime using modular division against odd numbers
• isPrime2() - checks if a number is prime using modular division against known primes
• primeCount() - counts the number of primes less than or equal to the specified number
• isComposite() - the opposite of prime
• isPrimeSpeedTest() - races isPrime againts isPrime2

In theory, checking against known primes should be faster than checking against all odd numbers, but it turned out to be slower because I was first finding the primes with getPrimes(). If a list of prime numbers was hardcoded in an array it might be faster for smaller numbers, and then the odd number method could be used for larger numbers.

View ASP implementation on Snipplr

Triangular Numbers

A triangular number is the sum of the n natural numbers from 1 to n.

ASP

1. function triangularNumber(someNumber)
2.     dim i
3.     dim result
5.     result = 0
7.     for i = 1 to someNumber
8.         result = result + i
9.     next
11.     triangularNumber = result
12. end function

PHP

1. function triangularNumber($number)
2. {
3.     for($i = 1; $i <= $number; $i++)
4.     {
5.         $result += $i;
6.     }
8.     return $result;
9. }

• View ASP implementation on Snipplr
• View PHP implementation on Snipplr

Perfect Numbers

This week's function is for checking if an integer is a perfect number.

ASP

1. function isPerfect(someNumber)
2.     dim i
3.     dim arrFactors
4.     arrFactors = Array()
6.     ' Only positive integers can be perfect.
7.     if someNumber < 1 then
8.         isPerfect = false
9.         exit function
10.     end if
12.     ' Calculate the factors for the given number.
13.     for i = 1 to someNumber
14.         if someNumber mod i = 0 then
15.             redim preserve arrFactors(UBound(arrFactors) + 1)
16.             arrFactors(UBound(arrFactors)) = i
17.         end if
18.     next
20.     ' A perfect number is a number that is half the sum of all of its positive divisors (including itself).
21.     if someNumber = eval(join(arrFactors, " + ")) / 2 then
22.         isPerfect = true
23.     else
24.         isPerfect = false
25.     end if
26. end function

PHP

1. function isPerfect($number)
2. {
3.     // Only positive integers can be perfect.
4.     if ($number < 1)
5.     {
6.         return false;
7.     }
9.     // Calculate the factors for the given number.
10.     for($i = 1; $i <= $number; $i++)
11.     {
12.         if ($number % $i == 0)
13.         {
14.             $arrFactors[] = $i;
15.         }
16.     }
18.     // A perfect number is a number that is half the sum of all of its positive divisors (including itself).
19.     return ($number == array_sum($arrFactors) / 2) ? true : false;
20. }

• View ASP implementation on Snipplr
• View PHP implementation on Snipplr

Summation

This week's function is summation using the Gauss method.

ASP

1. function sum(x, y)
2.     sum = (x + y) * ((y - x + 1) / 2)
3. end function

PHP

1. function sum($x, $y)
2. {
3.     return ($x + $y) * (($y - $x + 1) / 2);
4. }

• View ASP implementation on Snipplr
• View PHP implementation on Snipplr

Mersenne Numbers

Today we're going to write a function to generate Mersenne numbers. This is useful in searching for Mersenne primes.

ASP

1. function mersenne(x)
2.     mersenne = 2^x - 1
3. end function

PHP

1. function mersenne($x)
2. {
3.     return 2^$x - 1;
4. }

• View ASP implementation on Snipplr
• View PHP implementation on Snipplr

Sinc function

Today we're going to a Sinc function, both normalized and unnormalized. Apparently it's useful in digital signal processing.

ASP

1. Const M_PI = 3.14159265358979323846
3. ' Unnormalized sinc function.
4. function sinc(x)
5.     sinc = sin(x) / x
6. end function
8. ' Normalized sinc function.
9. ' REQUIRES: constant M_PI
10. function nsinc(x)
11.     sinc = sin(M_PI * x) / (M_PI * x)
12. end function

PHP

1. // Unnormalized sinc function.
2. function sinc($x)
3. {
4.     return sin($x) / $x;
5. }
7. // Normalized sinc function.
8. function nsinc($x)
9. {
10.     return sin(M_PI * $x) / (M_PI * $x);
11. }

• View ASP implementation on Snipplr
• View PHP implementation on Snipplr

Golden function

The golden function is the upper branch of the hyperbola.

ASP

1. function gold(x)
2.     gold = (x + sqr(x^2 + 4)) / 2
3. end function

PHP

1. function gold($x)
2. {
3.     return ($x + sqrt($x^2 + 4)) / 2;
4. }

Sorry if this is not exciting stuff. I've got some better stuff coming, but I want to clear out some older stuff that has been waiting a while.

• View ASP implementation on Snipplr
• View ASP implementation on Snipplr

Nth Root

Both ASP and PHP have a function that allows you to calculate the square root of a number. What if we wanted the cubic root of a number, or some deeper root? Calculating the root of a number is the same as raising that number to a fractional exponent.

ASP

1. function root(x, y)
2.     root = x ^ (1 / y)
3. end function

PHP

1. function root($x, $y)
2. {
3.     return pow($x, 1/$y);
4. }

x

the number you want the root of

y

the depth you want to go (2 = square, 3 = cubic, etc.)

• View ASP implementation on Snipplr
• View PHP implementation on Snipplr

Logarithms

ASP's log() function returns the natural logarithm of a number. But what if we want a different base? The same problem exists with handheld calculators, and the same trick we use to get around it there can be used here too.

ASP

1. function logx(number, base)
2.     logx = log(number) / log(base)
3. end function

View ASP implementation on Snipplr

Fibonacci numbers

The Fibonacci numbers have many applications in computer programming. Today we're going to write a function that returns individual numbers from the Fibonacci sequence.

ASP

1. function fib(x)
2.     dim fibArray()
3.     redim fibArray(x)
5.     fibArray(0) = 0
6.     fibArray(1) = 1
8.     for i = 2 to x
9.         fibArray(i) = fibArray(i - 1) + fibArray(i - 2)
10.     next
12.     fib = fibArray(x)
13. end function

PHP

1. function fib($x)
2. {
3.     $fibArray[0] = 0;
4.     $fibArray[1] = 1;
6.     for($i = 2; $i <= $x; $i++)
7.     {
8.         $fibArray[$i] = $fibArray[$i - 1] + $fibArray[$i - 2];
9.     }
11.     return $fibArray[$x];
12. }

So, for example, fib(8) will return 21, because the Fibonacci sequence is 1, 1, 2, 3, 5, 8, 13, 21, 34, 55...

• View ASP implementation on Snipplr
• View PHP implementation on Snipplr

Fermat numbers

Today we're going to write a function to generate Fermat numbers. This could be useful if you want to write your own pseudo-random number generator.

ASP

1. function fermat(x)
2.     fermat = 2^2^x + 1
3. end function

PHP

1. function fermat($x)
2. {
3.     return 2^2^$x + 1;
4. }

• View ASP implementation on Snipplr
• View PHP implementation on Snipplr

Factorial

This week we're going to delve into some discrete math, starting with factorial. The factorial of a number is the product of that number and all the numbers smaller than it. For example, the factorial of 3 is 1 x 2 x 3 = 6.

ASP

1. function factorial(x)
2.     dim result
4.     result = 1
6.     if x > 1 then
7.         for i = 2 to x
8.             result = result * i
9.         next
10.     end if
12.     factorial = result
13. end function

PHP

1. function factorial($x)
2. {
3.     $result = 1;
5.     if ($x > 1)
6.     {
7.         for ($i = 2; $i <= $x; $i++)
8.         {
9.             $result *= $i;
10.         }
11.     }
13.     return $result;
14. }

Now that we have a function for factorial, we can also do combinatorial. Combinatorial tells us the number of combinations, without regard to order, of y items that can be made from a pool of x items.

ASP

1. function combinatorial(x, y)
2.     if (x >= y) and (y > 0) then
3.         combinatorial = factorial(x) / factorial(y) / factorial(x - y)
4.     else
5.         combinatorial = 0
6.     end if
7. end function

PHP

1. function combinatorial($x, $y)
2. {
3.     return (($x >= $y) && ($y > 0)) ? factorial($x) / factorial($y) / factorial($x - $y) : 0;
4. }

We can also get the number of permutations of y items that can be made from a pool of x items.

ASP

1. function permutations(x, y)
2.     permutations = factorial(x) / factorial(x - y)
3. end function

PHP

1. function permutations($x, $y)
2. {
3.     return factorial($x) / factorial($x - $y);
4. }

• ASP implementation on Snipplr
• PHP implementation on Snipplr

Pythagorean Theorem

When you're dealing with right-angled triangles, trigonometry is not required to calculate the length of the hypotenuse. Our PHP programmers friends have a function called hypot() which solves for c in the equation: a^2 + b^2 = c^2

1. function hypot(a, b)
2.     hypot = sqr(a^2 + b^2)
3. end function

Using the classic 3-4-5 triangle as an example, for a = 3 and b = 4, the function will return 5.

View this code on Snipplr

Degrees and Radians

When you were learning trigonometry, you probably measured angles in degrees. But in calculus, angles are measured in radians (search for "degrees vs. radians" on Google for the reasons). Being able to convert between these two units might be handy. PHP provides two functions for this purpose, but no such luck in ASP. As usual, we're going to write our own.

Radians is heavily based on my favorite number, pi. We're going to need this number in our calculations, so make sure to define a constant for it.

Const M_PI = 3.14159265358979323846

And now the functions themselves...

1. function deg2rad(x)
2.     deg2rad = x * M_PI / 180
3. end function
5. function rad2deg(x)
6.     rad2deg = x * 180 / M_PI
7. end function

View this code on Snipplr

Euclid's Algorithm

Euclid's algorithm is one of the oldest, known by ancient Greeks like Aristotle. You might remember it from elementary school when you had to find things like greatest common factor/divisor and least common multiple. Greatest common factor/divisor allowed you to reduce fractions like 4/12 to 1/3. Least common multiple allowed you to add and subtract fractions that had different denominators.

There is more than one way to implement this algorithm. The original involved iterative subtraction. This was later improved upon with iterative modulo division. Another method, the one I'll be using here, is recursion.

ASP

1. function gcd(byVal a, byVal b)
2.     a = abs(a)
3.     b = abs(b)
5.     if a = 0 then
6.         gcd = b
7.     elseif b = 0 then
8.         gcd = a
9.     elseif a > b then
10.         gcd = gcd(b, a mod b)
11.     else
12.         gcd = gcd(a, b mod a)
13.     end if
14. end function
16. function lcm(byVal a, byVal b)
17.     a = abs(a)
18.     b = abs(b)
20.     if a > b then
21.         lcm = (b / gcd(a, b)) * a
22.     else
23.         lcm = (a / gcd(a, b)) * b
24.     end if
25. end function

PHP

1. function gcd($a, $b)
2. {
3.     $a = abs($a);
4.     $b = abs($b);
6.     if ($a == 0)
7.     {
8.         return $b;
9.     }
10.     elseif ($b == 0)
11.     {
12.         return $a;
13.     }
14.     elseif ($a > $b)
15.     {
16.         return gcd($b, $a % $b);
17.     }
18.     else
19.     {
20.         return gcd($a, $b % $a);
21.     }
22. }
24. function lcm($a, $b)
25. {
26.     $a = abs($a);
27.     $b = abs($b);
29.     if ($a > $b)
30.     {
31.         return ($b / gcd($a, $b)) * $a;
32.     }
33.     else
34.     {
35.         return ($a / gcd($a, $b)) * $b;
36.     }
37. }

Euclid's algorithm is not always the fastest, but it is the simplest. A better algorithm was devised by 20th century mathematician Dick Lehmer. Another 20th century mathematician, Josef Stein, devised a specialized algorithm for computers which uses bit shifting. Note, however, that the performance improvement of these more modern algorithms varies depending on the CPU and size of the numbers involved. In some cases, Euclid is actually faster.

• ASP implementation on Snipplr
• PHP implementation on Snipplr

Ceiling and Floor

In mathematics, there are two elementary special functions called ceiling() and floor() which allow us to round up or down, respectively, to the nearest whole number. These functions exist natively in PHP, but not in ASP. They are handy in situations where you want to force a number like 15.8 to round down to 15, but the round() function rounds it up to 16 according to the standard rules for rounding.

ASP

1. function floor(x)
2.     dim temp
4.     temp = round(x)
6.     if temp > x then
7.         temp = temp - 1
8.     end if
10.     floor = temp
11. end function
13. function ceil(x)
14.     dim temp
16.     temp = round(x)
18.     if temp < x then
19.         temp = temp + 1
20.     end if
22.     ceil = temp
23. end function

Base Conversion

Most of the modern world uses a base-10 number system. It's the easiest to work with. However, when it comes to computer systems, we use a few different number systems too. Base-2, or binary, is the basis of data storage and transmission; a bit is either on or off. We also use Base-8, or octal; each byte contains 8 bits. Last but not least is Base-16, or hexadecimal.

Under some circumstances, we might need to convert between these different number systems. ASP provides a pathetic two functions for this purpose: hex(), which converts from base-10 (decimal) to base-16 (hexadecimal), and oct() which converts from decimal to octal. PHP provides equivalent functions dechex() and decoct(), as well as additional functions decbin() for converting from decimal to binary, bindec() for converting from binary to decimal, hexdec() for converting from hexadecimal to decimal, and octdec() for converting from octal to decimal.

It would be nice to extend ASP to support these four additional functions. When I started doing that, I noticed a pattern in the formulae. All the functions that converted from decimal were fairly similar, and all the functions that converted to decimal were also fairly similar. So I abstracted the calculations out into their own functions and simplified my code.

ASP

1. ' Convert from binary to decimal.
2. function bindec(bin)
3.     bindec = toDecimal(bin, 2)
4. end function
6. ' Convert from decimal to binary
7. function decbin(dec)
8.     decbin = fromDecimal(dec, 2)
9. end function
11. ' Convert from decimal to hexadecimal.
12. function dechex(dec)
13.     ' Assume that built-in hex() function is faster.
14.     dechex = hex(dec)
15. end function
17. ' Convert from decimal to octal.
18. function decoct(dec)
19.     ' Assume that built-in oct() function is faster.
20.     decoct = oct(dec)
21. end function
23. ' Convert from hexadecimal to decimal.
24. function hexdec(hex)
25.     hexdec = toDecimal(hex, 16)
26. end function
28. ' Convert from octal to decimal.
29. function octdec(oct)
30.     octdec = toDecimal(oct, 8)
31. end function

Before we get into the underlying fromDecimal() and toDecimal() functions, some things need to be said. The lowest possible base is 2, so if the user tries to specify a base smaller than 2, we will change it to 2. Likewise, there is a practical upper limit of base 36. Beyond that, things get more complicated, so any base higher than 36 will be changed to 36 to prevent the function from going out of bounds and returning bad data.

ASP

1. function toDecimal(value, radix)
2.     dim result
3.     dim digit
5.     result = 0
7.     ' Prevent radix from going out of bounds.
8.     if radix < 2 then
9.         radix = 2
10.     elseif radix > 36 then
11.         radix = 36
12.     end if
14.     for i = 1 to Len(value)
15.         digit = Mid(value, i, 1)
17.         ' Convert letters to numbers.
18.         if not isNumeric(digit) then
19.             ' The letter A in any base is equal to 10 in decimal.
20.             ' The ASCII value of A is 65, so subtract 55 from the ASCII value to obtain the decimal value.
21.             digit = Asc(UCase(digit)) - 55
22.         else
23.             digit = CInt(digit)
24.         end if
26.         ' Return zero if any digit is out of bounds for the radix.
27.         if digit >= radix then
28.             result = 0
29.             exit for
30.         end if
32.         result = result + (digit * radix ^ (Len(value) - i))
33.     next
35.     toDecimal = result
36. end function
38. function fromDecimal(value, radix)
39.     dim result
40.     dim digit
42.     result = 0
44.     ' Prevent radix from going out of bounds.
45.     if radix < 2 then
46.         radix = 2
47.     elseif radix > 36 then
48.         radix = 36
49.     end if
51.     ' Check for invalid input.
52.     if isNumeric(value) then
53.         ' Inputted value appears to be base 10. OK to proceed.
54.         do until value = 0
55.             digit = value Mod radix
57.             if digit > 9 then
58.                 digit = Chr(digit + 55)
59.             end if
61.             result = CStr(digit) & result
62.             value = value \ radix
63.         loop
64.     else
65.         ' Inputted value was NOT base 10.
66.         result = 0
67.     end if
69.     fromDecimal = result
70. end function

It would be even better if we could easily convert between two bases where neither one is decimal. Also, it would be nice to have a unified interface. We can achieve both with one function, base_convert(), which is also present in PHP.

ASP

1. function base_convert(value, sourceRadix, targetRadix)
2.     if sourceRadix = targetRadix then
3.         ' If source radix and target radix are equal, don't waste time converting.
4.         baseConv = value
5.     elseif sourceRadix = 10 then
6.         ' If source radix is decimal, skip converting to decimal.
7.         baseConv = fromDecimal(value, targetRadix)
8.     elseif targetRadix = 10 then
9.         ' If target radix is decimal, skip converting from decimal.
10.         baseConv = toDecimal(value, sourceRadix)
11.     else
12.         ' Convert to decimal, and then from decimal.
13.         baseConv = fromDecimal(toDecimal(value, sourceRadix), targetRadix)
14.     end if
15. end function

I leave you with the following potential exercises:

• From base 37 to 62, the lowercase letters of the Latin alphabet are used, but special handling would need to be added for them. The ASCII value for Z is 90. The ASCII value for a is 97. There are six other characters in between.
• Base64 encoding begins with the uppercase letters A-Z, followed by a-z, followed by 0-9, followed by + and /. If you want to add Base64 support, separate functions would be wise, but could still be tied into the base_convert() wrapper.

Trigonometry, Part 3

I was hoping to publish every Saturday, but this past Saturday I got sidetracked. So without further ado, I bring you the next installment in the trigonometry series of articles.

Each of the six basic trigonometric functions has an inverse function. The inverse functions for sine, cosine, and tangent (arcsine, arcosine, and arctangent, respectively) are already defined natively in PHP. In ASP, only the inverse function for tangent (arctangent) is defined, but we will create an adapter for it to be consistent with the abbreviation in PHP. We also need to define some constants that are already present in PHP but not in ASP.

ASP

1. Const M_PI = 3.14159265358979323846
2. Const M_PI_2 = M_PI / 2
4. function asin(x)
5.     asin = atn(x / sqr(1 - x ^ 2))
6. end function
8. function acos(x)
9.     acos = M_PI_2 - asin(x)
10. end function
12. function atan(x)
13.     atan = atn(x)
14. end function

As you can probably guess, the inverse functions for cosecant, secant, and cotangent are arccosecant, arcsecant, and arccotangent.

ASP

1. function acsc(x)
2.     acsc = asin(1 / x)
3. end function
5. function asec(x)
6.     asec = M_PI_2 - acsc(x)
7. end function
9. function acot(x)
10.     acot = M_PI_2 - atn(x)
11. end function

PHP

1. function acsc($x)
2. {
3.     return asin(1 / $x);
4. }
6. function asec($x)
7. {
8.     return (M_PI_2 - acsc($x));
9. }
11. function acot($x)
12. {
13.     return (M_PI_2 - atan($x));
14. }

Next time we'll do something different for a change. I promise.

Trigonometry, Part 2

As promised, this week we're building some special trigonometry functions using the functions we wrote last week: versed sine (or versine), coversed sine (or coversine), haversed sine (or haversine), hacoversed sine (or hacoversine), exsecant, and excosecant. Actually, to be honest, only two of those build on the functions from last week.

ASP

1. function versin(x)
2.     versin = 1 - cos(x)
3. end function
5. function coversin(x)
6.     coversin = 1 - sin(x)
7. end function
9. function haversin(x)
10.     haversin = versin(x) / 2
11. end function
13. function hacoversin(x)
14.     hacoversin = coversin(x) / 2
15. end function
17. function exsec(x)
18.     exsec = sec(x) - 1
19. end function
21. function excsc(x)
22.     excsc = csc(x) - 1
23. end function

PHP

1. function versin($x)
2. {
3.     return (1 - cos($x));
4. }
6. function coversin($x)
7. {
8.     return (1 - sin($x));
9. }
11. function haversin($x)
12. {
13.     return (versin($x) / 2);
14. }
16. function hacoversin($x)
17. {
18.     return (coversin($x) / 2);
19. }
21. function exsec($x)
22. {
23.     return (sec($x) - 1);
24. }
26. function excsc($x)
27. {
28.     return (csc($x) - 1);
29. }

Next week, the fun continues with inverse trigonometric functions.

Trigonometry, Part 1

Both ASP and PHP contain three basic trigonometry functions: sin(), cos(), and tan(). You may remember from school that there are three more basic trigonometry functions: cosecant, secant, and cotangent. It might be handy to have some functions for these too.

ASP

1. function csc(x)
2.     csc = 1 / sin(x)
3. end function
5. function sec(x)
6.     sec = 1 / cos(x)
7. end function
9. function cot(x)
10.     cot = 1 / tan(x)
11. end function

PHP

1. function csc($x)
2. {
3.     return (1 / sin($x));
4. }
6. function sec($x)
7. {
8.     return (1 / cos($x));
9. }
11. function cot($x)
12. {
13.     return (1 / tan($x));
14. }

Next week we'll build off some of these basic functions to make some special functions.