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?

Answer 1

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: http://stackoverflow.com/questions/176775/big-integers-in-c

Answer 2

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.

Answer 3

Consider System.Numerics.BigInteger. It's coming to the BCL in .NET 4.0.

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!

Answer 5

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.

Answer 6

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.

Answer 7

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.