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

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...