From: pmontgom@math.orst.edu (Peter Montgomery)
Subject: Re: 64-bit integers from Sun f77
Organization: Oregon State University Math Department
Date: Sat, 25 Jul 1992 23:15:16 GMT

In article <9080023@hpfcso.FC.HP.COM> kauth@hpfcso.FC.HP.COM (Joan Kauth)
asks:
>
>Why do you need 64-bit integers?
>I.e. What do you use integers for that requires > 32 bits?


 1.  Multiple-precision arithmetic.  Presently we can do
     16 x 16 = 32-bit products in Fortran and C, and 32 x 32 = 64 in
     assembly (or using long long data in GNU C).  
     We need language constructs NOW for 32 x 32 = 64, 
     and soon for 64 x 64 = 128.

 2.  Long programs do operations over 2^32 times.  For example,
     my library has counters telling how often each subroutine
     has been called.  When the program runs a full day,
     some of these counters overflow.  How can a subroutine
     get called a negative number of times, some will wonder.

 3.  Big intermediate results.  For example, I do FFT's modulo p,
     where p is a prime congruent to 1 modulo 2^12 = 4096.
     If we restrict p < 2^16, then only three values of p qualify:
     12289, 40961, 61441.  These are inadequate for my application.
     If we allow p < 2^32, approximately 100000 values of p qualify.
     However, if p > 2^16, then the product a*b can overflow as
     I attempt to compute a*b mod p where 0 <= a, b, <= p-1.
     In other words, I need 64 bits for the intermediate product.

 4.  My latest research project will scan every lattice point 
     (point with integer coordinates) in a rectangle of area circa 10^15.
     The precise height and width are chosen by the program to maximize 
     a success probability, and might be 10^5 and 10^10.  If so, the loop 
     counter (which goes from 1 to the width) will not fit in 32 bits.

             If n is the standard integer length (currently n = 32,
     soon n = 64) then I want the following operations to
     be available, generating inline code, where a1, a2,
     have n bits and b1, b2 have 2n bits:

        Constants of length 2n
        Type conversions b1 = INT(a1, kind=2n)   (cast a1 to double-length)
                         a1 = INT(b1, kind=n)
                         Also conversions to/from floating point.
        b1 = INT(a1,kind=2n)*INT(a2,kind=2n)        (n x n -> 2n bits)
        a2 = b1/a1 and a3 = MOD(b1, a1)  (2n/n = n bit quotient and remainder)
                                        Undefined if quotient overflows.
        Addition and subtraction: -b1, b1 + b2, b1 - b2.
        Relationals b1.eq.b2, b1.gt.b2, ...
        Bitwise ops IAND(b1, b2), IOR(b1, b2), IEOR(b1, b2), NOT(b1).
        ISHFT with constant shift count and first argument of length 2n.

     Convenient but less important are:

        Ability to express rounding direction explicitly on conversions
                to/from floating point.
        Mixed expressions such as b1 +- a1, b1.ge.a1 .
        Simple intrinsics ABS(b1), MIN(b1, b2), MAX(b1, b2), DIM(b1, b2),
                          SIGN(b1, b2).
        ISHFT with variable shift count and first argument of length 2n.
        a1*b1 (product assumed to fit in 2n bits).
        Input and output of integers of length 2n.
        Debugger support for manipulating entities of length 2n.
	Truncated (or rounded) integer square root of b1, and remainder.

     Not important (for my present applications) are:

        DO loop counters of length 2n.
	Array dimensions low:high where low and high have length 2n.
        ISHFT(..., b1)
        (...)**b1		(except to generate constants 2^k - 1,
				 where k is constant and k <= 2n - 1)
        b1*b2, b1/b2, b1**(...)
-- 
New address as of June 26, 1992:
        Peter L. Montgomery              Internet: pmontgom@math.orst.edu
        Dept. of Mathematics, Oregon State Univ, Corvallis, OR 97331-4605 USA