Page 1 of 4 123 ... LastLast
Results 1 to 10 of 38

Thread: Prime number support

  1. #1
    Member Johannes's Avatar
    Join Date
    Nov 2010
    Location
    Wuustwezel, Belgium
    Age
    53
    Posts
    95
    Rep Power
    22

    Prime number support

    While watching male lizards fight over females and slightly salted/cheesed biscuits during my vacation I've been pondering prime numbers.
    Programming BigInt_IsPrime, _NextPrime and _PreviousPrime is not difficult. It is difficult to keep those functions fast for really big numbers.
    As it turns out, I think the speed is acceptable.

    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.

  2. #2
    Member Johannes's Avatar
    Join Date
    Nov 2010
    Location
    Wuustwezel, Belgium
    Age
    53
    Posts
    95
    Rep Power
    22
    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.

  3. #3
    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
    
    Attached Files Attached Files

  4. #4
    Member Johannes's Avatar
    Join Date
    Nov 2010
    Location
    Wuustwezel, Belgium
    Age
    53
    Posts
    95
    Rep Power
    22
    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.
    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
    
    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.

    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.

  5. #5
    prime numbers functions is a valuable addition to thinbasic, i have tried to factor this number 123456789123456789 , and the results :
    3*3󬱙113193607380352579 so we can feel more freedom. thank you

  6. #6
    thinBasic MVPs danbaron's Avatar
    Join Date
    Jan 2010
    Location
    California
    Posts
    1,378
    Blog Entries
    29
    Rep Power
    149
    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

  7. #7
    Member Johannes's Avatar
    Join Date
    Nov 2010
    Location
    Wuustwezel, Belgium
    Age
    53
    Posts
    95
    Rep Power
    22
    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:
    Currently, the fastest algorithm for proving the primality of Wagstaff numbers is ECPP.
    And this is what Wikipedia has to say about elliptic curve primality testing.

    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.

  8. #8
    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

  9. #9
    thinBasic MVPs danbaron's Avatar
    Join Date
    Jan 2010
    Location
    California
    Posts
    1,378
    Blog Entries
    29
    Rep Power
    149
    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

  10. #10
    Member Johannes's Avatar
    Join Date
    Nov 2010
    Location
    Wuustwezel, Belgium
    Age
    53
    Posts
    95
    Rep Power
    22
    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.

Page 1 of 4 123 ... LastLast

Similar Threads

  1. prime numbers (1-1000)
    By Lionheart008 in forum Sources, Templates, Code Snippets, Tips and Tricks, Do you know ...
    Replies: 4
    Last Post: 05-07-2010, 17:31
  2. prime numbers spiral
    By zak in forum Math: all about
    Replies: 4
    Last Post: 08-06-2010, 09:02

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •