home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / lang / fortran / 2836 < prev    next >
Encoding:
Text File  |  1992-07-25  |  4.1 KB  |  90 lines
  1. Newsgroups: comp.lang.fortran
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!moe.ksu.ksu.edu!ux1.cso.uiuc.edu!news.cs.indiana.edu!orstnews!pmontgom
  3. From: pmontgom@math.orst.edu (Peter Montgomery)
  4. Subject: Re: 64-bit integers from Sun f77
  5. Message-ID: <1992Jul25.231516.27506@talon.ucs.orst.edu>
  6. Sender: usenet@talon.ucs.orst.edu (Usenet News admin)
  7. Nntp-Posting-Host: lab2.math.orst.edu
  8. Organization: Oregon State University Math Department
  9. References: <1992Jul16.215352.25027@beaver.cs.washington.edu> <9080023@hpfcso.FC.HP.COM>
  10. Date: Sat, 25 Jul 1992 23:15:16 GMT
  11. Lines: 77
  12.  
  13. In article <9080023@hpfcso.FC.HP.COM> kauth@hpfcso.FC.HP.COM (Joan Kauth)
  14. asks:
  15. >
  16. >Why do you need 64-bit integers?
  17. >I.e. What do you use integers for that requires > 32 bits?
  18.  
  19.  
  20.  1.  Multiple-precision arithmetic.  Presently we can do
  21.      16 x 16 = 32-bit products in Fortran and C, and 32 x 32 = 64 in
  22.      assembly (or using long long data in GNU C).  
  23.      We need language constructs NOW for 32 x 32 = 64, 
  24.      and soon for 64 x 64 = 128.
  25.  
  26.  2.  Long programs do operations over 2^32 times.  For example,
  27.      my library has counters telling how often each subroutine
  28.      has been called.  When the program runs a full day,
  29.      some of these counters overflow.  How can a subroutine
  30.      get called a negative number of times, some will wonder.
  31.  
  32.  3.  Big intermediate results.  For example, I do FFT's modulo p,
  33.      where p is a prime congruent to 1 modulo 2^12 = 4096.
  34.      If we restrict p < 2^16, then only three values of p qualify:
  35.      12289, 40961, 61441.  These are inadequate for my application.
  36.      If we allow p < 2^32, approximately 100000 values of p qualify.
  37.      However, if p > 2^16, then the product a*b can overflow as
  38.      I attempt to compute a*b mod p where 0 <= a, b, <= p-1.
  39.      In other words, I need 64 bits for the intermediate product.
  40.  
  41.  4.  My latest research project will scan every lattice point 
  42.      (point with integer coordinates) in a rectangle of area circa 10^15.
  43.      The precise height and width are chosen by the program to maximize 
  44.      a success probability, and might be 10^5 and 10^10.  If so, the loop 
  45.      counter (which goes from 1 to the width) will not fit in 32 bits.
  46.  
  47.              If n is the standard integer length (currently n = 32,
  48.      soon n = 64) then I want the following operations to
  49.      be available, generating inline code, where a1, a2,
  50.      have n bits and b1, b2 have 2n bits:
  51.  
  52.         Constants of length 2n
  53.         Type conversions b1 = INT(a1, kind=2n)   (cast a1 to double-length)
  54.                          a1 = INT(b1, kind=n)
  55.                          Also conversions to/from floating point.
  56.         b1 = INT(a1,kind=2n)*INT(a2,kind=2n)        (n x n -> 2n bits)
  57.         a2 = b1/a1 and a3 = MOD(b1, a1)  (2n/n = n bit quotient and remainder)
  58.                                         Undefined if quotient overflows.
  59.         Addition and subtraction: -b1, b1 + b2, b1 - b2.
  60.         Relationals b1.eq.b2, b1.gt.b2, ...
  61.         Bitwise ops IAND(b1, b2), IOR(b1, b2), IEOR(b1, b2), NOT(b1).
  62.         ISHFT with constant shift count and first argument of length 2n.
  63.  
  64.      Convenient but less important are:
  65.  
  66.         Ability to express rounding direction explicitly on conversions
  67.                 to/from floating point.
  68.         Mixed expressions such as b1 +- a1, b1.ge.a1 .
  69.         Simple intrinsics ABS(b1), MIN(b1, b2), MAX(b1, b2), DIM(b1, b2),
  70.                           SIGN(b1, b2).
  71.         ISHFT with variable shift count and first argument of length 2n.
  72.         a1*b1 (product assumed to fit in 2n bits).
  73.         Input and output of integers of length 2n.
  74.         Debugger support for manipulating entities of length 2n.
  75.     Truncated (or rounded) integer square root of b1, and remainder.
  76.  
  77.      Not important (for my present applications) are:
  78.  
  79.         DO loop counters of length 2n.
  80.     Array dimensions low:high where low and high have length 2n.
  81.         ISHFT(..., b1)
  82.         (...)**b1        (except to generate constants 2^k - 1,
  83.                  where k is constant and k <= 2n - 1)
  84.         b1*b2, b1/b2, b1**(...)
  85. -- 
  86. New address as of June 26, 1992:
  87.         Peter L. Montgomery              Internet: pmontgom@math.orst.edu
  88.         Dept. of Mathematics, Oregon State Univ, Corvallis, OR 97331-4605 USA
  89.  
  90.