What Is The Largest Number A BigInteger Can Be? This Is Amazing?

Page 1 of 1

11 Replies - 2195 Views - Last Post: 29 September 2013 - 07:54 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=330278&amp;s=a319b2716694dcd7cc6d00727108b585&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

Reputation: 12
• Posts: 766
• Joined: 31-August 11

What Is The Largest Number A BigInteger Can Be? This Is Amazing?

Posted 29 September 2013 - 02:50 AM

So I've been playing with the BigInteger class that was released not that long ago in the .net version 4.0 and I'll have to say if it's doing what I think it is it's incredible.

For example say you have the code:

```BigInteger a = BigInteger.Parse("38283211123595798333307550494857347473733496903827263645859437384595");
BigInteger b = BigInteger.Parse("99282736327262441525550002394827736562211111209389111304049575550011");

Console.WriteLine("BigInterger {0}", (a * B)/>.ToString("R"));

```

It appears as long as you parse a string of numbers to the BigInteger type you can calculate ANYTHING so long as the machine has enough time to do so and it's based solely on the power of your machine not of the data types for example a double which can only go to 2 to the 64th power.

Be aware of what I said: A parsed string to the bigint. If you simply type a BigInt as a Variable this won't work. Also it should be converted BACK to a string format using the ToString() Method and you need to pass the parameter in ToString of "R" which tells it to output the BigInteger as itself.

INCREDIBLE!

But I'm confused as to whether or not it's simply rounding at this point? According to Microsoft's Documentation about this here:

http://msdn.microsof...y/dd268260.aspx

It says verbatim

"In most cases, the ToString method supports 50 decimal digits of precision. That is, if the BigInteger value has more than 50 digits, only the 50 most significant digits are preserved in the output string; all other digits are replaced with zeros. However, BigInteger supports the "R" standard format specifier, which is intended to round-trip numeric values. The string returned by the ToString(String) method with the "R" format string preserves the whole BigInteger value and can then be parsed with the Parse or TryParse method to restore its original value without any loss of data. The following example illustrates that a string output using the "R" format string can then be parsed by the Parse method without any data loss."

Notice "Without Data Loss" So I'm assuming it's actually multiplying and outputting the correct number for these incredibly large numbers multiplied together to make and even crazier large number? What do people here know about this?

This post has been edited by adn258: 29 September 2013 - 02:52 AM

Is This A Good Question/Topic? 0

Replies To: What Is The Largest Number A BigInteger Can Be? This Is Amazing?

#2 sepp2k

• D.I.C Lover

Reputation: 2277
• Posts: 3,507
• Joined: 21-June 11

Re: What Is The Largest Number A BigInteger Can Be? This Is Amazing?

Posted 29 September 2013 - 03:31 AM

adn258, on 29 September 2013 - 11:50 AM, said:

a double which can only go to 2 to the 64th power.

I think you're thinking of longs. Unsigned longs can go up to 2^64 (exclusive) and signed longs up to 2^63.

Doubles can represent integers up to 2^53 without data loss and then up to binary 1.111...11 (52 1s after the point) * 2^1023 with data loss (only remembering the 53 first binary digits).

Quote

it should be converted BACK to a string format using the ToString() Method and you need to pass the parameter in ToString of "R" which tells it to output the BigInteger as itself.

You don't need to call ToString explicitly to pass the "R" argument. You can pass it as part of the Format string like this: Console.WriteLine("{0:R}", number);.

PS: Strangely I don't get any rounding even if I don't pass "R" despite what this documentation says. Could this be a localization thing (German locale)? It'd be kind of strange if it were, but that's the only thing that I can think of other than the documentation being wrong/misleading.

PPS: Does anybody know why it would just replace the last digits with 0s without "R"? I mean I'd get it if it cut them of and replace them with E-notation, but just replacing them with 0s doesn't make the number shorter or easier to read - that just seems a confusing thing to do.

This post has been edited by sepp2k: 29 September 2013 - 03:32 AM

Reputation: 12
• Posts: 766
• Joined: 31-August 11

Re: What Is The Largest Number A BigInteger Can Be? This Is Amazing?

Posted 29 September 2013 - 04:16 AM

Thanks for the tips sepp yes strange right? An amazing class built in by Microsoft with what appears to be some quirks.
So correct me if I'm wrong but what you're saying is it's calculating these huge numbers EXACTLY to their true values I.E. there is no rounding going on?

#4 sepp2k

• D.I.C Lover

Reputation: 2277
• Posts: 3,507
• Joined: 21-June 11

Re: What Is The Largest Number A BigInteger Can Be? This Is Amazing?

Posted 29 September 2013 - 05:12 AM

Right, no rounding.

Oh and to answer the question in the title: A .net object can at most be 2GB big. So the array that BigInteger uses to store the number can roughly contain 2^30 bytes (a bit less because the array's header takes some bytes as well), meaning it can store roughly 8*2^30 = 2^33 bits. So the largest possible BigInteger is somewhat smaller than 2^(2^33).

Note that I'm assuming that the sign bit is stored separately and not as part of the array (so I'm also assuming that it uses 1's complement basically). I have no idea if that's true. If it isn't, it'd be 2^(2^32) instead. Either way it will be a freakishly large number.

Reputation: 12
• Posts: 766
• Joined: 31-August 11

Re: What Is The Largest Number A BigInteger Can Be? This Is Amazing?

Posted 29 September 2013 - 12:30 PM

sepp2k, on 29 September 2013 - 05:12 AM, said:

Right, no rounding.

Oh and to answer the question in the title: A .net object can at most be 2GB big. So the array that BigInteger uses to store the number can roughly contain 2^30 bytes (a bit less because the array's header takes some bytes as well), meaning it can store roughly 8*2^30 = 2^33 bits. So the largest possible BigInteger is somewhat smaller than 2^(2^33).

Note that I'm assuming that the sign bit is stored separately and not as part of the array (so I'm also assuming that it uses 1's complement basically). I have no idea if that's true. If it isn't, it'd be 2^(2^32) instead. Either way it will be a freakishly large number.

My computer took a few minutes to calculate this out and yes it was freakishly long but I was even able to calculate (it appears) 56^448000 yes to the 448,000 power. I just chose this because it would obviously be large and it still seemed to work and that's a lot. I guess that wouldn't be as large as 2 to the 2 to the 32nd power though. Amazing!

#6 baavgai

• Dreaming Coder

Reputation: 6379
• Posts: 13,629
• Joined: 16-October 07

Re: What Is The Largest Number A BigInteger Can Be? This Is Amazing?

Posted 29 September 2013 - 12:36 PM

Short answer: How much memory you got?

While there might be a .NET limit per single object, the smart programmer can would make an object, based on objects, based on... well, you get the idea. The sky's the limit.

What so amazed, though? Write your own big int. See how it works. It's a fun exercise, actually.

Reputation: 12
• Posts: 766
• Joined: 31-August 11

Re: What Is The Largest Number A BigInteger Can Be? This Is Amazing?

Posted 29 September 2013 - 12:43 PM

baavgai, on 29 September 2013 - 12:36 PM, said:

Short answer: How much memory you got?

While there might be a .NET limit per single object, the smart programmer can would make an object, based on objects, based on... well, you get the idea. The sky's the limit.

What so amazed, though? Write your own big int. See how it works. It's a fun exercise, actually.

Do you mean you could make this bigger than 2 gigs by using inheritance? What are you saying?

#8 baavgai

• Dreaming Coder

Reputation: 6379
• Posts: 13,629
• Joined: 16-October 07

Re: What Is The Largest Number A BigInteger Can Be? This Is Amazing?

Posted 29 September 2013 - 01:04 PM

I'm saying that, if you're impressed with BitInteger, you should try writing your own, to understand how it works.

I'm also saying that it needn't have a 2GB limit. Indeed, MS doesn't note one:

Quote

... because it has no upper or lower bounds, an OutOfMemoryException can be thrown for any operation that causes a BigInteger value to grow too large. ... its values can grow extremely large and have a measurable impact on performance.
-- http://msdn.microsof...biginteger.aspx

Reputation: 12
• Posts: 766
• Joined: 31-August 11

Re: What Is The Largest Number A BigInteger Can Be? This Is Amazing?

Posted 29 September 2013 - 01:21 PM

baavgai, on 29 September 2013 - 01:04 PM, said:

I'm saying that, if you're impressed with BitInteger, you should try writing your own, to understand how it works.

I'm also saying that it needn't have a 2GB limit. Indeed, MS doesn't note one:

Quote

... because it has no upper or lower bounds, an OutOfMemoryException can be thrown for any operation that causes a BigInteger value to grow too large. ... its values can grow extremely large and have a measurable impact on performance.
-- http://msdn.microsof...biginteger.aspx

Yes essentially you could write a class that does multiplication by hand and yes I've thought about writing one. I also haven't heard of a 2GB limit with BigInteger either anywhere. Essentially if you are writing a program for this you'll need to manage/catch out of memory Exceptions right indeed

#10 Michael26

Reputation: 380
• Posts: 1,574
• Joined: 08-April 09

Re: What Is The Largest Number A BigInteger Can Be? This Is Amazing?

Posted 29 September 2013 - 01:47 PM

You can enable this GC option to use <gcAllowVeryLargeObjects> Element, for that you need .NET 4.5, before this you could enable the /3GB switch Large matrices and vectors

This post has been edited by Michael26: 29 September 2013 - 01:47 PM

• MrCupOfT

Reputation: 2292
• Posts: 9,531
• Joined: 29-May 08

Re: What Is The Largest Number A BigInteger Can Be? This Is Amazing?

Posted 29 September 2013 - 02:10 PM

If you also keep track of where the decimal point would be, it can be used for fractional numbers.

#12 Skydiver

• Code herder

Reputation: 4371
• Posts: 14,107
• Joined: 05-May 12

Re: What Is The Largest Number A BigInteger Can Be? This Is Amazing?

Posted 29 September 2013 - 07:54 PM

As baavgai suggested, if you are really fascinated by how BigInteger works, consider implementing a version yourself. In the C++ forum, there is a guy struggling with his implementation where the digits are stored in a doubly linked list. You need not torture yourself, and simply use a a List<>. (His major problem was not knowing how to deal with pointers in a linked list, not the actual arithmetic operations.)

Try it yourself, you'll find it very educational. Once you've implemented your own BigInteger using a List<> of base 10 digits, next try implementing it as a list of BitVector32's or manage your own bitmap in an large buffer of bytes so that you'll have more efficient storage.