Integer Division of Very Large numbers

Last Up date: 2005 October 17
Recent changes: Update for www.laforth.com from: 2003 November 21

Historically, evaluating e and/or Pi and generating Prime Numbers were some of the first tasks to be done on early digital computer. I suspect at one time or another everyone here has programed one or more of these. I first calculated e to a thousand digits in 1961 on a computer built at Iowa State University. (Vacuum tubes, and about 100 microseconds for a 40 bit add.) Typically e is calculated simply by adding the reciprocal factorials.

In August 1986 I did a program to evaluate the constant e up to 150,000 decimal places on an 8088 based IBM PC. Using factorials up to about 37,592! It might surprise some to know it can be done never using a divisor greater than 16 bits; but that is another talk.

8086 Unsigned integer divide with a single word divisor, is a simple loop

;BX=the divisor, CX=the number of words in the numerator, and DX=0
;SI and DI point to the high order numerator words.

; The working loop is just:

divs:   lodsw           ;get the numerator word
        div     bx      ;AX=quot, DX=rem of (DX:AX)/BX
        stosw
        loop    divs    ;DIVide Step

;Multiple word quotient has replaced the Numerator and
; the remainder is in DX.

The conversion from binary to decimal involves repeatedly dividing or multiplying by ten. (One can reduce the number of divides or multiplies, by first converting to base 10,000.)


Variable Precision Divides with "Long Divisors"

An interesting challenge is doing variable precision binary integer "long divides" where the divisor can be several hundred 16 bit words long. I restricted myself to the Intel 8088 instruction set.

I do this very much like the grade school "long division", but with the "digits" being bytes. (Think in number system base 256.) This works fine, but in grade school decimal arithmetic we guess what the next quotient digit should be. How does a program make an intelligent guess? In pure binary it is easy. In base 10 it is a bit of a struggle. In base 256 we have to do better. We would like to "guess" the next quotient byte without error.

You can get a good guess at the next quotient byte with a machine divide of the high order word of the divisor into the high order word pair of the numerator. (Actually, I multiply by the reciprocal of the high order word of the divisor because a multiply is faster than a divide. Donald Knuth did not suggest this in his famous 3 volume set. ? It may be a mistake?) In ill conditioned cases I am sometimes off by two.

When I multiply by the quotient byte then subtract I would like to never have to check for it being too big or too small. Many times I thought I had it. But, sooner or later, there always turns up a "bad" example! Never ever having to correct with more than one add (if the quotient byte was too small) or one subtract (if the quotient was one too large) would make me happy.

I kept tweaking and rounding, several times I thought I had it, but eventually I had to leave in code which after a correcting add or subtract sometimes has to do another. I have never been so frustrated, and to this day I am not sure I could not improve getting the next quotient byte. I suspect: If I allowed myself to use a few 80386 instructions, I might make it happen. But I got tired.

To make sure I don't have undetected errors I put in the equivalent of "casting out nines" except doing it on binary words I check every divide by "casting out 65,535's". I have never been sure enough to remove that "checking" logic. It has been years since it caught any divide errors. The probability of it not detecting an error is certainly less than one in 65,535.


Contact me at:
My phone #'s
For comments call, or e-mail me. Go to My Home Page or TOP of this page.