Re: Large numbers (or is Ada the choice for me?)

[Tucker Taft <stt@averstar.com>]

Hans Georg Schaathun wrote:
> 
> I need a tool to solve large systems of linear equations, with no
> floating point operations (or any other approximations) allowed.
> Even though I am not a seasoned programmer, I think I'll have to
> write the tool myself.
> 
> My question is, will it be reasonably simple to handle large
> rational numbers with Ada?  Is there any packages for this?
> 
> Does basic Ada (gnat) support (f.ex.) 2048-bit integers?  Does
> any module exist for integers of dynamic size?  Are these
> handled reasonably efficiently, or is there much overhead?

The source for the GNAT compiler includes the source for
their "universal arithmetic" package I presume, which (again,
presumably) does arbitrary precision integer and rational 
arithmetic.

> 
> I guess I will manage to implement the rational numbers without
> too much hardship, but I really don't feel like implementing
> arithmetics on large integers.

Try the GNAT compiler sources.  We also have one lying around somewhere.

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. 
 
> 
> :-- Hans Georg
> --
> Signature en panne.

-- 
-Tucker Taft   stt@avercom.net   http://www.averstar.com/~stt/
Chief Technology Officer, AverCom Corporation (A Titan Company) 
Burlington, MA  USA (AverCom was formerly the Commercial Division of AverStar:
http://www.averstar.com/services/ebusiness_applications.html)