Project Euler #16 - C# 2.0

Question

I've been wrestling with Project Euler Problem #16 in C# 2.0. The crux of the question is that you have to calculate and then iterate through each digit in a number that is 604 digits long (or there-abouts). You then add up these digits to produce the answer.

This presents a problem: C# 2.0 doesn't have a built-in datatype that can handle this sort of calculation precision. I could use a 3rd party library, but that would defeat the purpose of attempting to solve it programmatically without external libraries. I can solve it in Perl; but I'm trying to solve it in C# 2.0 (I'll attempt to use C# 3.0 in my next run-through of the Project Euler questions).

Question

What suggestions (not answers!) do you have for solving project Euler #16 in C# 2.0? What methods would work?

NB: If you decide to post an answer, please prefix your attempt with a blockquote that has ###Spoiler written before it.

Answer 1

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

Answer 2

I solved this one using C# also, much to my dismay when I discovered that Python can do this in one simple operation.

Your goal is to create an adding machine using arrays of int values.

Spoiler follows

I ended up using an array of int values to simulate an adding machine, but I represented the number backwards - which you can do because the problem only asks for the sum of the digits, this means order is irrelevant.

What you're essentially doing is doubling the value 1000 times, so you can double the value 1 stored in the 1st element of the array, and then continue looping until your value is over 10. This is where you will have to keep track of a carry value. The first power of 2 that is over 10 is 16, so the elements in the array after the 5th iteration are 6 and 1.

Now when you loop through the array starting at the 1st value (6), it becomes 12 (so you keep the last digit, and set a carry bit on the next index of the array) - which when that value is doubled you get 2 ... plus the 1 for the carry bit which equals 3. Now you have 2 and 3 in your array which represents 32.

Continues this process 1000 times and you'll have an array with roughly 600 elements that you can easily add up.

Answer 3

I have solved this one before, and now I re-solved it using C# 3.0. :)

I just wrote a Multiply extension method that takes an IEnumerable<int> and a multiplier and returns an IEnumerable<int>. (Each int represents a digit, and the first one it the least significant digit.) Then I just created a list with the item { 1 } and multiplied it by 2 a 1000 times. Adding the items in the list is simple with the Sum extension method.

19 lines of code, which runs in 13 ms. on my laptop. :)

Answer 4

Pretend you are very young, with square paper. To me, that is like a list of numbers. Then to double it you double each number, then handle any "carries", by subtracting the 10s and adding 1 to the next index. So if the answer is 1366... something like (completely unoptimized, rot13):

hfvat Flfgrz;
hfvat Flfgrz.Pbyyrpgvbaf.Trarevp;    
pynff Cebtenz {
    fgngvp ibvq Pneel(Yvfg<vag> yvfg, vag vaqrk) {
        juvyr (yvfg[vaqrk] > 9) {
            yvfg[vaqrk] -= 10;
            vs (vaqrk == yvfg.Pbhag - 1) yvfg.Nqq(1);
            ryfr yvfg[vaqrk + 1]++;
        }
    }
    fgngvp ibvq Znva() {
        ine qvtvgf = arj Yvfg<vag> { 1 }; // 2^0
        sbe (vag cbjre = 1; cbjre <= 1000; cbjre++) {
            sbe (vag qvtvg = 0; qvtvg < qvtvgf.Pbhag; qvtvg++) {
                qvtvgf[qvtvg] *= 2;
            }
            sbe (vag qvtvg = 0; qvtvg < qvtvgf.Pbhag; qvtvg++) {
                Pneel(qvtvgf, qvtvg);
            }
        }

        qvtvgf.Erirefr();
        sbernpu (vag v va qvtvgf) {
            Pbafbyr.Jevgr(v);
        }
        Pbafbyr.JevgrYvar();

        vag fhz = 0;
        sbernpu (vag v va qvtvgf) fhz += v;
        Pbafbyr.Jevgr("fhz: ");
        Pbafbyr.JevgrYvar(fhz);
    }
}