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 (26)

  1. Levi says:

    Excellent work on the BigInteger type!  I’ve been going over the assembly with Reflector, and it looks like it will be very useful.

    One concern, though – the type uses managed arrays as a backing store.  It is likely that many people will implement cryptographic operations using BigInteger, and the potential for sensitive information (keys, etc.) to remain in memory is high.  Is there any plan to mitigate this risk, or am I missing some implementation detail and overthinking here?

    Thanks!

  2. There’s been a need for this for some time, and the guys have finally included this new BCL type in the

  3. awesome work! i can’t wait to use it.

  4. Jon Skeet says:

    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? 🙂

    Jon

  5. 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?

  6. Inbar Gazit says:

    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.

  7. grauenwolf says:

    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 Function

  8. 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.aspx

  9. You’ve been kicked (a good thing) – Trackback from DotNetKicks.com

  10. Oleg Ufaev says:

    >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!

  11. Vadimmer says:

    IMHO BigDecimal and bitwise operations are extremely needed

  12. We definitely need the ability to work with numeric types in generic methods.

  13. Aaron says:

    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 😉

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

  15. Tim says:

    wow, bitwise operations are a part of all Smalltalk  integer types. Simply because they inherit from the class Integer.  

  16. Ri Geon-Un says:

    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.

  17. Lem says:

    Nice class, gonna try to take fun!

    And don’t forget that 0! = 1! = 1

  18. Fduch says:

    System.Core.dll

    Hmmm….

    It’s cool name but is it good?

  19. În versiunea Orcas de .NET s-a introdus un nou namespace: System.Numeric. În acest namespace se regăseşte

  20. Незабаром в нас буде нова версія .Net Framework 3.5, яка схоже, як і 3.0, буде спиратися на базовий .Net

  21. Sharp Fool says:

    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 SharpFool

  22. So, you know I was thinking, Int64 is just too limiting for my integers. I mean, I might generate a product…

  23. I’m pleased to let you all know that Microsoft released the first beta version of the next version of

  24. While installing VisualStudio 2008 Beta2 I was surprised that the NET framework 2.0 installation got

  25. Joshua Goodman&#39;s session on CLR futures was packed – the crowd of developers wanted to learn what&#39;s