The knowledge needed to create your own integer class?

Question

Having reached the brick wall with the lack of a .NET framework in the BigInteger class (for now), I decided that I would like to develop my own exercise (I understand that there are open source alternatives). What hoops do I need to jump to be able to develop this? Is there any special knowledge that I probably would not have?

change: side issue. What type of data would you use to represent numbers inside your new large integer class?

Answer 1

Arbitrary precision arithmetic ?

Edit:. To represent your numbers, you probably want to resize the array of integers.

Answer 2

I would refresh your basic math skills. When I wrote the Big Int class, I had to remember how to add, multiply and share manually, as in elementary school.

Next, if you are going to create a new class, I will try to follow the standards that have been configured for the Framework. Thus, it looks like any other .Net class.

I will follow TDD so that you know that your class works the way it was designed.

Answer 3

You need to have a very good understanding of number systems. You could choose to represent bignum in base 10 , base 2, or any base x . This choice will greatly affect the performance of your class. You must also select the algorithms you want to implement. In general, large libraries such as GMP, for example, choose an algorithm based on the size of the operands. There are many topics that you should know about, but in the end you should be sure that you cannot create something really interesting. As an educational topic, this is very valuable, but when producing something useful, it is not recommended to reinvent the wheel!

Answer 4

If you want to dive deep into math, you need to read Donald Knut .

Answer 5

.Net 3.5 has the BigInteger class, but it is localized inside the CLR. You can see the code using Reflector . Open System.Core.dll and look in the System.Numeric namespace. BigInteger is the only class in this namespace.

If you want to see the code for the F # BigInteger class, look in the [F # install folder] \ source \ fsharp \ FSharp.Core \ math \ z.fs folder.

Answer 6

Maybe studying an already implemented BigInteger class can help?

Answer 7

If you use elementary algorithms, your BigInts will not be suitable for very large integers, such as Mersenne Primes.

If this suits you, use a simple 32-bit int as the base data type. In this case, you need to process 64 results. If you don't care about speed at all, use some radix-10 base as the base, say 10000, which will be very easy to implement.

This is mainly because multiplication in a naive implementation has O (n ^ 2) runtimes. Advanced algorithms based on Fourier transforms have O (n (log (n)) runtimes, which requires some mathematical skills and knowledge.