Best Bignum Library to Solve Project Euler Problems in C++

Best bignum library to solve Project Euler problems in C++?

Here are a couple of links regarding GMP and Visual Studio 2008:

GMP Install Help at CodeGuru

GMP Compile Guide at The Edge Of Nowhere (this one looks really thorough)

Project Euler #8, I don't understand where I'm going wrong

In fact your solution is too small rather than too big. The answer is what was pointed out in the comments, that there is integer overflow, and the clue is in the fact that your solution is close to the largest possible value for an signed int: 2147483647. You need to use a different type to store the product.

Note that the answer below is still 'correct' in that your code does do this wrong, but it's not what is causing the wrong value. Try taking your (working) code to http://codereview.stackexchange.com if you would like the folks there to tell you what you could improve in your approach and your coding style.

Previous answer

You are checking for a new greatest product inside the inner loop instead of outside. This means that your maximum includes all strings of less or equal ton 13 digits, rather than only exactly 13.

This could make a difference if you are finding a string which has fewer than 13 digits which have a large product, but a 0 at either end. You shouldn't count this as the largest, but your code does. (I haven't checked if this does actually happen.)

for (int i=0; i < num.length() -12; i++)
{
    product = ((int) num[i] - 48);
    for (int j=i+1; j<i+13; j++)
    {
        product = product * ((int) num[j] - 48);
    }
    if (greatestProduct <= product)
    {
        greatestProduct = product;
    }
}

C or C++ BigInt library on Microsoft Windows

GMP.

LGPL. Standard download from official website is designed for GCC. VC++ port is available from here.

Project Euler #16 - C# 2.0

A number of a series of digits. A 32 bit unsigned int is 32 binary digits. The string "12345" is a series of 5 digits. Digits can be stored in many ways: as bits, characters, array elements and so on. The largest "native" datatype in C# with complete precision is probably the decimal type (128 bits, 28-29 digits). Just choose your own method of storing digits that allows you to store much bigger numbers.

As for the rest, this will give you a clue:

2¹ = 2

2² = 2¹ + 2¹
2³ = 2² + 2²

Example:

The sum of digits of 2^100000 is 135178
Ran in 4875 ms

The sum of digits of 2^10000 is 13561
Ran in 51 ms

The sum of digits of 2^1000 is 1366
Ran in 2 ms

SPOILER ALERT: Algorithm and solution in C# follows.

Basically, as alluded to a number is nothing more than an array of digits. This can be represented easily in two ways:

• As a string;
• As an array of characters or digits.

As others have mentioned, storing the digits in reverse order is actually advisable. It makes the calculations much easier. I tried both of the above methods. I found strings and the character arithmetic irritating (it's easier in C/C++; the syntax is just plain annoying in C#).

The first thing to note is that you can do this with one array. You don't need to allocate more storage at each iteration. As mentioned you can find a power of 2 by doubling the previous power of 2. So you can find 2¹⁰⁰⁰ by doubling 1 one thousand times. The doubling can be done in place with the general algorithm:

carry = 0
foreach digit in array
  sum = digit + digit + carry
  if sum > 10 then
    carry = 1
    sum -= 10
  else
    carry = 0
  end if
  digit = sum
end foreach

This algorithm is basically the same for using a string or an array. At the end you just add up the digits. A naive implementation might add the results into a new array or string with each iteration. Bad idea. Really slows it down. As mentioned, it can be done in place.

But how large should the array be? Well that's easy too. Mathematically you can convert 2^a to 10^f(a) where f(a) is a simple logarithmic conversion and the number of digits you need is the next higher integer from that power of 10. For simplicity, you can just use:

digits required = ceil(power of 2 / 3)

which is a close approximation and sufficient.

Where you can really optimise this is by using larger digits. A 32 bit signed int can store a number between +/- 2 billion (approximately. Well 9 digits equals a billion so you can use a 32 bit int (signed or unsigned) as basically a base one billion "digit". You can work out how many ints you need, create that array and that's all the storage you need to run the entire algorithm (being 130ish bytes) with everything being done in place.

Solution follows (in fairly rough C#):

    static void problem16a()
    {
        const int limit = 1000;
        int ints = limit / 29;
        int[] number = new int[ints + 1];
        number[0] = 2;
        for (int i = 2; i <= limit; i++)
        {
            doubleNumber(number);
        }
        String text = NumberToString(number);
        Console.WriteLine(text);
        Console.WriteLine("The sum of digits of 2^" + limit + " is " + sumDigits(text));
    }

    static void doubleNumber(int[] n)
    {
        int carry = 0;
        for (int i = 0; i < n.Length; i++)
        {
            n[i] <<= 1;
            n[i] += carry;
            if (n[i] >= 1000000000)
            {
                carry = 1;
                n[i] -= 1000000000;
            }
            else
            {
                carry = 0;
            }
        }
    }

    static String NumberToString(int[] n)
    {
        int i = n.Length;
        while (i > 0 && n[--i] == 0)
            ;
        String ret = "" + n[i--];
        while (i >= 0)
        {
            ret += String.Format("{0:000000000}", n[i--]);
        }
        return ret;
    }

What is the standard (or best supported) big number (arbitrary precision) library for Lua?

The lmapm library by Luiz Figueiredo, one of the authors of the Lua language.

---

Related Topics