Browse Prior Art Database

Fast Calculation of Integer Products Modulo 2**31-1 Using IEEE Floating Point and Fused Multiply-Add

IP.com Disclosure Number: IPCOM000123273D
Original Publication Date: 1998-Aug-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 2 page(s) / 43K

Publishing Venue

IBM

Related People

Enenkel, RF: AUTHOR [+2]

Abstract

This disclosure describes a fast, division-free algorithm for exactly computing integer products modulo 2**<31>-1, using IEEE floating-point arithmetic and fused multiply-add instructions. Let q = 2**<31>-1. Let b and c be integers satisfying 0 lt b lt 2**<31>-1 and 0 lt c lt 2**<31>-1, such that b c mod q ne 0. Let d = b c mod q.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Fast Calculation of Integer Products Modulo 2**31-1 Using IEEE Floating
Point and Fused Multiply-Add

   This disclosure describes a fast, division-free algorithm
for exactly computing integer products modulo 2**<31>-1, using IEEE
floating-point arithmetic and fused multiply-add instructions.
               Let
      q = 2**<31>-1.  Let
      b and
      c be integers satisfying
      0 lt b lt 2**<31>-1 and
      0 lt c lt 2**<31>-1, such that
      b c mod q ne 0.  Let
      d = b c mod q.

   The efficient computation of d is important, for example, in
the linear congruential random number generator described in (1),
      <s sub <i+1> here = 7**5  s sub i mod q ,>
                        hvabove
      <x sub <i+1> here =  s sub <i+1> over q .>

   The disclosed algorithm for computing d is based on the
following formulas.  (Throughout this article, the results are
stated without proof due to space limitations.)
      <d here = b c - lfloor <b c> over q rfloor q>
                        hvabove
      <here = b c - lfloor b c 2**<-31>
       left ( 1 + 2**<-31> + 2**<-62> + 2**<-93> + ellipsis
       right ) rfloor
       left ( 2**<31>-1 right ) >
                    hvabove
       <here = b c - lfloor b c 2**<-31>
       left ( 1 + 2**<-31> right ) rfloor
       left ( 2**<31>-1 right ) >
                    hvabove
       <here = b c - 2**<31>
       lfloor b c left ( 2**<-31> + 2**<-62> right ) rfloor +
       lfloor b c left ( 2**<-31> + 2**<-62> right ) rfloor .

   Assume a computer using IEEE double precision floating
point arithmetic with the round-to-zero rounding mode, and having a
single-rounding-error f...