Dec 062017

Perform math on numbers of 100 digits or more. BASIC source. | |||
---|---|---|---|

File Name | File Size | Zip Size | Zip Type |

LONGMATH.BAS | 4915 | 1638 | deflated |

LONGMATH.DOC | 7552 | 3129 | deflated |

# Download File LONGMATH.ZIP Here

## Contents of the LONGMATH.DOC file

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.

(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.

December 6, 2017
Add comments