Handling “Big” Integers in C#

Question

How do I handle big integers in C#?

I have a function that will give me the product of divisors:

private static int GetDivisorProduct(int N, int product)
    {
        for (int i = 1; i < N; i++)
        {
            if (N % i == 0)
            {
                Console.WriteLine(i.ToString());
                product *= i;
            }
        }

        return product;
    }

The calling function is GetDivisorProduct(N, 1)

If the result is bigger than 4 digits , I should obtain only the last 4 digits. ( E.g. If I give an input of 957, the output is 7493 after trimming out only the last four values. The actual result is 876467493.).

Other sample inputs: If I give 10000, the output is 0.

The BigInteger class has been removed from the C# library!

How can I get the last four digits?

Answer 1

If you're only looking at the last four digits, you don't need anything larger than an integer. Consider this:

When multiplying two numbers, if you are only interested in the least significant digits (i.e. the last four digits), then the upper-most digits will not have an effect on lowest digits of the outcome... so you can just "throw out" the most significant (right-side) digits before you multiply.

For example: I want to multiply two large numbers but I only need the last two digits:

int num1 = 123456789;
int num2 = 987654321;

int result = num1 * num2; // Last two digits would be "69" but this OVERFLOWS

but if we multiply only the last two digits...

int result = (num1 % 100) * (num2 % 100);  // result = 89 * 21

89 * 21 = 1869 (the last two digits are still "69" but we have not overflowed).

I used this technique to calculate the Six Right-Most Digits of 1,000,000 factorial.

Answer 2

.NET 4.0 has a BigInteger class

Answer 3

http://www.codeproject.com/csharp/BigInteger.asp

Answer 4

Well, you can modify your code like this:

    for (int i = 1; i < N; i++)
    {
        if (N % i == 0)
        {
            Console.WriteLine(i.ToString());
            product *= i;
        }
        if (product > 10000 * N)
        {
            product %= 10000;
        }
    }

This is because the last four digits of (10000*k + l)R are the same as for lR. The actual type of product depends on the range of N's you want to handle. If it is all integer type, then product should be long.

By the way, why do you pass product as a parameter, if it is always 1?

Answer 5

How about trying to use a double or long instead of int for product? It would only work in some cases, but it would allow you to work with larger numbers that you've been able to.

Answer 6

I hope I didn't missunderstood, but you want to write in Console "0000" if the result is 0? Have you tried:

Console.WriteLine(i.ToString().PadLeft(4,"0")); 

?

If what you want is to get the number 0000 as an int I'm sorry, but don't know how to get it.

Answer 7

If you can't go to .NET 4.0 right now, you can use BigInteger from the J# library from C#. Here's an article describing how. It does impact deployment as you need to deploy the J# re-distributable.