NUMBER THEORY
 |
|
When I moved to the TI-92, I found it a pretty complete package; I mean, it covers quite a bit from quite a few classes. There were a few things that weren't implemented, but those gaps were soon patched by ELEM and ADV, two groups of programs released by Soft Warehouse, Inc., designers of Derive as well as many of the 92's symbolic manipulation routines.
There still were some things my 92 couldn't do, and I was bothered; it couldn't do a lot of number theory applications. The built-in factoring routine was decent, but it left residuals > 65521, meaning that using it as a primality test wasn't that great an idea.
While scouring the old GRAPH-TI program archives I came across some real jewels for the TI-85; unfortunately, since the 85 could only handle relatively small integers, the number theory programs I found weren't as useful as I would have liked. I set about to change that.
After converting several of the 85 programs, I stumbled across an excellent package called UBASIC - an advanced version of BASIC featuring extended precision arithmetic and integers with up to 2600 digits (over 4 x as many as the 92!). I also downloaded MALM, a pack of number theoretical programs for UBASIC. I set about converting some of these as well. The programs below are the fruits of my labor.
There are two places to download the program group from; one of them is here (the recommended distribution site) and the other is ticalc.org. An important difference is that the version distributed here is distributed as a ZIP whereas the ticalc.org version is a UUE file.
| psprime(n) | Returns true or false depending on whether or not 2^n=2 (mod n); if it passes, the number is probably prime -- if it doesn't, the number is composite. The first composite to pass is 341. |
| mprime(n, a) | If n is an integer <341 trillion, outputs with certainty a number's primality; if n >= ~ 341 trillion, checks to see if a number is a strong SPRP for all primes p | 1 < p < a. A VERY strong test -- if it passes through 19, the odds that your number is composite are extraordinarily small. Note that the second parameter must be <= 97 (*). |
prpcheck(a,b)| Checks to see if a is a b-PRP, or if b^a=b (mod a). Large numbers which pass this have only a small chance of being composite (see Probable-primes: How Probable? for an idea of just how small). |
|
| modpwr(a,b,n) | Returns a^b (mod n), where a^b would normally overflow or be an integer with more than 614 digits. |
| polpm1(n,b,u) | Attempts to factor n using base b (where u is the upper bound) by Pollard's p-1 method of factorization. Quite useful! |
| rho(n, a, ub) | Attempts to factor n by Pollard's Rho method into numbers that may or may not be prime. Make a larger or smaller if n grows larger or smaller, respectively. For numbers around 9-10 digits, a good a is about 10. The variable ub contains the upper bound, which may have to be adjusted depending on how difficult a number is to factor. Try 1000 for a starting value; bigger values will enable you to factor 'tougher' numbers, but will take more time. |
| isqrt(n) | Returns int(sqrt(n)) by getting the first 14 or so digits by int(sqrt(n)) and then extracting the remaining digits by Newton's method. MUCH faster than the original algorithm using bisection. |
| hprime() | Front end/help for psprime and mprime. |
Other files included:
| sumult(a,b,n) | Returns a*b (mod n) by brute force. I may implement a more elegant algorithm in the future... |
| primlist | A list of the first 25 primes (the primes between 1 and 100). You can extend the list yourself -- a program to do so may be available in the next version. |
* By extending the list, you can use a larger second parameter in mprime.
![[TI-92 number theory screen shot 1]](ex1.gif)
![[TI-92 number theory screen shot 2]](ex2.gif)
Special thanks are due to Yuji Kida, author of the excellent UBASIC programming language, Donald E.G. Malm, author of a pack of terrific UBASIC number theory programs and the authors (Mark Janeba, et. al) of the original TI-85 programs.
I'd also like to thank the people of #calc-ti for their support, friendly advice and general knowledge. If you're interested, #calc-ti is on EfNet -- irc.portal.com (6662) is one of many EfNet IRC servers.
Thanks for trying these programs!