Handling big numbers in C

**robatino** · 07-05-2007

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 %ll and %llu, respectively. %d is for int. I think this is correct, based on some googling, I've never actually used them.

**lala123** · 07-05-2007

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;
}

**robatino** · 07-05-2007

For added efficiency, note that the slowest operation is the %, 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.

**lala123** · 07-05-2007

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;
}

**lala123** · 07-05-2007

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;
}

**robatino** · 07-05-2007

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.

**robatino** · 07-05-2007

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.

**robatino** · 07-05-2007

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).

**lala123** · 07-05-2007

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 =)

**robatino** · 07-05-2007

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;
}

**lala123** · 07-05-2007

Perfect! Thanks a lot for your help.

**robatino** · 07-06-2007

Here's a very recently (2004) discovered algorithm that improves upon the sieve of Eratosthenes.

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

**Mortissus** · 07-06-2007

I received today an email telling me that the thread had new messages. The notification system is sooooo slow. Is this hapenning to everyone?

**lala123** · 07-06-2007

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, £1 (100p) and £2 (200p).

And then it asks you how many different ways can £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;
}

**robatino** · 07-06-2007

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.

Thread: Handling big numbers in C

Thread Tools

Search Thread

Display

Similar Threads

signal handling and exception handling

Link List math

Big (and small) numbers...

Using very big numbers, long isn't enough

Adding Line numbers in Word