Big/Giant number package

Giant Numbers in Forth

What is this?

There are two bignumber packages available here. The first is bignum.frt. It is completely written in Forth. Non-standard, but no problem for iForth. All algorithms are taken from Knuth's TAOCP. Although the multiplication method doesn't use modern tricks like Karatsuba and FFT, for numbers up to a few thousand bits it is certainly competitive with (if not faster than) GiantInt.

The second package is loaded by including factor.frt. It uses Perfectly Scientific's GiantInt package, which is written in "C". iForth accesses the code through the gint.dll. Glue routines, comparable to the ones needed for BLAS and NRC, are in gint.frt. The header file gint.h may allow you to use gint.dll in other contexts. The full code can be downloaded here. I have not ported it to Linux yet. That should be straight-forward though.

You will find that both bignum packages are heavily spiked with number theoretic functions.

I had hoped to get to the forefront of technology by incorporating GiantInt. It became clear while porting that technology has made vast progress since 1998 (last GiantInt release). My belief is now that up to maybe 100 digits gint.dll is OK, but not spectacular. For real heavy duty stuff it will be necessary to link to NFS or MPQS routines.

GiantInt Function overview

The standard +,-,*,/ and % operators. These work on two GIANTs or on a GIANT and a 16-bit number (gint.dll unfortunately uses short ints).
GCD in various flavors.
Modulus, exponentiation and shift for GIANTs, special cased for Mersenne and Fermat numbers.
Stack-like allocation and deallocation of GIANTs.
Elliptic curve routines (high-level variant of George Woltmans' Mersenne crusher)
A very fast prime test, bigprimeq.
Faculty (!) and squareroot functions (implemented in Forth)
Miller-Rabin prime test, also in high-level Forth.
Lucas-Lehmer prime test (for Mersenne numbers), in Forth

Pedigree

The sources for the gint.dll of the full GiantInt package can be downloaded from: http://www.perfsci.com/free/giantint/giantint.html.

  (Release 22 OCT 2001)

  "You may download giantint at any time, free of charge. PSI makes no warranty for this free
   software and we disclaim any and all implied warranties or conditions, including any implied
   warranty of title, of noninfringement, of merchantability, or of fitness for a particular
   purpose. If these terms are acceptable to you and you wish to download the free software,
   click here..."

The sources can be compiled to gint.dll, with some work. What to do exactly will be come clear when I release the Linux variant.

Bugs


   S" 99999999999999999999999991111111111111111173212028727617181111" .factor

   33107 * 560929 * 5384833477785736418660700040798137594423688327731437 [composite?]

   S" 5384833477785736418660700040798137594423688327731437" .factor

   ( should give: 548469301596654329 * 9817930487832035819402468332988053 or time out )

The timeout happens. However, it may just mean that Lenstra's method (from which I swiped the example) is better than what is in the GiantInt package. free counter