Re: ADA arithmetic

[cis.ohio-state.edu!magnus.acs.ohio-state.edu!math.ohio-state.edu!howland. reston.ans.net!noc.near.net!inmet!spock!stt@ucbvax.Berkeley.EDU (Tucker Taft)]

In article <1993Jul26.134358.1@otago.ac.nz> is20115@otago.ac.nz writes:

>I am currently working on a program which requires arithmetic to be performed
>on numbers of up to 16 digits long.  Has anyone out ther written a package
>which will do this?  Add & Subtract would suffice but * & divide and MOD would
>be a big help.  If anyone has one of these could they please mail to source
>code to COSC214.OTAGO.AC.NZ  this would be much appreciated.

Every Ada compiler includes within it an "infinite" precision
arithmetic package.  The GNAT compiler is no exception, so
if you want to do infinite precision arithmetic (both integral
and rational), you can snarf the "july9-release" of GNAT and
extract the following files:

    uintp-.ada   -- Universal Integer package spec
    uintp.ada    -- Univ int package body
    rat-.ada     -- Rational numbers package spec
    rat.ada      -- Rational numbers package body

GNAT is available by anonymous ftp from cs.nyu.edu
in directory pub/gnat/july9-release.  All of the Ada sources
are in the file gnat-src.tar.z (don't forget to use binary/image mode
to transfer it, and you will need gunzip and tar to extract
individual source files).

As do all such infinite precision packages, these packages
uses a sequence of "digits" in some convenient base
(e.g. 10_000 or 2**15) that can safely be manipulated
without overflowing the hardware integer.
In GNAT, these digits are stored in a somewhat obscure way,
since they are using arrays to represent everything.
The algorithms, however, can readily be adapted to other
representations for the sequence of digits.
They are based on the ones given in Knuth's "The Art of 
Computer Programming" Volume 2 (section 4.3.1).

If you are doing a lot of multiplication, rather than addition,
representations based on the "Chinese Remainder Theorem"
are more efficient, but the approach is somewhat more complicated.
(Unfortunately, I don't have a reference on the Chinese Remainder
Theorem.)

Hope this helps.

S. Tucker Taft   stt@inmet.com
Intermetrics, Inc.
Cambridge, MA  02138