High precision integer math in C#?

Question

Hi,

I have a very large number I need to calculate, and none of the inbuilt datatypes in C# can handle such a large number.

Basicly I want to solve this:

Project Euler 16:

2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2^1000?

I have already written the code, but, as said before, the number is too large for c# datatypes. The code has been tested and verified with small numbers (such as 2^15) and it works perfectly.

using System;

namespace _16_2E1000
{
    class Program
    {
        static void Main(string[] args)
        {
            ulong sum = 0;
            ulong i = 1 << 1000;
            string s = i.ToString();
            foreach (char c in s)
            {
                sum += (ulong) Convert.ToInt64(c.ToString());
            }
            Console.WriteLine(sum);
            Console.ReadLine();
        }
    }
}

Answer 1

First to answerer you exact question, look for a BigInt or BigNum type

Second, from what I know of Project Euler, there will be a cool, tricky way to do it that is much easier.

As a first guess I'd compute the answerer for 2^1 -> 2^n (for whatever n you can get to work) and look for patterns. Also look for patterns in the sequences

V(0) = 2^p

V(n) = floor(V(n - 1) / 10)  
D(n) = V(n) % 10

Answer 2

You can use BigInteger from the J# classes. First question in this article tells you how. It's a bit of pain b/c then you have to provide the J# redistributable when you roll out tho.

Answer 3

I hope this is not a homework problem, but to get to the answer of 2^1000, you'll have to divide it into smaller chunks,

try something like,

2^1000 = 2 * 2^999 = 2^999 + 2^999 = 2^ 998 + 2^ 998 + 2^ 998 + 2^ 998

breaking into smaller bits till you get to solvable a problem,

complete solution to project Euler is on following links.

http://blog.functionalfun.net/2008/07/project-euler-problem-16-calculating.html http://code.msdn.microsoft.com/projecteuler

Answer 4

It is not necessary to have Big Integer capabilities in order to solve this problem.

One could just use the property that:

2^n = 2^(n-1) + 2^(n-1)

If Big Integer is really necessary for other tasks, I have been using the BigInt class from F# in my C# programs and am happy with it.

The necessary steps:

1. Install the F# CTP

2. In your C# (or other .NET language) application add a reference to the FSharp.Core dll.

3. Add: using Microsoft.FSharp.Math;

4. In the "Class View" window familiarize yourself with the members of the two classes: BigInt and BigNum

After executing these steps one is basically ready to use the BigInt class.

One last hint:

To avoid declaring variables with improper names to hold constants that makes the code unreadable, I am using a name that starts with _ (underscore), followed by the integer constant. In this way one will have expressions like:

N = _2 * N;

clearly much more readable than:

N = Two * N;

Answer 5

Here's a BigInteger (source code is available) that you can use; though, as already mentioned, there are more efficient ways to do this than brute force.

BigInteger on codeplex

Answer 6

Actually, while a biginteger utility might be of interest here, you don't need it, even for this. Yes, it looks like it does, but you don't. In fact, use of a biginteger form may even slow things down.

Since I don't want to solve the problem for you, I'll just suggest you think about this in a modular way.