Number too big for int64_t?

This is a discussion on Number too big for int64_t? within the C Programming forums, part of the General Programming Boards category; Hi guys! I'm getting some troubles trying to find the sum of all primes below 1 million. I think I ...

  1. #1
    Registered User
    Join Date
    Aug 2007
    Posts
    13

    Number too big for int64_t?

    Hi guys! I'm getting some troubles trying to find the sum of all primes below 1 million. I think I created a fairly good program (or at least one that should get the job done!), but apparently I'm having trouble with how I declare my variable/variables. This is the code:

    Code:
    /*The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
    
     Find the sum of all the primes below one million.*/
    
    #include<stdio.h>
    #include<stdint.h>
    #include<math.h>
    
    #define MAX 1000000
    
    int isPrime(int64_t a);
    
    int main(int argc[], char *argv[]) {
        int64_t i;
        uintmax_t sum=0;
    
        for (i=2; i<MAX; i++) {
            if (isPrime(i)==0) {
                sum += i;
                printf("&#37;lld\t", sum);
                printf("%lld\n", i);
            }
        }
        
        printf("%lld", sum);
        printf("Press a key to continue...\n");
        getch();    
    
        return (0);
    }
    
    int isPrime(int64_t a) {
        int64_t i;
        
        if(a%2==0&& a!=2){
            return(1);
        }
        
        for(i=2; i<a/2 ; i++) {
            if(a%i==0) {
                return(1);
            }
        }
    
        return (0);
    }
    I tried to google some snippets of code, looking for variables and types capable of storing huge numbers, and uintmax_t and int64_t (both declared in stdint.h) were the biggest I found. Any way I can solve this or is this bruteforce method flawed?


    edit: Oh yeah, I actually haven't said what's the problem! It compiles smoothly and start running (I guess the algorithm is correct, 'cause the program finds the correct sums up to small numbers, so it should do so for big ones too); around 250k, anyway, the sum reaches I don't know exactly what value, goes negative and start to decrement (that is, to augment...) Around 500k it reaches 0 again and starts to climb up again. Here I usually stop, 'cause I believe this shouldn't definitely be the right behavior...suggestions?
    Last edited by Dorišn; 09-01-2007 at 05:47 PM.

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Whilst it has no functional difference, it is definitely confusing that is "isprime" returning zero rather than one when it's a prime. Please don't call a funcion isxxx and then return "false" when it IS. it should either be "isntprime" or return 0 for something that isn't a prime, and one for something that is.

    To make your code run a bit faster, you may also consider starting your calculation by "knowing" that the value 2 is a prime, and testing values 3 and above. That way, you only need to test odd values, which means half the number of tests - yes, I know, checking if it's divisible by 2 is relatively easy, but it's still completely unnecessary.

    Either way, You can also start your loop in isprime at three, since you have already tested for 2. And since any number above 2 that is a prime is an odd number, you don't need to check if it's divisible by even numbers - because then it would also "catch" on half that number - e.g. 52 is divisible by 26 - but you should already have tested with 13, so it's no point.

    Both of these combined means your code will essentially run 4 times faster (you are testing half the numbers, and with half as many numbers).

    If you know that 2 only 2 is an even prime, why not check with "if(a == 2) return 0;".

    I ran one of my prime number calculators, and it came up with this sum:
    37550402023 (78498 primes)

    You may want to check that you get only primes with your isprime function. I haven't tested with your method - I use sieve of erathostenes(sp?), which is a bit faster (but starts to fall apart after a while because it requires LOTS of memory).

    --
    Mats

  3. #3
    Chinese p‚tť foxman's Avatar
    Join Date
    Jul 2007
    Location
    Canada
    Posts
    404
    I suspect this is due to printf since 64 bits integer can store decimal numbers up to 18 x 10^18. The sum of the first 250 000 integers wouldn't even be close to this. So is the sum of the first 1 000 000 integers.

    But maybe it's something else. Someone out here surely knows.

    Oh and except for the sum variable, i would use int (or unsigned int if you wish) variable instead of fancy int64_t (which i never manipulated, in fact, i'm not sure the library you are talking about (<stdint.h>) is anything but standard). int can store number at least up to 2 billion. I'm one of those guys who, when i have to manipulate integer, will use int before everything else except if i really can't use them. Like in the case of your sum variable...

    And using int may speed up the whole thing a little bit if you are on a 32 bit processor. But if you do want to speed up the process, don't call printf each time you meet a prime number.

    Also, you might want to switch this
    Code:
    for(i=2; i<a/2 ; i++)
    for this
    Code:
    for(i=2; i < sqrt(a); i++)
    or something like
    Code:
    maxUsefulTestValue = (int) sqrt(a);
    for(i=2; i < maxUsefulTestValue; i++)
    but your compiler may have done this optimisation anyway...


    In the last case, you could use some sort of BigNum librairy. But like i said, i'm quite sure this has something to do with printf, so it would be rather useless...
    Last edited by foxman; 09-01-2007 at 06:19 PM. Reason: mistake between scanf and printf

  4. #4
    Registered User ssharish2005's Avatar
    Join Date
    Sep 2005
    Location
    Cambridge, UK
    Posts
    1,682
    int can store number at least up to 2 billion
    You cant just say two billion. It would really depend on his OS and the compiler which he is using.

    ssharish2005

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Foxman: You make a good point. The sum of all primes up to 250000 is a bit over 2 billion, so around the point of wrapping a 32-bit number. So it seems like the the printf isn't printing a 64-bit number. Is this a MS compiler? If so, use %I64d" instead of "%lld".

    --
    Mats

  6. #6
    Chinese p‚tť foxman's Avatar
    Join Date
    Jul 2007
    Location
    Canada
    Posts
    404
    You cant just say two billion. It would really depend on his OS and the compiler which he is using.
    Hah right, i tought the guaranteed minimal magnitude of int was 2^32 but i just checked and saw in was in fact 2^16 (in the case my documentation is up to date). But yeah, i was wrong, this isn't the guaranteed minimal magnitude for int.

    Anyway.

  7. #7
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by foxman View Post
    Hah right, i tought the guaranteed minimal magnitude of int was 2^32 but i just checked and saw in was in fact 2^16 (in the case my documentation is up to date). But yeah, i was wrong, this isn't the guaranteed minimal magnitude for int.

    Anyway.
    I don't think there's ANY minimum guarantee for an int - only that (when it comes to size) char <= int <= long <= long long - but in theory all of them could be 8 bits on some unusually old hardware. 16-bit integers are definitely not unusual in the embedded arena where 16-bit processors are quite commonly used.

    --
    Mats

  8. #8
    Chinese p‚tť foxman's Avatar
    Join Date
    Jul 2007
    Location
    Canada
    Posts
    404
    matsp: Well i don't know, guess we would have to check the document about C official standard.

    I took my information there at cplusplus.com. They could be wrong, but i guess you know this site and agree this is a lovely C documention website.

    But i agree on this "char <= int <= long <= long long".

    [edit] I just did some research and found that in the current C standard (C99) document, at page no. 22 (page no. 34 of pdf pages), it states that int should effectively be at least 16 bits wide. But i agree that doesn't mean every compiler respect the C99 standard.

    Oh, and i also found that <stdint.h> was indeed a standard library since C99. My bad. I'm not really into that C99 standard but more about the ANSI one... hehe... [/edit]
    Last edited by foxman; 09-01-2007 at 06:58 PM.

  9. #9
    Registered User
    Join Date
    Aug 2007
    Posts
    13
    Quote Originally Posted by matsp View Post
    Whilst it has no functional difference, it is definitely confusing that is "isprime" returning zero rather than one when it's a prime. Please don't call a funcion isxxx and then return "false" when it IS. it should either be "isntprime" or return 0 for something that isn't a prime, and one for something that is.
    i don't get your point. My func returns 0 if is a prime, doesn't it? isn't 0 a success return value?

    Quote Originally Posted by matsp View Post
    To make your code run a bit faster, you may also consider starting your calculation by "knowing" that the value 2 is a prime, and testing values 3 and above. That way, you only need to test odd values, which means half the number of tests - yes, I know, checking if it's divisible by 2 is relatively easy, but it's still completely unnecessary.

    Either way, You can also start your loop in isprime at three, since you have already tested for 2. And since any number above 2 that is a prime is an odd number, you don't need to check if it's divisible by even numbers - because then it would also "catch" on half that number - e.g. 52 is divisible by 26 - but you should already have tested with 13, so it's no point.

    Both of these combined means your code will essentially run 4 times faster (you are testing half the numbers, and with half as many numbers).

    If you know that 2 only 2 is an even prime, why not check with "if(a == 2) return 0;".

    I ran one of my prime number calculators, and it came up with this sum:
    37550402023 (78498 primes)

    You may want to check that you get only primes with your isprime function. I haven't tested with your method - I use sieve of erathostenes(sp?), which is a bit faster (but starts to fall apart after a while because it requires LOTS of memory).

    --
    Mats
    yeah, I was skipping even numbers in the function, now I implemented a condition in the main for loop, so to pass to the function only odd numbers!
    According to this txt, my prime numbers (up to 997) are correct, so I believe are correct even after 997!

    Quote Originally Posted by foxman View Post
    I suspect this is due to printf since 64 bits integer can store decimal numbers up to 18 x 10^18. The sum of the first 250 000 integers wouldn't even be close to this. So is the sum of the first 1 000 000 integers.

    But maybe it's something else. Someone out here surely knows.

    Oh and except for the sum variable, i would use int (or unsigned int if you wish) variable instead of fancy int64_t (which i never manipulated, in fact, i'm not sure the library you are talking about (<stdint.h>) is anything but standard). int can store number at least up to 2 billion. I'm one of those guys who, when i have to manipulate integer, will use int before everything else except if i really can't use them. Like in the case of your sum variable...

    And using int may speed up the whole thing a little bit if you are on a 32 bit processor. But if you do want to speed up the process, don't call printf each time you meet a prime number.
    Those types where inherited from previous versions of the code, I left them there without reason...now I changed them back to int, leaving only sum declared as an uintmax_t...the printfs are there for visual debugging, just to check everything is running correctly!

    Quote Originally Posted by foxman View Post
    But like i said, i'm quite sure this has something to do with printf, so it would be rather useless...
    You think so? So maybe is not my fault after all ?!
    perhaps I could try to write it in a file? Would it change something?

  10. #10
    Registered User
    Join Date
    Aug 2007
    Posts
    13
    Quote Originally Posted by matsp View Post
    Foxman: You make a good point. The sum of all primes up to 250000 is a bit over 2 billion, so around the point of wrapping a 32-bit number. So it seems like the the printf isn't printing a 64-bit number. Is this a MS compiler? If so, use %I64d" instead of "%lld".

    --
    Mats

    I'm using Eclipse's CDT...

  11. #11
    Registered User
    Join Date
    Aug 2007
    Posts
    13
    You know what, guys? I think I64d made the trick. I changed the printf in the loop and left unchanged the one at the end of the program. I looped up to MAX/2 (just to try it out) and the first one printed "9914236195", while the last one printed "1324301603". Now I've got the program running, doing the full loop...let's see if this works!

  12. #12
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Dorišn View Post
    i don't get your point. My func returns 0 if is a prime, doesn't it? isn't 0 a success return value?
    Not strictly, and most importantly, functions like "isdigit" or "isalpha" returns a "true/false" result, where true is considered any non-zero value, and false is zero. Your function uses this naming convention, but operates in the opposite way.

    There are lots of functions where returning non-zero is an indication of success, fopen(), fread/fwrite are but a few examples where a non-zero result (or non-NULL - but as NULL and zero have the same value in most instances, I classify this as the same).

    If you actually want to indicate SUCCESS/FAILURE, then you should return SUCCESS and compare with SUCCESS, not return 0 and compare with 0 - the fact that SUCCESS happens to be zero (in some systems) is besides the point.

    But I still think functions that have similar names should operate in similar ways - so something called "isxxx" should return non-zero (e.g. 1) for "is" and 0 for "isn't".


    yeah, I was skipping even numbers in the function, now I implemented a condition in the main for loop, so to pass to the function only odd numbers!
    According to this txt, my prime numbers (up to 997) are correct, so I believe are correct even after 997!
    Sounds right then - I wasn't saying it was wrong, just that you should check it - obviously, if you are adding more numbers than you should, the number would grow larger than it should too!

    You think so? So maybe is not my fault after all ?!
    perhaps I could try to write it in a file? Would it change something?
    Writing to a file using fprintf() wouldn't change anything. I don't know much abotu Eclipse CDT, so I don't know if it's printf supports 64-bit prints.

    Perhaps you can use a manual conversion, like this:
    Code:
    char *lltostr(uintmax_t n, char *str, int maxlen) {
        char *s = str[maxlen-1];
        *s-- = 0;   /* Start by marking the end */
        do {
            *s--- = (char)((n % 10) + '0');
             n /= 10;
        } while(n);
        return s;
    }
    
    ...
       char ss[25];
       printf("Sum = %s\n", lltostr(sum, ss, 25))
    ...
    --
    Mats

  13. #13
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    9914236195 is what I get for 0.5 million primes, so it looks like you've cracked it.

    --
    Mats

  14. #14
    Registered User
    Join Date
    Aug 2007
    Posts
    13
    Quote Originally Posted by matsp View Post
    Not strictly, and most importantly, functions like "isdigit" or "isalpha" returns a "true/false" result, where true is considered any non-zero value, and false is zero. Your function uses this naming convention, but operates in the opposite way.

    There are lots of functions where returning non-zero is an indication of success, fopen(), fread/fwrite are but a few examples where a non-zero result (or non-NULL - but as NULL and zero have the same value in most instances, I classify this as the same).

    If you actually want to indicate SUCCESS/FAILURE, then you should return SUCCESS and compare with SUCCESS, not return 0 and compare with 0 - the fact that SUCCESS happens to be zero (in some systems) is besides the point.

    But I still think functions that have similar names should operate in similar ways - so something called "isxxx" should return non-zero (e.g. 1) for "is" and 0 for "isn't".
    Oh, all right, I got your point now. Is more a "standard" issue, then, am I right? Perhaps I could use EXIT_SUCCESS and EXIT_FAILURE, as declared in stdlib.h? (meh, I believe they're declared respectively as 0 and 1, so it wouldn't change really much, would it?)


    Quote Originally Posted by matsp View Post
    Sounds right then - I wasn't saying it was wrong, just that you should check it - obviously, if you are adding more numbers than you should, the number would grow larger than it should too!
    yeah, that would cause some trouble!


    Quote Originally Posted by matsp View Post
    Writing to a file using fprintf() wouldn't change anything. I don't know much abotu Eclipse CDT, so I don't know if it's printf supports 64-bit prints.

    Perhaps you can use a manual conversion, like this:
    Code:
    char *lltostr(uintmax_t n, char *str, int maxlen) {
        char *s = str[maxlen-1];
        *s-- = 0;   /* Start by marking the end */
        do {
            *s--- = (char)((n % 10) + '0');
             n /= 10;
        } while(n);
        return s;
    }
    
    ...
       char ss[25];
       printf("Sum = %s\n", lltostr(sum, ss, 25))
    ...

    I guess I'm lucky the CDT likes I64d, 'cause I really can't understand what this code does ! What should I convert with it?

  15. #15
    Registered User
    Join Date
    Aug 2007
    Posts
    13
    SUCCESS! Thanks guys, problem solved!

    here's the final code, perhaps I could still learn something from errors I overlooked...

    Code:
    /*The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
    
     Find the sum of all the primes below one million.*/
    
    #include<stdio.h>
    #include<stdint.h>
    #include<math.h>
    
    #define MAX 1000000
    
    int isPrime(int a);
    
    int main(int argc[], char *argv[]) {
        int i;
        uintmax_t sum=2;
    
        for (i=3; i<MAX; i++) {
            if(i%2!=0){
                if (isPrime(i)==0) {
                    sum += i;
                    printf("%I64d\t", sum);
                    printf("%d\n", i);
                }
            }
        }
        
        printf("\n%I64d\n", sum);
        printf("Press a key to continue...\n");
        getch();    
    
        return (0);
    }
    
    int isPrime(int a) {
        int i;
            
        for(i=3; i<a/2 ; i++) {
            if(a%i==0) {
                return(1);
            }
        }
    
        return (0);
    }
    (still haven't changed return values of the function, sorry mats )

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

Similar Threads

  1. Link List math
    By t014y in forum C Programming
    Replies: 17
    Last Post: 02-20-2009, 06:55 PM
  2. Replies: 6
    Last Post: 02-19-2009, 07:19 PM
  3. how to transform an aray of char in to a big number
    By transgalactic2 in forum C Programming
    Replies: 1
    Last Post: 01-03-2009, 06:41 AM
  4. Issue w/ Guess My Number Program
    By mkylman in forum C++ Programming
    Replies: 5
    Last Post: 08-23-2007, 02:31 AM
  5. help with a source code..
    By venom424 in forum C++ Programming
    Replies: 8
    Last Post: 05-21-2004, 01:42 PM

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