How to implement long division for enormous numbers (bignums)

Question

I'm trying to implement long division for bignums. I can't use a library like GMP unfortunately due to the limitations of embedded programming. Besides, i want the intellectual exercise of learning how to implement it. So far i've got addition and multiplication done using any-length arrays of bytes (so each byte is like a base-256 digit).

I'm just trying to get started on implementing division / modulus and i want to know where to start? I've found lots of highly-optimised (aka unreadable) code on the net, which doesn't help me, and i've found lots of highly-technical mathematical whitepapers from which I can't bridge the gap between theory and implementation.

If someone could recommend a popular algorithm, and point me to a simple to understand explanation of it that leans towards implmenentation, that'd be fantastic.

-edit: I need algorithms which work when the dividend is ~4000bits, and divisor is ~2000bits

-edit: Will this algorithm work with base-256 ? http://courses.cs.vt.edu/~cs1104/BuildingBlocks/divide.030.html

-edit: Is this the algorithm (newton division) i should really be using? http://en.wikipedia.org/wiki/Division_(digital)#Newton.E2.80.93Raphson_division

Alluvium

I found this, but i'm not sure it'll be a good algorithm for numbers > 2048 bits? #2525672 – Alluvium

I also found this paper, would it be a good algorithm for me to start with? brinch-hansen.net/papers/1994b.pdf – Alluvium

Answer 1

If you want to learn, then start with the pencil and paper method you used in elementary school. Believe it or not, that is essentially the same O(n^2) algorithm that is used in most bignum libraries for numbers that are in the range you are looking for. The tricky first step is called "quotient estimation", and that will probably be the hardest to understand. Once you understand that, the rest should come easy.

A good reference is Knuth's "Seminumerical Algorithms". He has many discussions about different ways to do quotient estimation both in the text and in the exercises. That book has chapters devoted to bignum implementations.

Brainwash

The pencil and paper method only seems to work if the divisor is one or two digits long, from what i can find on the net – Alluvium

Hang on, is this the same as the shift/subtract method here? courses.cs.vt.edu/~cs1104/BuildingBlocks/divide.030.html – Alluvium

You'll have to generalize the paper-and-pencil method. – Brainwash

In the end, i used the shift and subtract method: courses.cs.vt.edu/~cs1104/BuildingBlocks/divide.030.html – Alluvium

Answer 2

This question is over 2 years old, but for this size numbers you can look at the OpenSSL source code. It does RSA with this size numbers so has lots of math routines optimized for 1000 to 4000 bit numbers.

Internship

Answer 3

Are you using the void Four1(long double[],int,int) in your code and then convolving and then doing a inverse transform well I got multiplication to work but when I tried to do division the same way it spat out one result then quit so I cannot help but if you have the tome called "Numeric Recipes in C++" go to near the end and you will find what you are looking for actually it starts on Page 916 to 926.

Mathura