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?

Solution 1

Consider System.Numerics.BigInteger.

Solution 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#

Solution 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.

Solution 4

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.

Solution 5

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!

View more solutions

Comments

[Greg B]

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

[Nicholas Mancuso]

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.

[abelenky]

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

[FCin]

But how would you add them?

[Michael Barber]

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

[n4rzul]

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