The Texas Instruments calculators sells a line of programmable hand calculators with set of functions and a simple programming language which is, at a simple level, compatible between calculator models. These programs will run on the TI-86/85/83/82/72.
The TI-8x series of calculators runs on a variant of the old Zilog Z80 processor and supports computations with integers as large as 246. (The display will not display integers this large, converting them to floating point for display, but some simple experiments seems to show that the internal representation is still faithful.) This means that, taking into account multiplication and modular reduction, the largest numbers which can be used in these algorithms is 223=8388608.
These programs can be written and saved on the calculator from PRGM mode, entered by typing the [PRGM] key. The basic functions are entered into a program by finding them in the menu structure, usually in MATH mode. On the TI-85/86 the functions may also be entered by typing their names in directly (case is not important).
The basic arithmetic operations, +, -, /, are
available from the keyboard. The factorial operation, n!,
is available from the [PROB] submenu of the
[MATH] menu.
The TI86/85 have a modular reduction operator. This can either
be typed in directly from the keyboard: MOD(37,5) (case is
not important), or found in the [NUM] submenu of the
[MATH] menu. For the other calculators the same effect as
MOD(n,m) can be gotten by computing n-m*int(n/m)
if m is positive.
GCD is a built-in function for all but the TI-82. The GCD function
found in the [MISC] submenu of the [MATH] menu.
An extended GCD algorithm can be implemented with the following program.
Input "N ",N
Input "M ",M
[1,0]->K
[0,1]->L
Repeat (N=0)
int(M/N)->Q
M-N*int(M/N)->M
L-Q*K->L
If (M==0)
Goto XGCDEnd
int (N/M)->Q
N-M*int(N/M)->N
K-Q*L->K
End
M->N
L->K
Lbl XGCDEnd
Disp N,K
Users of the TI-82 may use the following program to compute the basic GCD program. This is written so it can be used as a subroutine in other programs by placing the operands in x and y and expecting the result in x.
Repeat (Y=0)
X-Y*int(X/Y)->X
If (X==0)
Y->X
Return
End
Y-X*int(Y/X)->Y
End
Return
The Russian Peasant method for modular exponentiation can be implemented with the following program:
Input "Modulus ",M
Input "Element ",E
Input "Power ",P
1->A
Repeat (P=0)
If ((P-2*int(P/2))=1)
E*A-M*int(E*A/M)->A
E^2-M*int(E^2/M)->E
iPart (P/2)->P
End
Disp A
The Sieve of Eratosthenes for finding successive primes can be implemented with the following program. The program sieves over the first 255 odd numbers, printing out the primes.
255 -> L
L -> dim(L1)
Fill(0,L1)
For(I,1,L)
If (L1(I)==0)
Then
Disp 2*I+1
For(J,I,L,2*I+1)
1 -> L1(J)
End
End
End
DelVar(L1)
The Pollard Rho method for factorization can be implemented with the following program:
Input "Number ",M
2->R
5->S
1->F
While (F=1)
R^2+1-M*int((R^2+1)/M)->R
S^2+1-M*int((S^2+1)/M)->S
S^2+1-M*int((S^2+1)/M)->S
gcd(abs(R-S),M)->F
End
Disp F
The order of an integer in the group of units mod some other integer (ie the smallest exponent e such that be(mod N)=1) can be computed with the following program:
Input "Modulus ",M
Input "Element ",E
1 -> O
ELT -> A
Repeat (A=1)
E*A-M*int(E*A/M) -> A
ORD+1 -> ORD
End
Disp ORD