Re: Questions

Mark Tillotson (markt@harlequin.co.uk)
Mon, 14 Sep 1998 20:46:14 +0100

• Next message: C Matthew Curtin: "Re: tristrata"
• Previous message: Greg Noel: "Spam from t10.net"

Walied.Othman@Student.KULeuven.ac.be asked:
| I 'm designing a package to handle large (signed) integers (in pascal), the size of these
There is at least one GPL'd package to do this, including the package
in the public versions of PGP - someone will know what the others are
(in the FAQ?)

| integers are merely bounded by the available memory. First a trivial question: Does
| anyone have a fast (faster than euclidean division) algorithm to calculate x mod n?

It's a standard result in complexity theory that square-root,
reciprocation, division/modulus and multiplication are all mutually
implementable with a only a small constant factor slowdown - in other
words they are all asymptotically the same, and the fastest
multiplication algorithm is N log N (well, near as dammit!).

For really big integers (I think the trade-off is at
thousands of bits) the Schonhasse-Strassen algorithm is best (but
COMPLEX), at O(N.log(N).log(log(N))) I think (but with a large
constant factor).

For hundreds of bits and below a recursive technique can be used which
is O(N^1.5) with a low constant factor. There is a good paper
discussing these at the RSA website (its mainly concerned with modular
exponentiation, of course)

For the smaller/medium sizes, Division/modulus are not best
implemented in terms of multiplication, but there are still clever
tricks I think. Knuth has the basic long-division algorithm.

| Performance:
| What number of cycles are acceptable/fast/extraordinary to multiply/add x-digit
| numbers?
as above, plus the obvious observation that +/- are O(N), comparison
is O(1) (expected), mult/division by a small (single word) value is O(N).

| What functions (besides the basics (+,-,*,/), and x mod n, x^d mod n) should such a a
| package contain?
comparisons, scaling by small constants, string/radix conversion, gcd/lcm
naive factorization?, chinese-remaindering, etc etc.

| If I 'm forgetting something, let me know.
Its dead handy to have garbage collection if using true integers...
...so why use Pascal?

__Mark
[ markt@harlequin.co.uk | http://www.harlequin.co.uk/ | +44(0)1954 785433 ]
[ personal homepage http://utter.chaos.org.uk/~markt/ | fax " " 785444 ]

• Next message: C Matthew Curtin: "Re: tristrata"
• Previous message: Greg Noel: "Spam from t10.net"