Results 1 to 10 of 38

Thread: Prime number support

Hybrid View

Previous Post Previous Post   Next Post Next Post
  1. #1
    Member Johannes's Avatar
    Join Date
    Nov 2010
    Location
    Wuustwezel, Belgium
    Age
    56
    Posts
    95
    Rep Power
    25

    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
    56
    Posts
    95
    Rep Power
    25
    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
    56
    Posts
    95
    Rep Power
    25
    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×7×11×13×19×3607×3803×52579 so we can feel more freedom. thank you

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

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

Members who have read this thread: 0

There are no members to list at the moment.

Posting Permissions

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