tags:

views:

770

answers:

8

Does anybody know of a way I can calculate very large integers in c#

I am trying to calculate the factorial of numbers e.g.

5! = 5*4*3*2*1 = 120

with small numbers this is not a problem but trying to calculate the factorial of the bigest value of a unsigned int which is 4,294,967,295 it doesn't seem possible.

I have looked into the BigInteger class but it doesn't seem to do what I need

any help would be greatly appreciated

+3  A: 

Firstly, it's worth pointing out that the factorial of uint.MaxValue is astronomically large. I'm not able to find a good estimate of the order of magnitude of its factorial, but its bit representation will probably occupy a high percentage of a standard RAM, if not well exceed.

A BigInteger class seems to be what you want, providing you only want to go up to around 1,000,000 or so (very roughly). After that, time and memory become very prohibitive. In current (stable) versions of .NET, up to 3.5, you have to go with a custom implementation. This one on the CodeProject seems to be highly rated. If you happen to be developing for .NET 4.0, the Microsoft team have finally gotten around to including a BigInteger class in the System.Numerics namespace of the BCL. Unlike some BigInteger implementations, the one existing in .NET 4.0 doesn't have a built-in factorial method (I'm not sure about the CodeProject one), but it should be trivial to implement one - an extension method would be a nice way.

Since you seem to think you don't want to use a BigInteger type, it would be helpful if you could verify that it's not what you want having read my reply, and then explain precisely why it doesn't suit your purposes.

Noldorin
It was in 2.0 beta and was removed in final... It was System.Numeric.BigInteger at that time, I hope they don't change their mind this time...
Mehrdad Afshari
@Mehrdad: Indeed. I knew it was pulled out of .NET 3.5, but not 2.0. There already exists a stable implementation in .NET 4.0 beta 1, so it would be quite stupid to remove it now.
Noldorin
Yes, it was 3.5. I think that one was stable too... Sometimes people do stupid thing ;) who knows :P
Mehrdad Afshari
Yes, quite. I do however have a good amount of faith in the .NET devs. :) Or maybe I'm just optimistic... The fact that the documentation has already been written can only be a good sign.
Noldorin
Yeah, probably they pulled it to have something more than just "dynamic" to add in v4.0. :)) Kidding.
Mehrdad Afshari
Noldorin - it's not that I don't want to use the BigInteger class - I have tried - but at some point i keep getting an exception. there is a setting called maxLength which has to be changed but no matter to what I set it - when i run it on large numbers it still gives an exception. I guess I will just have to keep plugging away at it - thanks!
Avner
@Avner: Ah fair enough. Keep having a play around, and if you're still getting that error, post the exact details so that we can take a look. I take it you're using the CodeProject impelementation?
Noldorin
Noldorin - Yes I am - Thanks again
Avner
A: 

Try to use an array for this task. You could use as long integers as you have free memory space. Every member of array repsesents one decimal digit. The only you need is to implement multipication.

Vanuan
would you have any basic code that implements what you are describing? when you say each member of the array would represent a decimal digit - wouldn't that be wasting space because even if i have an array of bytes - each byte would hold a single digit when realy it could hold a value up to 255. unless I didn't understand you?!
Avner
I've realized that it is similar to creating new integer type. You need to implement basic operations such as multyplication. It could be waste of space to store 1 decimal digit into byte. But you can use a bit array (the BitArray class for example).There is some basic code http://www.daniweb.com/code/snippet233.htmlHope it helps.
Vanuan
A: 

You can use the BigInteger class from the J# libraries for now. Here's an article on how. It makes deployment harder because you have to send out the J# redistributable. You can also consider going to VS2010 beta as Framework 4.0 will have BigInteger.

JP Alioto
+7  A: 

To calculate the factorial of uint.MaxValue you'd need a lot of storage.

For example, the Wikipedia article as 8.2639316883... × 10^5,565,708. You're going to gain information like crazy.

I strongly suspect you're not going find any way of calculating it on a sane computer in a sane amount of time. Why do you need this value? Would Stirling's approximation be close enough?

Jon Skeet
I don't see how any approximation is going to solve the issue. firstly because I need the exac result and secondly because even an approximation will still need to be calculated and would still be a very large number - no?
Avner
Well it depends on what you'd need to do with it. If you could keep it as "it's roughly 10^x" for some x, that would be a lot less information than "It's exactly 1929494...." However, if you need the exact result I suspect you're going to have a big problem.
Jon Skeet
A: 

In case you have J# redist installed, an alternative way would be using java.math.BigInteger by adding a reference to the vjslib assembly.

Mehrdad Afshari
+2  A: 

Why do you think that you need to calculate those factorials? It's not practiacally useful for anything to do the actual calculations.

Just the result of calculating factorial of (2^32-1) would take up a lot of space, approximately 16 GB.

The calculation itself will of course take a lot of time. If you build the program so that you can transfer the calculation process to faster hardware as it is invented, you should be able to get the result within your lifetime.

If it's something like an Euler problem that you are trying to solve, consider that a lot of solutions are found by elliminating what it is that you actually don't have to calculate in order to get the answer.

Guffa
A: 

If you are doing calculations with factorials like combinations for example you rarely need to multiply all the way down to 1 (eg. 98 * 98 * 97 since everything else cancels out).

+2  A: 

4294967295! = 10^(10^10.597) ~ 10^(40000000000) This value requires about 40 Gb of RAM to store, even if you will find any BigInteger implementation for C#!

P.S. Well, with optimized storing, let's say 9 digits in 4 bytes, it will take ~18 Gb of RAM.

Nikolay Vyahhi
I can see your point. I guess with current technology it wouldn't be practical.thanks
Avner