- The TI-85 has
a "word size" for its real number type: 14 digits, of which only
12 are shown. On this page we see how to use strings and lists to
get around this limitation.

- The key to following program converts a string
of digits to a list of real numbers:

- How does the above algorithm
work? Well, after prompting the user to input a string, the

Going Backwards: Converting a List to String

- Consider the list of
digits to represent an array of coefficients of powers of 10:

So far we have a way of entering in a number with more than 14 digits. Assuming we have procedures for operating on these, we'll then need some way to output the result. The following algorithm makes use of the way the "+" is overloaded on the '85 so that strings can be concatenated.

__Program L2ST__

`:" "->ST2 //
Create and initialize string``:1->B``:While C(B)==0
// Skip over leading zeroes.``: B+1->B``:End``:For (I,1,dimL C)
// From 1st non-zero element to end of C``: If C(I)==1
// Handle each digit case separately:``: ST2+"1"->ST2``: If C(I)==2``: ST2+"2"->ST2``: If C(I)==3``: ST2+"3"->ST2``: If C(I)==4``: ST2+"4"->ST2``: If C(I)==5``: ST2+"5"->ST2``: If C(I)==6``: ST2+"6"->ST2``: If C(I)==7``: ST2+"7"->ST2``: If C(I)==8``: ST2+"8"->ST2``: If C(I)==9``: ST2+"9"->ST2``: If C(I)==0``: ST2+"0"->ST2``:End
// End the For loop``:sub(ST2,2,lngth ST2-1)
// Print the number string`

The**
While **loop in the beginning
serves to advance the current position in the list (

- Ok, we know how to get
large numbers in and out of the calculator. How do we perform operations
on the lists?

Consider addition first.
If we want to add ** [1
3 1 2 4 1]** and

- We want to "carry" this number to

- The algorithm for converting
a number of the form

`:For(I,dimL C,2,(-)1)``:(C(I)-mod(C(I),10))/10+C(I-1)->C(I-1)``:mod(C(I),10)->C(I)``:End`

Load ** [3
10 4 4 5 3]** into

- 1. What if we need to carry from the most significant
place value? You can't just redimension the same
list to have one more digit, since the new position would

be on the wrong end of the list.

2. What if the two numbers don't have the same number of digits?

First work out the special
case when both numbers have the same number of digits -- say, *n*.
Dimension a list C with *n+1* elements to hold the sum and add i-th
elements of addend lists to the i+1-st position in C. This leaves room
for a carry in the first position, if it's needed. For example, with addend
lists: ** [8 3 2 4 2] **and

For the more complicated situation
where one addend has more digits than the other, irst dimension a list
of seven elements. After this we'd add put the second number in the last
six positions to have**
[ 0 3 2 1 4 5 7] **and then
add the first number to the final positions, to get

- Suppose we want to compute
3490529510847650949147849619903898133417764638493387843990820577 * 32769132993266709549961988190834461413177642967992942539798288533?

Most humans are understandably reluctant to perform this computation by hand. When multiplied out they produce a famous number, RSA-129: so named because it was part of an RSA challenge. (Mark Janeba has an excellent article on the factorization of RSA-129, if you're interested.) The challenged issued was to factor the 129 digit number:

- 114381625757888867669235779976146612010218~

296721242362562561842935706935245733897830~

597123563958705058989075147599290026879543541

Representing the two factors as 64 and 65 digit lists, we have:

Ignoring the need to carry, the algorithm to we want to find these coefficients is just the algorithm for finding the coefficients of a product of polynomials. Then we can apply a Carry algorithm to finish.

The formula for the *k*th
coefficient is ** sum(a_{i}*b_{j,}such
that i+j=k)**. Where

Program =MULT

`:0->C //Clear
out C``:ClLCD``:Disp "Long Integer"``:Disp "Multiplication"``:Disp ""``:InpST ST``:ST2L``:NL->A //
Input first factor to list A``:InpST ST``:ST2L``:NL->B //
Input second factor to list B``:dimL A+dimL B->dimL C //
The digits in product is sum of factor's digits.``:For(I,1,dimL A)``: For(J,1,dimL B)
// Each product is computed once``: C(I+J)+A(I)*B(J)->C(I+J)
// and added to proper coefficient.``: End``:End``:Carry``:L2ST`

- Can we use these techniques
to compute

To exponentiate a positive
integer *B* to an integral exponent, *N*, we could apply the
multiplication algorithm described above *N-1* times, and dimension
the product to the appropriate size, but this assumes that *B *and
*N *may need to be more than *14 *digits. Now, the number
of digits in *B ^{N }*is

Thus, we can safely
assume that both B and N are ordinary TI reals with less than 15 digits.
It's then a simple matter to dimension the list for the *B ^{N}*
number using

`:ClLCD``:0->C //
Initialize C``:Disp "Compute B^N"``:Disp ""``:Input B //
A is the base of the exponential.``:Input N //
B is the exponent.``:iPart (N*log N)+1->dimL
C //Note that 1+log(A^B) gives decimal
digits.``:B->C(dimL C) //
The (dimL C) is needed to keep the list type.``:For(I,1,N-1) //
Multiply A (already in C) by A, B-1 times.``: If max(C)*A>2E13
// If the largest number in C*A is
greater than 2*10 ^{13}`

`[0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 2]``[0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 4]``[0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 8]`

. . . Keep multiplying by**
2 **until

. . . then do a

. . . and multiply by

the list is

. . . which after a

. . . and after the final

The TI-85 handles the next 3 Mersenne
primes easily: `2 ^{89}-1,
2^{107}-1, 2^{127}-1`

In 1952, Robinson discovered the next 5 Mersenne primes:

Why wait until the list elements are large to do the carry?

You can use the built-in factorial routine ([2nd] [x] [F2] [F1]) to compute factorials, but starting with 20! we loose precision. As the screen shot shows, we can get 13 accurate digits by subtracting off the leading digits, but the 14th is suspect since the 15th digit is missing and there may have been some round off.

Using the list type to compute larger factorials is quite simple, though you may wonder how we can compute log(N!), in the process of computing N!. There are two good reasons making this possible. One is that we don't need an exact value for log(N!) since we end up just taking its integer part, and the second is that log(N!) = sum(logk, k, 2, N).

`:0->C``:ClLCD``:Disp "N FACTORIAL"``:Disp ""``:Input N //
N is an integer less than 14 decimal digits.``:iPart (log (N!))+1->dimL
C // Formula for number of decimal
digits.``:N->C(dimL C) //
Enter N as the last entry in list C.``:For(K,N-1,2,-1) //
Be sure to enter [(-)] for negative``: C*K->C``: If max(C)*K>2E13``: Then``: CARRY``: End``:End``:CARRY``:L2ST`

- Here's a routine to do subtraction of large integers.

`:ClLCD``:0->C``:Disp "SUBTRACTION"``:Disp ""``:InpST ST``:ST2L
// Get AB and AC to subtract AC from AB``:NL->AB``:InpST ST``:ST2L``:NL->AC``:dimL AB->dimL C //
Create C to hold the difference``:For(P,dimL AB,dimL AB-dimL
AC+1,-1) // Start at the right end``: If AB(P)>=AC(P-dimL AB
+ dimL AC) // Check to see if
you need to borrow``: Then``: AB(P)-AC(P-dimL
AB+dimL AC)->C(P)``: Else //
Borrow``: 1->K``: While AB(P-K)==0
// Look for the first non-zero value
to borrow from.``: 9->AB(P-K)``: K+1->K``: End``: AB(P-K)-1->AB(P-K)``: AB(P)-AC(P-dimL
AB+dimL AC)+10->C(P)``: End``:End``:For(P,dimL AB-dimL AC,1,-1)``: AB(P)->C(P) //
Copy the rest of the digits we won't subtract from.``:End``:L2ST`

__Division__

- So you want to implement
the division algorithm to produce a quotient and a remainder when two large
integers (AB/AC) are divided? This is a bit longer than the others
and required using more of the design process - though I imagine someone
could reduce the code length here with a little ingenuity.

The key elements of the subtraction routine above0 are used to do repeated subtraction with borrowing. There are tests to see if subtraction is required and then an index, I, keeps track of how many times the divisor is subtracted in a specific place value, P, which is in the list of quotient digits, C. When all that can be subtracted is taken out, I is the numeral written to that place value in the quotient. When the procedure is finished, the remainder is in AB.