Saturday, February 24, 2007 8:56 AM bart

System.Numeric.BigInteger

One of the new features in .NET Framework 3.5 is the new namespace System.Numeric that lives in System.Core.dll. It's a pretty lonesome place for a class to be defined in: System.Numeric's only citizen at this very moment is BigInteger. But how happy it is to be there :-) A little tale...

Everyone knows the mathematical ! operator for factorials. Recursively it is defined as a unary operator on natural numbers:

0! = 1
n! = n * (n-1)! for n > 0

which can be implemented using a simple loop:

int res = 1; for (int i = 2; i <= n; i++) res *= i; return res;

The bottleneck? Take a look at the type of res, which is int (aka System.Int32). Further than 12! you won't get without overflowing. Replacing the type by long instead of int won't help us much further: after calculating 20! we're out of luck (question: would uint or ulong bring us any further?). Luckily BigInteger is here to help us out. A sample:

1 using System; 2 using System.Numeric; 3 4 namespace ConsoleApplication1 5 { 6 class Program 7 { 8 static void Main(string[] args) 9 { 10 FactorialWithInt32(); 11 FactorialWithInt64(); 12 FactorialWithBigInteger(); 13 } 14 15 static void FactorialWithInt32() 16 { 17 int res = 1; 18 19 try 20 { 21 checked 22 { 23 for (int n = 2; ; n++) 24 Console.WriteLine("{0}! = {1}", n, res *= n); 25 } 26 } 27 catch { } 28 } 29 30 static void FactorialWithInt64() 31 { 32 long res = 1; 33 34 try 35 { 36 checked 37 { 38 for (int n = 2; ; n++) 39 Console.WriteLine("{0}! = {1}", n, res *= n); 40 } 41 } 42 catch { } 43 } 44 45 static void FactorialWithBigInteger() 46 { 47 BigInteger res = 1; 48 49 try 50 { 51 checked 52 { 53 for (int n = 2; ; n++) 54 Console.WriteLine("{0}! = {1}", n, res *= n); 55 } 56 } 57 catch { } 58 } 59 } 60 }

The checked keyword performs overflowing checks and is needless in the FactorialWithBigInteger sample; BigInteger won't run out of juice pretty soon (basically, a BigInteger is an abstraction of an array of integer values together with a sign, with overloads for typical integer operators). So, if you ever need to deal with large (I mean really large!) integers, BigInteger might be something for you. However, keep in mind that BigIntegers are slower in use (after all, it has to deal with much more data than a simple add operation) so unless you really need to keep a large value, stay away from it.

A few notes

What do I need to run the sample? Answer: download the January 07 CTP of Orcas

Where is System.Core.dll? Answer: take a look at %windir%\Microsoft.NET\Framework\v3.5.11209

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

Comments

# re: System.Numeric.BigInteger

Sunday, February 25, 2007 11:26 AM by Tom

> question: would uint or ulong bring us any further?

No, 21! needs 66Bits and  13! 33 Bits... so unisigned won't help much

(not testet, but there was this tiny calculator on my desk...)

;)

Thomas

# An introduction to C# 3.0

Friday, April 13, 2007 5:27 AM by 芭蕉

不知不觉间,己经加入C#QAteam四个多月了,天天在和Orcas打交道,却一直没有好好的去学习C#3.0。现在Orcasbeta1己经signoff,我想也是时间开始认识学习C#3.0了...

# The Case of The Failed Demo – StackOverflowException on x64

Wednesday, July 07, 2010 2:35 AM by B# .NET Blog

Introduction A while ago I was explaining runtime mechanisms like the stack and the heap to some folks