Prime number support has been added. See the release in the sticky topic.
While watching male lizards fight over females and slightly salted/cheesed biscuits during my vacation I've been pondering prime numbers.
As it turns out, I think the speed is acceptable.Programming BigInt_IsPrime, _NextPrime and _PreviousPrime is not difficult. It is difficult to keep those functions fast for really big numbers.
I did some test just now, in (interpreted) thinBasic using the module as is, and checking if 100000000003 is prime (it is) takes 1.2 seconds (first attempt was 6.8 seconds) and finding the next prime number from that point (100000000019) also takes 1.2 seconds (first attempt was 6.9 seconds). This is of course in thinBasic, not as a module. Speed should increase significantly.
Working with prime numbers below 2^32 will be quite fast and up to 2^64 (my two examples mentioned above) I think the speed will still be acceptable. Above 2^64 (where the prime factors cross the magic 32-bit line) things will be slow. But that is of course up to the user.
So far I'm thinking of implementing BigInt_IfPrime, BigInt_NextPrime, BigInt_PrevPrime and BigInt_FactPrime. The last one will return an array with the prime factors of the given Big Integer. If anybody has suggestions for more functions dealing with primes, let me know in this thread.
Boole and Turing, help me!
Primary programming: 200 MHz ARM StrongARM, RISC OS 4.02, BASIC V, ARM assembler.
Secondary programming: 3.16 GHz Intel Core 2 Duo E8500, Vista Home Premium SP2, thinBasic, x86 assembler.
Prime number support has been added. See the release in the sticky topic.
Boole and Turing, help me!
Primary programming: 200 MHz ARM StrongARM, RISC OS 4.02, BASIC V, ARM assembler.
Secondary programming: 3.16 GHz Intel Core 2 Duo E8500, Vista Home Premium SP2, thinBasic, x86 assembler.
Hi Johannes
how to adapt this example about prime numbers to give a meaningfull results. i got only the first one to work, the other it displayed unwanted chars, only BigInt_IsPrime are working for me
Uses "console" Module "BigInt" String someprime=BigInt_FromInteger(53) Dim prime As Long prime = BigInt_IsPrime(someprime) PrintL prime Dim a As String a = BigInt_FromInteger(89) PrintL BigInt_NextPrime(a) Dim s As String s="9" Dim pf(2) As String BigInt_FactPrime(s,pf) PrintL pf(1) PrintL pf(2) s = BigInt_FromString("9") BigInt_FactPrime(s,pf) PrintL pf(1) PrintL pf(2) WaitKey
Zak,
Here is the changed script. Your main problem was that it is not possible to directly print Big Integers. You always need to use BigInt_ToString. Only conversion from string to Big Integer is automatic, not the other way around.
I'll try to make proper example functions as soon as possible but that takes a lot of time and I still have to do all the bit stream stuff.Uses "Console" Module "BigInt" ' Define a prime. String someprime=BigInt_FromInteger(53) ' Find out if it really is a prime. Dim prime As Boolean prime = BigInt_IsPrime(someprime) If prime Then PrintL "Prime" Else PrintL "Not prime" EndIf ' Directly print a larger prime. Dim a As String a = BigInt_FromInteger(89) PrintL BigInt_ToString(BigInt_NextPrime(a)) ' Variable a is still 89, not 97. PrintL BigInt_ToString(a) ' Determine prime factors for a number. Dim s As String Dim i,n As Integer s="9" Dim pf(2) As String ' The '2' is not necessary. Dim pf() is enough. BigInt_FactPrime(s,pf) ' Determine how many prime factors were returned. n = UBound(pf) ' Print all prime factors using BigInt_ToString. For i=1 to n PrintL BigInt_ToString(pf(i)) Next i ' The next code works the same as the previous example ' because BigInt_FromString is automatic there. s = BigInt_FromString("9") BigInt_FactPrime(s,pf) n = UBound(pf) For i=1 to n PrintL BigInt_ToString(pf(i)) Next i WaitKey
The most important thing to remember is that you cannot print a Big Integer directly. You must always use BigInt_ToString.
Boole and Turing, help me!
Primary programming: 200 MHz ARM StrongARM, RISC OS 4.02, BASIC V, ARM assembler.
Secondary programming: 3.16 GHz Intel Core 2 Duo E8500, Vista Home Premium SP2, thinBasic, x86 assembler.
prime numbers functions is a valuable addition to thinbasic, i have tried to factor this number 123456789123456789 , and the results :
3*3×7×11×13×19×3607×3803×52579 so we can feel more freedom. thank you
Hi Johannes.
(I admit, this is sort of a dirty trick.)
Dan
****************************************
Programmer's Challenge
Code and perform the numerical calculation to determine with 100% certainty if the following integer is prime.
201487636602438195784363
****************************************
Last edited by danbaron; 05-04-2011 at 20:59.
"You can't cheat an honest man. Never give a sucker an even break, or smarten up a chump." - W.C.Fields
Well, of course I used google to see if this was a particular type of prime, and it is.
The number 201487636602438195784363 is the 12th Waggstaff prime W79. (Why not the 13th Wagstaff Prime W101? I love 13. )
Quoth Wikipedia:
And this is what Wikipedia has to say about elliptic curve primality testing.Currently, the fastest algorithm for proving the primality of Wagstaff numbers is ECPP.
This would take me a year to program, assuming I am that good. So doing a BigInt_IfPrime and waiting the week (or two) would be faster.
Either way, I don't think so Dan.
Boole and Turing, help me!
Primary programming: 200 MHz ARM StrongARM, RISC OS 4.02, BASIC V, ARM assembler.
Secondary programming: 3.16 GHz Intel Core 2 Duo E8500, Vista Home Premium SP2, thinBasic, x86 assembler.
never cease to be amazed at the unexpected turns while surfing the net,
just now while searching for the prime number that Dan posted above
found out about sexy primes http://en.wikipedia.org/wiki/Sexy_prime
Just for fun.
When someone gets some extra time.
Factor the following composite integer.
21130819027319923178509622632727980622577522491335986162202750512019525136688895741633235387039306968582318693021114825649130164135868576427684517893
Last edited by danbaron; 06-04-2011 at 10:01.
"You can't cheat an honest man. Never give a sucker an even break, or smarten up a chump." - W.C.Fields
That's a 111-digit number. Let me guess, does it consist of two 56-digit primes?
This is why at first I was reluctant to add the prime number support. I told myself this would happen.
Although I am convinced of the usefulness of BigInt, the one obvious drawback is that certain operations will be so slow as to be unusable. Multiplication, division, powers and roots of extremely large numbers are very, very slow. But anything having to do with prime numbers larger than, say, 15 decimal digits is just unworkable.
Maybe I'll put the factoring of that 111-digit number in my will.
Boole and Turing, help me!
Primary programming: 200 MHz ARM StrongARM, RISC OS 4.02, BASIC V, ARM assembler.
Secondary programming: 3.16 GHz Intel Core 2 Duo E8500, Vista Home Premium SP2, thinBasic, x86 assembler.
Bookmarks