If the aim is to learn how to write tight code from number theory, then i found using a rexx wrapper around a hamster is the way to go. The hamster is a little program like 'factor' or the UBASIC factor routines on this. You don't have to modify this code much, largely to get it to print some extra string on the output line.
The REXX code isn't run much: its function in life is to create a command line for the hamster to chew on. This is usually something like a command line of a search-string and a very large number.
Code: Select all
[D:\]aj 12 96
factorising 12A96 = 34182189187166851926484583071088641
first trying brute force division by small primes
PRIME FACTOR 7489
now trying 1000 iterations of brent's method
PRIME FACTOR 3122881
PRIME FACTOR 1461573322938242802306049
The hamster here is a win32 and os2 factor program.
Code: Select all
factor -f <formula>
e.g. factor 999999999999999999999999999999999999999999999999999997
or factor -f 10#100-19
To suppress the commentary, use flag -s
To input from a file, use flag -i <filename>
To output to a file, use flag -o <filename>
e.g. factor -f 10#100-7 -s -o factors.dat
Freeware from Shamus Software, Dublin, Ireland
Full C source code and MIRACL multiprecision library available
Email to email@example.com for details
Web page http://indigo.ie/~mscott
Source code from ftp://ftp.compapp.dcu.ie/pub/crypto/miracl.zip
I use it fromhttp://home.netcom.com/%7Ejrhowell49/math/index.html
which is updated.
The optimisation comes from feeding the hamster correctly. A spot of optimisation, over a period of three or so days, reduced the running time of a number of projects by months.
Another good trick in the rexx program is to put the program into shutdown mode, where a signal is raised by creating a file, and the batch run ends at the end of the signal. The last good record is kept updated, so it starts with the first undone one on power failure etc.