views:

1236

answers:

7

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?

A: 

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.

Pwninstein
I have already tried with double, long etc. With the same result.
priyanka.sarkar
Sorry I couldn't be more help! Good luck!
Pwninstein
+1  A: 

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

Dries Van Hansewijck
Thanks ..even I have also seen that before.Please give a solution for the same code.
priyanka.sarkar
+7  A: 

.NET 4.0 has a BigInteger class

Thomas Levesque
Sweet - did not know about BigInteger class!
TWith2Sugars
The OP shouldn't use BigInteger at all. See Robert's answer.
Mehrdad Afshari
A: 

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.

MaLKaV_eS
I have done in this way.. but it is not at all feasible solution.Do you think it is indeed?
priyanka.sarkar
+1  A: 

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?

Dmitry Risenberg
+26  A: 

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.

Enjoy,

Robert C. Cartaino

Robert Cartaino
Yep. Modular arithmetic: (a * b) % m == ((a % m) * (b % m)) % m
Mehrdad Afshari
That's a much more concise way to explain my long-winded example <grin>.
Robert Cartaino
A: 

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.

JP Alioto