Category : Science and Education
Archive   : LONGMATH.ZIP
Filename : LONGMATH.DOC

Arithmetic on Your PC
(BYTE Magazine March 1985 by Peter Rice)
(Corrected in BYTE Magazine May 1986)

LONGMATH.BAS contains all four arithmetic algorithms that let you
circumvent the floating-point decimal limitation of the IBM PC. The
program takes 12 seconds to multiply two 20-digitnumbers and 3 minutes,
55 seconds to divide a 160-digit number by a 40-digit number.

A number is a string of digits; addition and subtraction are
performed digit by digit, by carrying and borrowing. A digit can be
relative to any base, making it possible to create programs designed
to take advantage of the architecture of a specific computer. In this
instance, base 10 is used, so a digit is a number between 0 and 9.
Multiplication, with partial products running down the page, is not
the easiest way to get the job done on a computer, but it is not far
from the best method. Long division is just as complicated when done
by computer as it is on paper. You (or the computer) have to do some
guessing (try out a quotient and change it if it is too big). A couple
of programming tricks shorten the work, but little is changed from the
old paper-and-pencil method.

If you check LONGMATH.BAS, line 1040, you will see that a number
ió reaä intï á strinç variablå witè eacè digiô recordeä aó á character.
Because arithmetic can't be done with characters directly, the string
is converted to an array in which the zeroth value is the units digit,
the first value is the tens digit, the second value is the hundreds
digit, etc. Using notation, X(7) is the digit in the seventh place
(the 1 in 10,000,000). The last element of the array is the largest
place value in your number. (This information makes it possible to
run FOR ...NEXT loops only as long as they have nonzero values to work
with, a great savings in time.) For example, the number 44,098 would
be represented as X(0)=8, X(1)=9, X(2)=0, X(3)=4, X(4)=4, and X(200)=
4. All other array values are 0.

To add two numbers, the digits are added by columns. For 34,456
+ 83,509, the first sum is 6 + 9 = 15. The 5 is recorded (put in the
zeroth place), and the 1 is carried to the next sum: 5 + 0 + 1 = 6.
The 6 is put away in the first place, and a 0 is carried to the next
sum. The process is repeated from right to left until the end of both
numbers is reached. The program starts by finding the number of digits
in the larger number (line 10010). In this example, it's 83,509 (five
digits; four place values). The loop i lines 10020 to 10050 calculates
and carries. Line 10060 checks to see if a 1 was carried on the last
addition and, if so, sets the length of the answer.

Subtraction is almost as simple for the program. When a
subtraction results in a negative value, a 1 is borrowed from the next
place. (Borrowing is the reverse of carrying. A 1 is subtracted from
the next place instead of being added to it.) Only one problem can
occur: subtraction can result in a negative number. The program checks
to see if the result is negative by looking at the borrow on the last
subtraction. If there was one, that digit is negative and tells the
program that the result is negative. This is done by lines 11020 to
11060. The next line strips zeros from the difference.
Š


The multiplication algorithm involves multiplying digits and
putting the results in the right place. (The place of the result is
the sum of the place values of the numbers being multiplied.) For
example, multiply 78 and 105. The first step is 5 x 8 = 40, which
belongs in the zeroth place because 5 and 8 are each in the zeroth
place in their respective numbers, 0 + 0 = 0; followed by 5 x 7 = 35,
which belongs in the first place because 5 is in the zeroth place and
7 is in the first place, 0 + 1 = 1; then 1 x 8 = 8 goes in the second
place, and 1 x 7 = 7 goes in the third place. The other products are
0. When two numbers go into the same place, they are added; therefore,
the product above is 7, 8, 35, 40 with the places separated by commas.
Of course, we don't write 783540 since the 35 and 40 are bigger than
10. Rather, the tens digit of each of these numbers is carried into
the next place: 7, 8 + 3, 5 + 4, 0 = 7, 11, 9, 0 = 7 + 1, 1, 9, 0 =
8190. (Carrying occurs when a product is greater than 10; the tens
digit is carried to the next place.) The loop in lines 12010 to 12080
performs this; it takes pairs of digits, finds the product, adds that
to the digit already in the answer at the proper place and, if the
result is greater than 10, divides by 10 and puts the remainder back
into the result, and carries the quotient to the next higher place.
(The reverse slash, \ , is the integer divide function. It gives the
integer quotient only, dropping the fractional part. MOD is the
function that calculates only the fractional part -- the remainder.)
This algorithm differs from the manual method only in that, instead of
writing down partial products and adding at the end, you keep a running
total.

The division algorithm requires a preface. Calculating on paper,
you divide the divisor into the first few digits of the dividend,
arriving at a single-digit result. Then you multiply the divisor by
this digit and subtract from the dividend (in the right place).
Choosing this digit requires some care. Looking at the first digits
of the divisor and dividend is some help, but usually you try it out,
decrease the integer by one, and try again. One theorem says that,
in certain circumstances, the result of dividing the first one or two
digits of the dividend by the first digit of the divisor is never more
than two units too big. These circumstances can be manufactured by
multiplying the divisor and dividend by the right number. The
calculation of this number D and the multiplication by it take place
in lines 13140 to 13330.

C, the digit in the quotient, is calculated in line 13360 (or
13350). Another refinement is used in line 13370: C is checked to see
if it is too large when considered as the quotient of the first three
digits of the dividend by the first two digits of the divisor. If it
passes this test, then you can be sure that it is not more than one
unit too big. If it does not pass this test, decrease it (line 13380)
and try again.




Š The actual division -- multiplication by C and subtraction --
takes place in lines 13400 to 13510. When that is finished, you check
to see if C was one unit too large (lien 13520) and correct C and the
dividend (lines 13530 to 13570). The final steps are to set the length
of the quotient (13610) and the length of the remainder (13620 to
13660) and divide the remainder by D. It is not necessary to divide
the quotient by D because X/Y = Q with remainder R, then X = QY + R.
Multiply by D: DX = QDY + DR, so DX/DY = Q with remainder DR.

Note: A letter in BYTE May 1986 corrected line 11070, added line
13365, deleted line 13640 and changed line 13650 from the original
prograí listinç iî BYTÅ Marcè 1985® Theså changeó correcô thå problems
of a number divided by itself (25/25) and a number divided by a single-
digit divisor (25/5), both of which resulted in an illegal function
calls. These changes work in all situations of non-negative integers,
excluding a divisor of zero.