.NET 4.0 now has a new data type, System.Numeric.BigInteger. From what I understand, this can hold numbers that have, up to, 1 million digits. Simple arithmetic operations can be performed on this number. What I am wondering is how Microsoft implemented such a thing, given that it would obviously exceed 32-bits and even 64-bits. How does this not overflow?
+5
A:
Arithmetic operations have been performed on structures that exceed the native integer (and floating point) sizes for quite some time. This is ordinarily done by turning a single conceptual arithmetic operation on the larger structure (addition, for example), into a series of operations upon multiple native types.
Adam Robinson
2010-08-09 03:06:09
So would using this make math operations slower?
icemanind
2010-08-09 03:09:11
@icemanind: Yes, considerably.
Michael Petrotta
2010-08-09 03:11:38
Slower in the same way a child learning their arithmetic is more than four times slower adding four-digit numbers than adding one-digit numbers, and much slower again multiplying. Not quite that bad in the same way that the child will learn a few shortcuts with experience. You certainly don't want to use it for math that can be adequately handled by the native types.
Jon Hanna
2010-08-09 13:22:56
+1
A:
Exactly the same way that you do arithmetic with the digits 0-9. You do not have to borrow someone elses fingers when you make change for a twenty. The big integer class uses 32 bit or 64 bit integers in pretty much the same way you use digits. This is oversimplifying quite a bit, particularly as numbers get large
deinst
2010-08-09 03:06:58
Actually, I don't think that really over-simplifies it at all, barring optimisations. Any more detailed than that would have to get into a full-blown description of the entire implementation to be any more useful.
Jon Hanna
2010-08-09 03:26:59
@Jon The optimizations, particularly for multiplication and division take us away from the schoolbook algorithms.
deinst
2010-08-09 11:39:15
Exactly. It's a blog-post at shortest, an article to do it any real justice, and probably at least a chapter to be really adequte!
Jon Hanna
2010-08-09 13:20:38
+3
A:
BigInteger uses Arbitrary Precision Mathematics.
In computer science, arbitrary-precision arithmetic is a technique whereby calculations are performed on numbers whose digits of precision are limited only by the available memory of the host system.
Use it only when you need to work with very large numbers:
Arbitrary precision is used in applications where the speed of arithmetic is not a limiting factor, or where precise results with very large numbers are required.
Dolph
2010-08-09 03:09:57
+2
A:
Internally, the BigInteger type is implemented as an array of unsigned integers (uint32[] in c#) and another field that specifies the sign.
The array gives the type the ability to store such large numbers and the methods and operators hide away the details of dealing with the complicated structure making it easy to use.
GiddyUpHorsey
2010-08-09 03:11:44
+1
A:
Some words about BigInteger structure
BigInteger is structure by its nature. It has bunch of static methods that let you perform different mathematical operations on BigIntegers. There are also many operators and type conversions defined for BigInteger so you can use BigIntegers like usual integers. Take look at the BigInteger members documentation.
From this blog
I would also read as the above author suggests the MSDN documentation.
David Basarab
2010-08-09 03:12:33