Introducing: System.Numeric.BigInteger [Inbar Gazit]
Update: BigInteger was cut from the .NET 3.5 release.
Have you ever needed a really huge number? So big it just couldn't fit into any other base-type in the framework? Well, no problem anymore, just use the new BigInteger type. You can now have the ability to use integers of any arbitrary size, so they can exponentiate until the cows come home... or memory runs out, whichever comes first :-)
So, what's so "Big" about BigInteger?
I saw some people wondering whether we should have called this new type UnboundedInteger instead of BigInteger and I would like to tell you what I think. First, you should know that the BCL team does not take naming lightly. We spend a lot of time and energy making sure we choose the best names for our types, methods, properties etc. I believe that good names are not only technically accurate but also intuitive and easy to remember and use. That's one of the reasons that made us decide to use the name BigInteger. The other reason was that other languages are using the prefix "Big" for unbounded types. Isn't that huge? Enormous? Gigantic? Well, I think it's simply Big...
Using the new BigInteger
So, what do you need to do in order to use this new type?
First you need to get the latest CTP for the new version of Visual Studio (code name – "Orcas") and install it so that you also get the new version of the .NET Framework including this new type. It would be a good idea to install it on a separate computer or make sure you back-up your important work first. Remember, this is pre-beta software... (in the January CTP you can choose either a Virtual PC image or to use the actual installation bits)
If you do install the bits, all you need is the new System.Core.dll as a reference in your project. The new BigInteger class is in this new assembly.
From this point on I'm going to be talking C# although this can all work for other languages (such as VB.NET).
Create a new C# project and add a new Using System.Numeric at the top of your cs module. Now, you're ready to use BigInteger in your code.
Here is a sample code to calculate factorials:
using System;
using System.Numeric;
namespace TryOutBigInteger {
class MyBigIntApp {
static BigInteger BigFactorial(BigInteger x) {
if (x < 0)
return BigFactorial(-x);
else if (x <= 1)
return x;
else return x * BigFactorial(--x);
}
static void Main(string[] args) {
BigInteger x = BigInteger.Parse(Console.ReadLine());
Console.WriteLine(BigFactorial(x).ToString());
Console.ReadLine();
}
}
}
Here is what we get when we run it:
5
120
And:
300
306057512216440636035370461297268629388588804173576999416776741259476533176716867465515291422477573349939147888701726368864263907759003154226842927906974559841225476930271954604008012215776252176854255965356903506788725264321896264299365204576448830388909753943489625436053225980776521270822437639449120128678675368305712293681943649956460498166450227716500185176546469340112226034729724066333258583506870150169794168850353752137554910289126407157154830282284937952636580145235233156936482233436799254594095276820608062232812387383880817049600000000000000000000000000000000000000000000000000000000000000000000000000
Wow! I wish that was my bank account balance :-)
BigInteger supports most of the operations that int supports including +, -, *, /, ++, --, %, DivRem GreatestCommonDivisor, Pow, ModPow, Abs and Negate. All of these are static methods you can find using intellisense by typing "BigInteger".
Bitwise operations are not supported, but we will have an MSDN article coming soon with how to write your own library extension of BigInteger.
Please try the new BigInteger type and let us know what you think. We'd love to hear your feedback!
Comments
Anonymous
January 16, 2007
The comment has been removedAnonymous
January 16, 2007
There's been a need for this for some time, and the guys have finally included this new BCL type in theAnonymous
January 17, 2007
awesome work! i can't wait to use it.Anonymous
January 17, 2007
The most important (good) part of the naming decision, IMO? It's the one all Java programmers will look up first when they want to find the type. So, can we expect BigDecimal next? :) JonAnonymous
January 17, 2007
TrackBack from http://chyld.net/CS/blogs/cmedford/archive/2007/01/17/that-s-so-big-of-you.aspxAnonymous
January 17, 2007
I ran the code supplied above and gave it 4000 to find the factorial and it worked, but when I gave it 5000 I got a StackOverflowException. Why is this? I have over 1GB memory - it seems like it should of worked. Any thoughts?Anonymous
January 17, 2007
Sorry, the way I implemented Factorial is using recursion which means that we are going to use the stack before we run out of memory as each time you make another call into Factorial the stack grows and the number of calls is the factorial you are trying to implement. You can write this method in an iterative way using a simple for loop and you would avoid this issue.Anonymous
January 17, 2007
That's cool and all, but are you going to create an INumeric interface so I can use generics with it? You know, something that supports this syntax Function Average(Of T AS INumeric)(a as T, b as T) Return A.Add(b).Divide(2) End FunctionAnonymous
January 18, 2007
I changed the recursion to a loop and then computed the factorial for 50,000...the article with the results are here: http://chyld.net/CS/blogs/cmedford/archive/2007/01/17/that-s-so-big-of-you.aspxAnonymous
January 18, 2007
You've been kicked (a good thing) - Trackback from DotNetKicks.comAnonymous
January 18, 2007
>Bitwise operations are not supported, but we will have an MSDN article coming soon with how to write your own library extension of BigInteger. "Great Idea" May be include extension code example from article to BigInteger standart implementation? I can't understand your policy: write article about how inmplement bitwise operations and not implement it in BigInteger. Bitwise operation are used often!Anonymous
January 19, 2007
IMHO BigDecimal and bitwise operations are extremely neededAnonymous
January 19, 2007
We definitely need the ability to work with numeric types in generic methods.Anonymous
January 19, 2007
Wow, I am so used to working with Java and C# at the same time I always just assumed that .NET had a BigInteger type already ;) Well, I guess better late than never. I do wonder what the BCL people were doing when they designed certain parts of the framework initially. This reminds me of the total absence of a LinkedList type of collection class before 2.0. How could they forget something like that? I wanna call "slackers", but other parts of the BCL are so well though out. Its perplexing. On a different note, why does every MS project have a "code name" that has nothing to do with the project or what the project will really eventually be called? Seems goofy ;)Anonymous
January 22, 2007
Smalltalk had “LargeInteger” since the 1970s. In Smalltalk you do not even need to type your variable to LargeInteger: Any computation with an integer that flows over, will automatically convert to LargeInteger.Anonymous
January 23, 2007
wow, bitwise operations are a part of all Smalltalk integer types. Simply because they inherit from the class Integer.Anonymous
January 29, 2007
Congratulations on the implementation of the BigInteger class. Now we need a BitStreamReader and a BitStreamWriter class. :) The .NET Framework is immense, but I feel it's quite lacking.Anonymous
January 30, 2007
Nice class, gonna try to take fun! And don't forget that 0! = 1! = 1Anonymous
February 04, 2007
System.Core.dll Hmmm.... It's cool name but is it good?Anonymous
February 14, 2007
În versiunea Orcas de .NET s-a introdus un nou namespace: System.Numeric. În acest namespace se regăseşteAnonymous
February 15, 2007
Незабаром в нас буде нова версія .Net Framework 3.5, яка схоже, як і 3.0, буде спиратися на базовий .NetAnonymous
February 15, 2007
I would like to propose the inclusion of a function BigInteger BinaryShift(BigInteger b, int n) { return b * BigInteger.Pow(2, n); } This function is a convenience only, but an important one when porting code from other languages. For example it could replace the ubiquitous Java functions BigInteger shiftLeft(int n) [this << n] BigInteger shiftRight(int n) [this >> n] And, of course, it can be implemented much more efficiently compared to the function above. My second suggestion is a much more important one. I think it is almost a must to have the functions Product(T[] a) Sum(T[] a) and for slices of T[] Product(T[] a, int start, int end) Sum(T[] a, int start, int end) for T in {int, long, BigInteger}. Well, you might answer a simple foreach loop will solve this task. And I think a great many people will indeed implement it in this way. However, this is the most inefficient way to compute a sum or a product. For big numbers sequential adding or multiplying tends to be 'unbalanced', a small term or factor is paired with an increasingly large one. Bad. Much better is the strategy of binary splitting. Just for illustration of the idea: BigInteger recProduct(BigInteger[] s, int len) { if (len == 0) return BigInteger.One; if (len == 1) return s[index++]; int len2 = len >> 1; return recProduct(s, len - len2) * recProduct(s, len2); } And the only 'right' place to implement this is BigInteger, of course. Furthermore, something like Product(T[] a) and Sum(T[] a) assists the trend to functional programming in C# 3. So go ahead and show us some improvement over the BigInteger library of Java, written 15 years ago. Cheers SharpFoolAnonymous
April 01, 2007
So, you know I was thinking, Int64 is just too limiting for my integers. I mean, I might generate a product...Anonymous
April 20, 2007
I'm pleased to let you all know that Microsoft released the first beta version of the next version ofAnonymous
August 08, 2007
While installing VisualStudio 2008 Beta2 I was surprised that the NET framework 2.0 installation gotAnonymous
October 30, 2008
Joshua Goodman's session on CLR futures was packed - the crowd of developers wanted to learn what's