Modular type (Re: Large numbers)

[georg@ii.uib.no (Hans Georg Schaathun)]

On Fri, 09 Mar 2001 16:59:32 -0500, Tucker Taft
  <stt@averstar.com> wrote:
: My friends in "experimental mathematics" (sounds like fun, eh?) generally
: prefer to use arbitrary-precision packages based on the Chinese
: remainder theorem, because that allows large multiplications to
: be performed very efficiently.  Essentially a number is represented
: by its value modulo a series of prime numbers, typically those just
: less than 2**31.  Multiplication can then be done by 
: multiplying the individual "digits" independently.  A few dozen "digits"
: is usually enough to handle some very large numbers. 

Great hint;  I should have thought of this before.  Thank you.

But it raises two more questions.

1) Division.
If I remember correctly, that is NP-hard; though that does not really
matter since our numbers are bounded to 32 bits.  I was rather disappointed
to see that Ada does division completely wrong (it would be better not to
do it at all).  What is the best way to do division?  A linear search for
the inverse requires 2*10^9 multiplications, which is about as many as
required for all the rest of the problem.  Is this really the preferred
algorithm?

2) Dynamic modulus.
Is it in any way possible to choose the modulus for a modular type 
runtime, e.g. by parameter to the program?  Or must a dozen mod-types
be defined with hardcoded modulus?  (Barring of course, the possibility
to define modular types from scratch.)

:-- Hans Georg
-- 
Signature en panne.