- General
- Basic Operations
- GCD
- Exponentiation - PowMod
- Finding Primes - The Sieve of Eratosthenes
- Factoring - Pollard Rho
- Computing the Order of Integers
- Commands

[Prev] [TI Calc Intro] [Next]

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
2^{46}. (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 2^{23}=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(L_{1})

Fill(0,L_{1})

For(I,1,L)

If (L_{1}(I)==0)

Then

Disp 2*I+1

For(J,I,L,2*I+1)

1 -> L_{1}(J)

End

End

End

DelVar(L_{1})

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 `b`^{e}(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

**abs**(n) - Compute the absolute value of a number (or the elements of a list or matrix). (TI-86/85/83/82/73)- n
**!**- Compute n factorial. [Found in the STAT menu] (TI-86/85/83/82/73) **gcd**(n,m) - Compute the gcd of two numbers. (TI-86/85/83/73, but not TI-82)**int**(n) - Compute the largest integer less than n. (TI-86/85/83/82/73)**iPart**(n) - Compute the integer part of a real number. For positive numbers this will be positive and for negative numbers this will be negative. For positive numbers this will have the same value as int. (TI-86/85/83/82/73)**mod**(n,m) - Compute the value of n(mod m), the smallest postive number a such that a-n is divisible by m. (TI-86/85, but not TI-83/82/73)

Robert Campbell Last modified: Oct 6, 2002