Program:   LONGOPS

Author:    Paul Pollack  (paulp@televault.com)

Date:      June 19, 1996

Synopsis:  LONGOPS performs a series of operations and returns the

	   exact result where precision would normally be lost.



Instructions:



If you've uudecoded the listing below, load up the Graph-Link

software/LINK85 and ungroup LONGOPS; you should now have L2SD, LONGC,

MULT, PWR, and FCTRL.



LONGC and L2SD are "subroutines" necessary for the successful running of

PWR, FACT and MULT; MULT has changed since version 1.0 and now takes

full advantage of LONGC and L2SD, saving about 700 bytes.



Run either PWR, MULT, or FCTRL; you should be prompted for a number. If

you're running MULT, enter the number using as many digits as you'd like-

it's stored as a string and all the computations are done using lists,

so you could theoretically work with numbers hundreds of digits long. If

you're working with PWR or FCTRL you'll have to use numbers that the

TI can normally work with. In PWR, a (in a^b) must be less than about

(4.473e6). How long your results can be depends on the amount of free

memory in your calculator.



===



Bugs/features: The programs above were meant for figuring out problems

which would be too tedious to work out by hand. Ironically, in their

design, the simple problems are either not done, or done incorrectly. MULT

will not multiply two one digit numbers; PWR does not handle the trivial

cases 1^x, 0^x or x^0 and FCTRL doesn't do 0!



===



Limitations: Many of the limitations (such as the limit on the number of

digits the two numbers you multiply can be) vary depending on the

calculator's memory. Others do not -- a^b in PWR as well as n! in FCTRL

must not exceed 1e999.



===



Algorithm (for those who care): I simulate long integers by storing

them internally as a list of digits.



Let me cover the algorithm used in MULT first:  the two numbers

the user inputs are translated from strings into lists by a rather

inefficent (but working) algorithm. I simply go through the whole string,

check each "number" in the string to see what digit it corresponds to and

then place it in the list.



Say my two lists look like this (a very simple case, admittedly...):



[ 1 1 ] [ 1 3 ]



I treat the two lists as polynomials -- multiplying using Richard Homard's

excellent algorithm, I get another list [ 1 4 3 ]; because all the numbers

in the list are single digits, I've got lucky and 143 is my final answer. I

could get unlucky, though, and get a product like [ 1 26 21 12 31 ]. Since

I'm evaluating the polynomial at 10, I can implement a simple algorithm,

going from right to left that takes the number (div 10), adds it to the

number in front and then replaces the number by the number mod 10. I go

through the whole list until I finish... This is the basis for LONGC, which

MULT (in this version) uses.



Continuing with [ 1 26 21 12 31 ], I get:



[ 1 26 21 15 1], then

[ 1 26 22 5 1], then

[ 1 28 2 5 1], then

[ 3 8 2 5 1]



Since all my numbers are single digits, 38251 is the answer I'm looking

for -- all I have to do is change the number from a list to a string and

I'm done -- this is what L2SD (List 2 String and Display) does, but that

came long after MULT as well.



The algorithm used in PWR and FCTRL is similar: they both rely on the fact

that to multiply a number stored this way, all I have to do is multiply

each of its elements by the desired quantity and then use the above list

cleaning up algorithm on it. For example, to multiply 3921 by 22, I do

something like this:



[ 3 9 2 1 ] * 22=

[ 66 198 44 22 ];

[ 66 198 46 2 ];

[ 66 202 6 2];

[ 86 2 6 2];

[ 8 6 2 6 2]



I then just have to run L2SD and I have my number! PWR just does this

a number of times: to calculate 8 cubed, all I do is find out how many

digits 8^3 has by truncating the log of the answer and adding one.

Note that my reasoning isn't circular [I can already hear people saying

"How's he taking the log of the answer when he doesn't know it!?"]--

I'm taking the log of the answer the calculator gets normally, which in

many cases will be missing significant digits. Anyway, here goes:



[ 0 0 8 ] ( I create a list with 3 (or more) places since 8^3 has 3 digits.

	    I then place the number in the last spot and multiply by 8

	    the remaining (power-1) times -- in this case, 2. )

[ 0 0 64] ( *8 and then LONGC here to clean it up )

[ 0 6 4 ] ( cleaned up output )

[ 0 48 32 ] ( multiplied by 8 again )

[ 5 1 2 ] ( cleaned up )



FCTRL uses a similar process which you should be able to guess by now...

you're also probably wondering why I clean-up the output after each time.

I was wondering that as well, and that's why I don't. In the programs below,

I only clean up the list when the numbers in them good have significant

digits lost when performing the multiplication.



To understand this, consider below:



Say I was working with a stupid machine that could only handle 4 digits

in a list and I want to take 8^5. I have



[ 0 0 0 0 8 ] -->

[ 0 0 0 0 64 ]

[ 0 0 0 0 512 ]

[ 0 0 0 0 4096 ] -- Ahhhh! I can't go on any further because

		    if I multiply by 8 again, I'm just going to lose

		    significant digits! I just clean up the list right now

		    to prevent it...

[ 0 4 0 9 6 ]

[ 0 32 0 72 48 ]

(after cleaning up): [ 3 2 7 6 8 ]



This does bring some limitations into it; since the TI-85 only integers

up to about 2e13 without loss of significant digits, the base of the

number I'm multiplying by can't be any bigger than its (2e13's) square root

without risking some danger -- hence the 4.2e6 limitation. Hence, to

make 2^300 execute faster, you could use 2^20 as your number and 15 as

your power, but you couldn't use 2^30 as your number with 10 as your power.



That about wraps it up. Drop me a note with any questions or comments.



===



If you find a bug in any of these programs, I'll issue a new version

immediately. Feel free to write me or use any of my routines in a program

of your own -- all I would like is an e-mail message telling me of

the project and just a small mention in your documentation. BTW, DOS

versions of FCTRL and PWR are available and handle numbers up to approx.

16200 digits long. If you're interested, just drop me a message with

the subject: LONGOPS DOS request, or something of that nature.



Thanks!



-- Paul Pollack

paulp@televault.com