GCL SI Manual: Bignums

A directory mp was added to hold the new multi precision arithmetic code. The layout and a fair amount of code in the mp directory is an enhanced version of gpari version 34. The gpari c code was rewritten to be more efficient, and gcc assembler macros were added to allow inlining of operations not possible to do in C. On a 68K machine, this allows the C version to be as efficient as the very carefully written assembler in the gpari distribution. For the main machines, an assembler file (produced by gcc) based on this new method, is included. This is for sites which do not have gcc, or do not wish to compile the whole system with gcc.

Bignum arithmetic is much faster now. Many changes were made to cmpnew also, to add ’integer’ as a new type. It differs from variables of other types, in that storage is associated to each such variable, and assignments mean copying the storage. This allows a function which does a good deal of bignum arithmetic, to do very little consing in the heap. An example is the computation of PI-INV in scratchpad, which calculates the inverse of pi to a prescribed number of bits accuracy. That function is now about 20 times faster, and no longer causes garbage collection. In versions of GCL where HAVE_ALLOCA is defined, the temporary storage growth is on the C stack, although this often not so critical (for example it makes virtually no difference in the PI-INV example, since in spite of the many operations, only one storage allocation takes place.

Here is the comparison of lucid and gcl before and after on that pi-inv. Times are in seconds with multiples of the gcl/akcl time in parentheses.

pi-inv   akcl-566  franz        lucid         old kcl/akcl
----------------------------------------
10000      3.3     9.2(2.8 X)  15.3 (4.6X)    92.7   (29.5 X)
20000      12.7    31.0(2.4 X) 62.2 (4.9X)    580.0  (45.5 X)


(defun pi-inv (bits &aux (m 0))
  (declare (integer bits m))
  (let* ((n (+ bits (integer-length bits) 11))
         (tt (truncate (ash 1 n) 882))
         (d (* 4 882 882))
         (s 0))
    (declare (integer s d tt n))
    (do ((i 2 (+ i 2))
         (j 1123 (+ j 21460)))
        ((zerop tt) (cons s (- (+ n 2))))
      (declare (integer i j))
        (setq s (+ s (* j tt))
              m (- (* (- i 1) (- (* 2 i) 1) (- (* 2 i) 3)))
              tt (truncate (* m tt) (* d (the integer (expt i 3))))))))

15.1 Bignums