GFA BASIC 32‎ > ‎How To‎ > ‎

05 Calculating Prime Numbers

posted Aug 20, 2015, 4:50 PM by Troy Cheek   [ updated Aug 20, 2015, 4:51 PM ]
http://www.wbur.org/npr/102871918
Can you calculate prime numbers using GFA BASIC 32?  Of course you can, but only very small ones.

A prime number is an integer whose only two factors are one (1) and itself.  In other words, you can only evenly divide it (no remainder) by 1 and itself.  Zero (0) isn't prime because you can't divide it by itself (0/0 makes the universe implode).  One (1) isn't prime because you need two factors and we're already using one as part of the definition.  Trying to make one prime is like trying to take yourself as your own date to the prom.  Again, the universe implodes.  So, the first prime is two (2) followed by three (3) and it gets complicated from there.

Most of the time when I work with integer numbers in GB32, I use the Int, Int32, Integer32, Long Data Type.  All those are different ways of saying the same thing:  a 32 bit signed integral value.  32 bits means that it can hold up to 2^32 different values.  Since we need to reserve one bit to tell us the sign (positive or negative), that leaves us 2^31 different values.  Since we have to leave room for zero, the largest number we can store is 2^31-1 or 2147483647.  That's about 2 billion.  I tend to use Int32 because it was the default data type in earlier versions of GFA BASIC, GB32 math runs faster with integers, and 32 bit integers are fastest of all because GB32 is, as the name implies, a 32 bit application.

I hardly ever use Int16, Integer16, Word, Short Data Type.  I can only hold numbers up to 2^15-1 or 32767.  The Card data type is unsigned so it can store 2^16-1 or 65535, but you can't use it to store negative numbers.  Card is the largest unsigned integer data type

For larger numbers, you can use the Int64, Integer64, Large Data Type.  The largest number this data type can store is 2^63-1 or 9223372036854775807.  That's about 9 quintillion (US short scale) or 19 digits long.  This seems like a pretty big number.  In fact, names used to describe the largest number held by an Int32 or Int64 carry monikers such as MAXINT, MAX_VALUE, math.huge, and (my favorite) Big McLargeHuge.  GB32, by the way, uses _maxInt and _maxLarge.

You might consider using single or double precision floating point data types.  A double uses 64 bits to store values upwards of 10^300, which makes Int64 with 10^18 seem puny.  However, while single and double can store very large numbers, they can't store very precise numbers.  They only keep track of the 8 or 16 (approximately) most significant digits.  They can store numbers in the bazillions (imaginary large number), but they don't store the exact number down to the 10s and 1s decimal places, but instead store about so many bazillions.  If you store incredibly large number and incredibly large number plus one into double precision variables, you'll find that both are now the exact same rough approximation of incredibly large number.  This is useful in many situations, but it's no help at all in calculating prime numbers.  We're left with Int64 as our best option.

I find myself offended that my spell checker continues for flag quintillion as misspelled, even though it's a perfectly cromulent word, while accepting bazillion, an imaginary made up number, as correct.

Remember back at the start of the article when I mentioned you could only use GB32 to calculate very small primes?  You think I'm wrong, don't you?  After all, I just showed you that GB32 can handle integer numbers in the quintillion (19 digit) range.  Surely, we can calculate a very large prime, right?

Wrong.  The largest known prime is 257885161-1.  That exponent is 57 million.  This number, written out in standard decimal form, is over 17 million digits long.  If you started typing that out, hitting an average of one key per second, it would take over six months to finish.  That's what the prime number people consider a large prime.  When they speak of small primes, they mean prime numbers with less than 100 digits.  Get that?  A googol, that's 10^100 or a 1 with 100 zeroes after it, is a small number to these people.  When they say something like "here's a program for calculating primes, but it's inefficient and only good for very small numbers," they mean any number easily stored in any default variable type in any programming language you've ever heard of.

Yes, there are ways to work with integers larger than 2^63-1 in GB32, but they are beyond the scope of this article.  (Snicker.)

So, how do we work with "very small" primes in GB32?  First, make sure you're using the Int64 or Large data type for any variable that might hold a prime candidate or prime factor.

Dim n, p, i, q27b as Large

Now, let's say we want to find out if a number is prime or not.  The first thing we do is thin the herd a bit.  It just so happens that all prime numbers have a final digit, the 1s place, of 1, 3, 7, or 9.  That's not to say that all numbers which end with 1-3-7-9 are prime.  It's just that if they don't, we definitely know that they're not prime.  You see, if they end in any even number like 2-4-6-8, we know they're evenly divisible by 2, so they can't be prime.  If they end in 0 or 5, we know they're evenly divisible by 5, so they can't be prime.

Function IsPrime(p) As Boolean ' determines if candidate 'p' is a prime number
  Local t$
  t$=Right$(Str$(p))
  If t$="1" Or t$="3" Or t$="7" Or t$="9" Then
    Rem Do more detailed analysis.
  Else ' definitely not a prime
    Return False
  Endif
EndFunction

I just threw that together, so there may be some errors, but I think you get the general idea.  Now, as for more detailed analysis, the only real way to tell if a number is prime is to try dividing it by all smaller primes (up to the square root of that number) and seeing if one of the divisions comes out even.  You only have to go up to the square root of the number because, worst case, at least one of the factors has to be at most as large as the square root and is probably going to be a lot smaller.  In fact, for "very small primes" like we're working with, some programs just divide the prime candidate by a list of the first 100 or so primes (hard-coded into the program or loaded from disk) and figure that if nothing comes out even, there's a 99% or better chance that the candidate is prime and that's close enough.

A good generic program for the "Do more detailed analysis" would look something like this:

For n = 3 to Sqr(p) Step 2
  If p mod n = 0 Then ' evenly divisible!
    Return False
  Endif
Next n
Return True

(Note:  I'm not sure the mod operator works with Large variables, as there's mention in the help file that parameters that aren't integers are converted to a 32 bit value first.  Large variables are integers, but they use 64 bits and not 32, so would they be converted?  Or does the conversion only happen to floating point values?  Must do more experimenting.  You can re-write the routine to not use the mod operator, but this way is neater.  It may not always work, but it's neater.)

This method involves dividing the prime candidate by all odd integers from 3 to the square root of the candidate, so it takes a little longer than just dividing by previously known primes, but you don't have to calculate or store any previously known primes, so it kind of evens out.  You could, of course, maintain a list of the first 100 or so primes, check all of them first, then continue with larger odd numbers.  We don't need to check even numbers because those are divisible by 2 and we've already eliminated them.

All the above is what I will call the brute force method.  I'm sure the prime number people have their own name for it.

Now we will talk about the sieve method.  There are several variations, but the basic principle is that you start with a list from 2 to the largest number you want to test.  So if you wanted to find all the prime numbers up to 100, your list would be 2, 3, 4, ... 99, 100.  The first number is prime, so print that out or move it to your prime list or whatever.  Then go through the rest of the list marking off all multiples of 2.  This will mark off 4, 6, 8, and in fact all the even numbers.  You then move to the next number on the list which hasn't been marked off, which is prime and in this case 3.  Print that out, then mark off all the multiples of 3 (which will include some of the numbers marked off by 2, but that's okay).  The next number not marked off is 5, so that's prime.  Continue until you get up to the square root of your largest number.  Any number not yet marked off the list is prime.

Coding an example of this for GB32 is left as an exercise for the reader.  (Snicker.)

The problem with implementing this method in GB32 is that you need a large array to keep track of which numbers have been crossed off the list.  At the very least, you need a boolean (true/false) array of size largest number you want to test.  We're hoping to test numbers as large as _maxLarge or 2^63-1 or 9 qunitillion.  Unfortunately, the largest boolean array I can dimension in GB32 is a bit over 2^30 or 1 billion.  So you can only use this method to calculate very small primes up to that size.  If you cheat and hard code in 2 as the first prime, your list can consist of only odd numbers, so you can raise that to 2 billion, but that's still a long way from quintillions.

The sieve process works fine if you want to know if a particular number is prime, or if you want to know all the primes smaller than a target number, but what if you want to know the first 100 primes?  Well, it turns out that the nth prime number is equal to or less than n log n.  In GB32 syntax, that would be n * log2(n).  If you use that value as your highest number in the sieve, it will generate at least n primes.  In our "very small numbers" range, it overshoots it by about 10%, but I'm told that for suitably large numbers it's quite accurate.  Also, it's supposed to be natural log and not log base 2 (log vs log2 in GB32 syntax), but that seems to generate a number about 20% too small.  Perhaps I'm using it wrong.

There's no sample code to download just yet.  I may add some in the future or you can email me your code.
Comments