Handling big numbers in C

This is a discussion on Handling big numbers in C within the C Programming forums, part of the General Programming Boards category; Your code looks almost right, except for 3 things: 1) To iterate 7830457 times, the loop condition should be "i ...

  1. #16
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    Your code looks almost right, except for 3 things:
    1) To iterate 7830457 times, the loop condition should be "i < 7830457", not "i <= 7830457".
    2) I suspect that the constant 10000000000 may be treated as an int by default, instead of a long long, and get truncated. Try writing the constant as 10000000000LL or 10000000000LLU instead; that should tell the compiler that the constant is long long or unsigned long long, resp. Do this everywhere you use this number.
    3) After "number++;", you need to reduce number mod 10000000000 again, just in case it happened to be exactly 10000000000.

    Edit: Oh, and 4) The printf() specifiers for long long and unsigned long long should be &#37;ll and %llu, respectively. %d is for int. I think this is correct, based on some googling, I've never actually used them.
    Last edited by robatino; 07-05-2007 at 06:15 PM.

  2. #17
    the magic penguim
    Join Date
    Jul 2005
    Posts
    91
    robatino

    Thanks a lot robantino =) I find it amazing how small the code is...

    Code:
    #include <stdio.h>
    
    int main ()
    {
        unsigned long long number = 28433;
    
        for (int i = 0; i < 7830457; i++)
        {
            number = (number << 1) &#37; 10000000000LLU;
        }
    
        number = (number + 1) % 10000000000LLU;
    
        printf ("%llu",  number);
        return 0;
    }

  3. #18
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    For added efficiency, note that the slowest operation is the &#37;, and you can minimize the number of times that gets called by doing as many bitwise left shifts as you can without exceeding the capacity of an unsigned long long, before using %. Suppose number was 9999999999, which is less than 2^34, and the maximum value of an unsigned long long is (2^64)-1. Then you could double number 30 times without overflow, and this is the worst case, since you started out with the largest possible 10-digit number. This means you can do your left shifts in chunks of 30, so you can left-shift by 30 261015 times, followed by a single left shift by 7 (since 7830457 == 261015*30 + 7). This way you only have to do about 1/30 as many % operations. I'll leave it to you to work out the messy details.

  4. #19
    the magic penguim
    Join Date
    Jul 2005
    Posts
    91
    The same problem done using the gmp library, by uranther posted at the project euler's forum:

    Code:
    int main(void)
    {
        mpz_t pow, product, final;
        char *finalstring;
    
        mpz_init(pow);
        mpz_init(product);
        mpz_init(final);
    
        mpz_ui_pow_ui(pow, 2, 7830457);
        mpz_mul_ui(product, pow, 28433);
        mpz_add_ui(final, product, 1);
    
        finalstring = mpz_get_str(NULL, 10, final);
    
        printf("&#37;s\n", finalstring+strlen(finalstring)-10);
    
        return 0;
    }

  5. #20
    the magic penguim
    Join Date
    Jul 2005
    Posts
    91
    Robantino if you have some spare time can you please take a look at this code, it's my implementation of the sieve of erasthothenes... For some reason it ain't working:

    Code:
    #include <stdio.h>
    #include <math.h>
    
    int main(void)
    {
        int primes[1000000];
        int totalPrimes = 0;
    
        for (int i = 0; i < 1000000; i++)
            primes[i] = 1;
    
        for (int i = 0; i < 1000; i++)
        {
            if ((isPrime(i)) && primes[i])
            {
                int mul = 1;
                while ( (i * mul) < 1000000)
                {
                    primes[i*mul] = 0;
                    mul ++;
                }
            }
        }
    
        for (int i = 0; i < 1000000; i++) // testing the code
            if (primes[i])
                printf("&#37;d ", i);
    
        return 0;
    }
    
    int isPrime (int n)
    {
        for (int i = 2; i < sqrt(n); i++)
        {
            if (!(n % i))
                return 0;
        }
    
        return 1;
    }

  6. #21
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    Code:
      int primes[1000000];
    You're trying to allocate 4 MB statically (assuming 4 byte ints). This may fail immediately, and in general you shouldn't try to allocate more than a fraction of a MB that way. Allocate the array dynamically using malloc() instead.
    Code:
      for (int i = 2; i < sqrt(n); i++)
    It should be "i <= sqrt(n)", and should be written instead as "i*i <= n", as this will both be faster and you don't have to worry about floating-point arithmetic. You could also check for divisibility by 2, and then by the odd numbers from 3 up, to reduce the time by a factor of 2.

    Edit: Actually, you could precompute the biggest integer less than or equal to sqrt(n) (call it m) and then use "i <= m" which is even faster. You need to be careful that floating-point error doesn't cause it to be one too small.

    Edit: I think if you let m = sqrt(n + .5), where m is an int, that should work. The .5 should prevent m from being too small, without making it any bigger. There could be a better way, though.
    Last edited by robatino; 07-05-2007 at 10:07 PM.

  7. #22
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    Code:
      if ((isPrime(i)) && primes[i])
    You don't need to call isPrime(i), since if primes[1] == 1, then you know i is prime (so you can just get rid of the isPrime() function, and ignore most of my previous comments). Just use
    Code:
      if (primes[i])
    Standard C90 doesn't allow variable declarations in the middle of a block:
    Code:
      int mul = 1;
    This is another gcc nonstandard extension. For standards-compliant code, declare mul at the beginning of main() with the other variables, and then just set it to 1 inside the if statement.

  8. #23
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    Declaring i inside each of the for loops is only allowed in C99, not C90. You should declare i at the start of main(), not inside the for loops. Also, when you initialize the values primes[i], you should initialize primes[0] and primes[1] to 0, and the rest to 1.
    Code:
      for (int i = 0; i < 1000; i++)
    This loop should start at 2, not 0. Finally, mul should be initialized to 2, not 1 (otherwise you end up setting primes[i] to 0).

  9. #24
    the magic penguim
    Join Date
    Jul 2005
    Posts
    91
    Hehe to be pretty honest with you I don't know how to use malloc :P I've just gone back to programing and I don't quite remember some aspects like pointers or memory... So I can't make that change in the code If you could please do it for me...

    About the other change, removing the isPrime routine, I've done it.

    I've also noticed a huge error, if that variable mul is set to 1 initially all multiples of the prime will be stripped, including the prime itself! So now mul is set to two.

    Code:
    #include <stdio.h>
    
    int main(void)
    {
        int *primes = malloc(1000000 * sizeof (int));
        int totalPrimes = 0;
        int mul;
    
        for (int i = 0; i < 1000000; i++)
            primes[i] = 1;
    
        primes[0] = 0;
        primes[1] = 0;
    
        for (int i = 2; i < 1000; i++)
        {
            if (primes[i])
            {
                mul = 2;
                while ( (i * mul) < 1000000)
                {
                    primes[i*mul + 2] = 0; // because the loop starts at two
                    mul ++;
                }
            }
        }
    
        for (int i = 0; i < 1000000; i++) // testing the code
            if (primes[i])
                printf("&#37;d ", i);
    
        return 0;
    }
    Edit: Sorry I've missed your last post :P Hehe we've spotted the same errors =)
    Last edited by lala123; 07-05-2007 at 11:05 PM.

  10. #25
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    Code:
      primes[i*mul + 2] = 0;
    Take out the "+ 2". You should also #include <stdlib.h> whenever using malloc(), and to get your code to compile, I had to declare i at the start of main(), not in the for() loops. With these changes, your code works properly. Here is a version I got working earlier (I tend to write compressed code). I use assert() as a quick-and-dirty way to check malloc() for NULL.
    Code:
    #include <assert.h>
    #include <stdio.h>
    #include <stdlib.h>
    
    int main(void) {
      int i, mul, *primes;
    
      assert(primes = malloc(1000000*sizeof(int)));
      primes[0] = primes[1] = 0;
      for (i=2; i<1000000; i++) primes[i] = 1;
    
      for (i=0; i<1000; i++) {
        if (primes[i]) {
          for (mul=2*i; mul<1000000; mul += i) primes[mul] = 0;
        }
      }
    
      for (i=0; i<1000000; i++) {
        if (primes[i]) printf("&#37;d\n", i);
      }
    
      free(primes);
      return 0;
    }

  11. #26
    the magic penguim
    Join Date
    Jul 2005
    Posts
    91
    Perfect! Thanks a lot for your help.

  12. #27
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    Here's a very recently (2004) discovered algorithm that improves upon the sieve of Eratosthenes.

    http://en.wikipedia.org/wiki/Sieve_of_Atkin

  13. #28
    Registered User Mortissus's Avatar
    Join Date
    Dec 2004
    Location
    Brazil, Porto Alegre
    Posts
    152
    I received today an email telling me that the thread had new messages. The notification system is sooooo slow. Is this hapenning to everyone?

  14. #29
    the magic penguim
    Join Date
    Jul 2005
    Posts
    91
    I'm doing one of euler's challenges, and I'm completely clueless about this one =P

    It tells you that there are eight coins in circulation in england: 1p, 2p, 5p, 10p, 20p, 50p, &#163;1 (100p) and &#163;2 (200p).

    And then it asks you how many different ways can &#163;2 be made using any number of coins.

    If someone could just show an algorithm wich would be helpfull here... I don't even know where to start =/

    Here's my code so far, I tried implementing a greedy algorithm because it's the only one google pointed me out:

    Code:
    #include <stdio.h>
    
    int main(void)
    {
        int coins[] = {1, 2, 5, 10, 20, 50, 100}, i, j, temp, ways = 1;
    
        // I've removed the 200p coin and increased the ways var
    
        for (i = 6; i >= 0; i++)
        {
            temp = 200;
            temp -= coins[i];
    
            while (temp > 0)
            {
                for (j = 6; j >= 0; j++)
                {
                    if (temp >= coins[j])
                    {
                        temp -= coins[j];
                        break;
                    }
    
                    if (j == 0)
                        printf("No solutions....");
                }
            }
    
            ways++;
        }
    
        return 0;
    }

  15. #30
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    Well, the number of 200p coins in any combination adding up to 200p is either 0 or 1. For each of these possibilities, you can work out the possible numbers of 100p coins (0, 1, or 2 in the first case, 0 in the second). For each of these, etc., etc. You could count all the possibilities with a set of nested loops, one for each type of coin, with the outermost loop being for 200p.

    Edit: For an arbitrary set of denominations, you could define a function that takes as arguments the desired sum, the number of different denominations, and an array containing the values (preferably in decreasing order), and returns the number of combinations. It can be implemented recursively.
    Last edited by robatino; 07-06-2007 at 11:01 PM.

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

Similar Threads

  1. signal handling and exception handling
    By lehe in forum C++ Programming
    Replies: 2
    Last Post: 06-15-2009, 11:01 PM
  2. Link List math
    By t014y in forum C Programming
    Replies: 17
    Last Post: 02-20-2009, 06:55 PM
  3. Big (and small) numbers...
    By swif in forum C Programming
    Replies: 6
    Last Post: 04-22-2005, 01:21 PM
  4. Using very big numbers, long isn't enough
    By Zewu in forum C++ Programming
    Replies: 9
    Last Post: 03-27-2005, 07:54 AM
  5. Adding Line numbers in Word
    By Mister C in forum A Brief History of Cprogramming.com
    Replies: 24
    Last Post: 06-24-2004, 09:45 PM

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