How to use large numbers

This is a discussion on How to use large numbers within the C Programming forums, part of the General Programming Boards category; Hello Team (Hellow World?), I am a new C learner, I am trying to learn the language on my own, ...

  1. #1
    Registered User
    Join Date
    Jan 2011
    Posts
    1

    How to use large numbers

    Hello Team (Hellow World?),

    I am a new C learner, I am trying to learn the language on my own, which it does not look too bad with the tutorials on this site.

    I wrote a simple program to determine the primality of a number.
    I wanted to extend my program to handle very large numbers.
    Sure I can go on the web and find a number of routines already written, but I will not learn.

    I want to modify the program, which I will list below, to:
    1. Handle very large numbers with millions of digits
    2. Use pointers to create a list of prime numbers as the program finds them


    Also, could you please take a look at my simple program and criticize it? I really want to learn the language!

    Thank you


    /* This program will check a number for primality */
    /* It expects 1 argument, an integer, positive number greater than 1 */

    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    #include <string.h>

    int check4prime(int p); /* Prototype function */

    int main(int argc, char *argv[])
    {
    int n;

    if (argc != 2) exit(EXIT_FAILURE); /* Need at least 2 args */

    sscanf(argv[1], "%d", &n); /* Convert String to int */

    if ( check4prime(n) ) /* if 1 is returned, we found a prime */
    {
    /* It is prime */
    printf("%d is prime!\n", n);
    exit(EXIT_SUCCESS);
    } /* End if */

    } /* End of main */

    /* ################################### */
    /* Function to check for primality */
    /* ################################### */

    int check4prime(int p)
    {
    if ( p <= 1 ) return 0; /* Prime can't be <= 1 */
    if ( p == 2 || p == 3 ) return 1; /* first 2 prime numbers */

    int rem = p % 2; /* No even #, except 2, is known to be prime */
    if ( rem == 0) return 0; /* Eliminate even # first */

    /* If we are here, that means the number is odd and it is neither 2 nor 3 */
    /* Can it be prime? */
    /* All known primes => 5, when divided by 6 have remainder of 1 or 5 */

    rem = p % 6; /* Possible prime have rem = 1 or 5 */
    if ( rem == 1 || rem == 5 ) /* Possible prime? */
    {
    /* So far, so good */
    /* Continue checking for primality */

    int k;
    int sr = sqrt(p); /* No need to check behind sqrt(p) */

    for ( k = 2; k <= sr; k++ ) {
    if ( p % k == 0 )
    {
    return 0; /* False */
    }
    } /* for */

    return 1; /* True, found a prime */
    }
    return 0; /* True, found a prime */
    } /* End of check4prime */

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,598
    Quote Originally Posted by thecstudent
    I wrote a simple program to determine the primality of a number.
    I wanted to extend my program to handle very large numbers.
    Sure I can go on the web and find a number of routines already written, but I will not learn.

    I want to modify the program, which I will list below, to:

    1. Handle very large numbers with millions of digits
    2. Use pointers to create a list of prime numbers as the program finds them
    For starters, I suggest that you take a look at the GNU Multiple Precision Arithmetic Library. Download it and use it to extend your program with functionality #2. After you have it working fine and dandy, put it aside so that it can function as a reference implementation, i.e., you can use it to check if your program extended with your own arbitrary integer library implementation is working correctly.

    Quote Originally Posted by thecstudent
    Also, could you please take a look at my simple program and criticize it? I really want to learn the language!
    Post code within bbcode tags as it makes reading code easier (assuming that you have good formatting to begin with).
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,831
    As a small refinement, this loop
    Code:
    for ( k = 2; k <= sr; k++ )
    ... instead you can start at 5 and increment by 2.

  4. #4
    Password:
    Join Date
    Dec 2009
    Location
    NC
    Posts
    587
    /* All known primes => 5, when divided by 6 have remainder of 1 or 5 */

    Generalization: Any number that, when divided by n#, has a remainder of either 1 or a prime > n, is coprime to all primes <= n. Where # denotes primorial.
    Last edited by User Name:; 01-10-2011 at 02:07 PM.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    "millions of digits"?!?!
    I'm researching this very problem right now for my own big-int class.
    Do you realise that even with 100000 digits you typically require somewhere between days and decades of processing time to determine with only a high degree of certainty that it is prime? (I.e. still can't be absolutely sure).
    If you're really interested in determinig primality of large numbers then you have a lot of research to do before you'll get anywhere at all.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    theCstudent -- Welcome to the forum!

    Always put your code between code tags so it can be read easily.

    Quote Originally Posted by User Name: View Post
    /* All known primes => 5, when divided by 6 have remainder of 1 or 5 */

    Generalization: Any number that, when divided by n#, has a remainder of either 1 or a prime > n, is coprime to all primes <= n. Where # denotes primorial.
    Interesting - thanks. I didn't know prime numbers % 6 equaled either 1 or 5.

    Can you expand on the Generalization part? I felt this blast of something zing by my head - I must have instinctively ducked, because it went right by me.

    Thanks User Name.
    Last edited by Adak; 01-10-2011 at 11:38 PM.

  7. #7
    Password:
    Join Date
    Dec 2009
    Location
    NC
    Posts
    587
    We'll use 5#(2*3*5=30) for the example. All numbers, n, indivisible by 2, 3, AND 5 will meet the condition "n % 30 equals either 1 or any prime more than 5 and less than 30".

    The test is similar to the Sieve of Eratosthenes, in how it eliminates a set of numbers based on what they're divisible by. The example I gave eliminates all numbers divisible by 2, 3, or 5, so it is effectively the same as doing the first 3 steps of the Sieve of Eratosthenes.

    EDIT: Actually, it would be make sense to give the example in the same way as the original:
    Where he said:
    "All known primes => 5, when divided by 6 have remainder of 1 or 5,"(To be precise, it should be "All know primes => 6", but the results are the same.)
    for our example, we would say:
    "All known primes => 30, when divided by 30 have remainder of 1, 7, 11, 13, 17, 19, 23, or 29"
    Last edited by User Name:; 01-11-2011 at 01:44 AM.

  8. #8
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    1,623
    Quote Originally Posted by uggmini View Post
    Although I do not know what that means, but I still hope to learn from learning
    That's the spirit!
    Devoted my life to programming...

  9. #9
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    On low numbers, this won't speed up your search for a prime, but on large numbers, it surely will help a lot:

    "All prime numbers, are numbers that will not divide evenly by any other prime number, of lesser value."

    That seems obvious, since primes will not divide evenly by any number except 1, but to use the above, in a program avoids ALL the testing of numbers against the candidate prime number, except for the prime numbers you've already found, of lesser value.

    Say I want to test 10001 to see if it's a prime number. Instead of testing (starting the testing with 7):
    7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99, 101. 48 tests in all.

    You only wind up testing:
    7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 37, 39, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101. 27 tests in all.

    As the number go higher, and primes become more widely separated (on average), that reduction in testing becomes greater.

    I used an array to hold these lesser primes, but for the high range of primes you want to work with, that wouldn't be practical to hold all of them. You could hold a lot of them though.

    In the realm of "mathematically intuitive and simple" code, it makes for a quick program - the first 12,000 prime numbers are found in 0.11 seconds on one thread of a 2.66 C2D cpu. It won't compare with the math intense ultra speedsters, but it's a lot faster than the less elegant, normal prime program, you see on the net so frequently.

  10. #10
    Password:
    Join Date
    Dec 2009
    Location
    NC
    Posts
    587
    The test is only probabilistic. Any number indivisible by 2, 3, and 5 will pass the example test. In other words, it fails for most multiple of 7 and higher primes

    Not only that, but its effectiveness decreases as the numbers being tested increase.

  11. #11
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by User Name: View Post
    The test is only probabilistic. Any number indivisible by 2, 3, and 5 will pass the example test. In other words, it fails for most multiple of 7 and higher primes

    Not only that, but its effectiveness decreases as the numbers being tested increase.
    ? All the tests in this thread have been exact. (And the only multiple of 7 that is prime is 7, which passes.)

  12. #12
    Password:
    Join Date
    Dec 2009
    Location
    NC
    Posts
    587
    The way I recommend you use it, is to do something like this:

    Code:
    for(int i = 1;i <= limit;i++)
    {
         primetest(6 * i + 1);
         primetest(6 * i + 5);
    }
    Which will only produce numbers indivisible by 2 and 3. In effect, this eliminates 2/3 of all numbers.

    tabstop: 49 % 30 = 19, 49 is not prime, yet it passes the test. I meant that most multiples of 7, or of any prime higher than 7, such as 11 will pass the test. 77 % 30 = 17, which means it also passes the test, but is obviously not prime(7*11).
    Last edited by User Name:; 01-11-2011 at 05:40 PM.

  13. #13
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by User Name: View Post
    The way I recommend you use it, is to do something like this:

    Code:
    for(int i = 1;i <= limit;i++)
    {
         primetest(6 * i + 1);
         primetest(6 * i + 5);
    }
    Which will only produce numbers indivisible by 2 and 3. In effect, this eliminates 2/3 of all numbers.

    tabstop: 49 % 30 = 19, 49 is not prime, yet it passes the test. I meant that most multiples of 7, or of any prime higher than 7, such as 11 will pass the test. 77 % 30 = 17, which means it also passes the test, but is obviously not prime(7*11).
    Gotcha, I see what you mean. Yes, it should be used to generate candidates.

  14. #14
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    A 2/3rd's reduction in testing sounds good, but it's really not that great.

    Between 1 and 1,000, using only the previously generated prime numbers to test, you would reduce testing by 83% (there are 168 primes in the range).

    As you go to larger numbers, the reduction would soar. For example, there are only 81 primes between 100,000 and 101,000, or 8 percent primes, a 92% reduction in testing.

    Your suggestion offers no further reduction in testing at higher numbers.

  15. #15
    Password:
    Join Date
    Dec 2009
    Location
    NC
    Posts
    587
    I already said its effectiveness decreases exponentially for large numbers. But are you really going to argue that checking all 1000 numbers to find 81 primes is better than checking 333 numbers and still finding the same primes? Even though it isn't conclusive, it still reduces the set of numbers you have to test by a significant amount.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Printing random decimal numbers in a text file
    By warrick in forum C Programming
    Replies: 3
    Last Post: 03-08-2010, 08:32 AM
  2. how to deal wth large numbers
    By bvgsrs in forum C++ Programming
    Replies: 2
    Last Post: 06-18-2007, 06:16 AM
  3. Handling Large Numbers
    By Xzyx987X in forum C Programming
    Replies: 2
    Last Post: 05-03-2004, 02:33 PM
  4. Help needed with VERY large numbers.
    By jwarner in forum C++ Programming
    Replies: 4
    Last Post: 01-18-2004, 11:01 AM
  5. A (complex) question on numbers
    By Unregistered in forum C++ Programming
    Replies: 8
    Last Post: 02-03-2002, 05:38 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21