How to implement long division for enormous numbers (bignums)

views:

answers:

+4 Q:

How to implement long division for enormous numbers (bignums)

Hi, 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

+2 A:

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.

GregS 2010-07-08 00:06:53

+1 for Knuth reference.

Anton Tykhyy 2010-07-08 00:09:23

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

Chris 2010-07-08 00:24:54

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

Chris 2010-07-08 00:32:36

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

GregS 2010-07-08 00:43:05

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

Chris 2010-07-08 23:38:04

Some links on the subject :
Basic Arithmetic with Infinite Integers
Large Numbers
Multiplying Large Numbers with Karatsuba`s Algorithm - Apply What We Have Just Learned
Calculating π to any arbitrarily large numbers
Calculating pi to one million decimal places

lsalamon 2010-07-08 00:52:49

First and second article only do add/subtract, however i found another article by the second writer specifically about division:http://www.devarticles.com/c/a/Development-Cycles/Division-of-Large-Numbers/

Chris 2010-07-08 01:26:27

ansaurus

tags:

views:

answers:

How to implement long division for enormous numbers (bignums)

related questions