working with incredibly large numbers in .NET

Question

I'm trying to work through the problems on projecteuler.net but I keep running into a couple of problems.

The first is a question of storing large quanities of elements in a List<t>. I keep getting OutOfMemoryException's when storing large quantities in the list.

Now I admit I might not be doing these things in the best way but, is there some way of defining how much memory the app can consume?

It usually crashes when I get abour 100,000,000 elements :S

Secondly, some of the questions require the addition of massive numbers. I use ulong data type where I think the number is going to get super big, but I still manage to wrap past the largest supported int and get into negative numbers.

Do you have any tips for working with incredibly large numbers?

Thermit

In .NET 4.0, System.Numerics.BigInteger deals with large numbers. – Bydgoszcz

Answer 1

Consider System.Numerics.BigInteger.

Salt

Answer 2

You need to use a large number class that uses some basic math principals to split these operations up. This implementation of a C# BigInteger library on CodePoject seems to be the most promising. The article has some good explanations of how operations with massive numbers work, as well.

Also see: Big integers in C#

Arieariel

Answer 3

As far as Project Euler goes, you might be barking up the wrong tree if you are hitting OutOfMemory exceptions. From their website:

Each problem has been designed according to a "one-minute rule", which means that although it may take several hours to design a successful algorithm with more difficult problems, an efficient implementation will allow a solution to be obtained on a modestly powered computer in less than one minute.

Montage

lol, yes. I'm not mega mathematicien. Though I'm hoping to learn a something – Thermit

you can get by pretty well with some basic number theory and set theory. Read up on Miller Rabin primality test for a lot of those prime number problems. – Disincentive

Answer 4

I assume this is C#? F# has built in ways of handling both these problems (BigInt type and lazy sequences).

You can use both F# techniques from C#, if you like. The BigInt type is reasonably usable from other languages if you add a reference to the core F# assembly.

Lazy sequences are basically just syntax friendly enumerators. Putting 100,000,000 elements in a list isn't a great plan, so you should rethink your solutions to get around that. If you don't need to keep information around, throw it away! If it's cheaper to recompute it than store it, throw it away!

Marbleize

Answer 5

As user Jakers said, if you're using Big Numbers, probably you're doing it wrong.

Of the ProjectEuler problems I've done, none have required big-number math so far. Its more about finding the proper algorithm to avoid big-numbers.

Want hints? Post here, and we might have an interesting Euler-thread started.

Remnant

A random down-vote, without comment, over a year and a half from the original post? How curious! – Remnant

ProjectEuler is more about clever math than clever programming, which I actually find a little annoying. – Caressa

Answer 6

See the answers in this thread. You probably need to use one of the third-party big integer libraries/classes available or wait for C# 4.0 which will include a native BigInteger datatype.

Nally

Answer 7

As far as defining how much memory an app will use, you can check the available memory before performing an operation by using the MemoryFailPoint class.

This allows you to preallocate memory before doing the operation, so you can check if an operation will fail before running it.

Fatal

Answer 8

string Add(string s1, string s2)
{
        bool carry = false;
        string result = string.Empty;

        if (s1.Length < s2.Length)
            s1 = s1.PadLeft(s2.Length, '0');
        if(s2.Length < s1.Length)
            s2 = s2.PadLeft(s1.Length, '0');

        for(int i = s1.Length-1; i >= 0; i--)
        {
            var augend = Convert.ToInt64(s1.Substring(i,1));
            var addend = Convert.ToInt64(s2.Substring(i,1));
            var sum = augend + addend;
            sum += (carry ? 1 : 0);
            carry = false;
            if(sum > 9)
            {
                carry = true;
                sum -= 10;
            }
            result = sum.ToString() + result;
        }
        if(carry)
        {
            result = "1" + result;
        }

    return result;
}

Shena

Answer 9

I am not sure if it is a good way of handling it, but I use the following in my project.

I have a "double theRelevantNumber" variable and an "int PowerOfTen" for each item and in my relevant class I have a "int relevantDecimals" variable.

So... when large numbers is encountered they are handled like this:

First they are changed to x,yyy form. So if the number 123456,789 was inputed and the "powerOfTen" was 10, it would start like this:

theRelevantNumber = 123456,789 PowerOfTen = 10 The number was then: 123456,789*10^10

It is then changed to: 1,23456789*10^15

It is then rounded by the number of relevant decimals (for example 5) to 1,23456 and then saved along with "PowerOfTen = 15"

When adding or subracting numbers together, any number outside the relevant decimals are ignored. Meaning if you take:

1*10^15 + 1*10^10 it will change to 1,00001 if "relevantDecimals" is 5 but will not change at all if "relevantDecimals" are 4.

This method make you able to deal with numbers up doubleLimit*10^intLimit without any problem, and at least for OOP it is not that hard to keep track of.

Serle

Answer 10

You don't need to use BigInteger. You can do this even with string array of numbers.

class Solution
{
    static void Main(String[] args)
    {
        int n = 5;
        string[] unsorted = new string[6] { "3141592653589793238","1", "3", "5737362592653589793238", "3", "5" };
        
        string[] result = SortStrings(n, unsorted);
        
        foreach (string s in result)
            Console.WriteLine(s);
        Console.ReadLine();
    }
    static string[] SortStrings(int size, string[] arr)
    {

        Array.Sort(arr, (left, right) =>
        {
           
            if (left.Length != right.Length)
                return left.Length - right.Length;
            return left.CompareTo(right);
        });
       
        return arr;
    }
}

Fp

But how would you add them? – Gifford

Abhilash Virat, can you explain how the Array.Sort () Lamda function is working? I'm not following it. – Frustrated

This doesn't answer the question(s) – Iconology

Answer 11

If you want to work with incredibly large numbers look here...

MIKI Calculator

I am not a professional programmer i write for myself, sometimes, so sorry for unprofessional use of c# but the program works. I will be grateful for any advice and correction. I use this calculator to generate 32-character passwords from numbers that are around 58 digits long. Since the program adds numbers in the string format, you can perform calculations on numbers with the maximum length of the string variable. The program uses long lists for the calculation, so it is possible to calculate on larger numbers, possibly 18x the maximum capacity of the list.

Dwan

This is not an answer – Haukom