1
$\begingroup$

I am reading on a specific operation, how it should be done in order to avoid overflow during multiplication.
The operation is:
$( A * \text{state} ) \% M;$

This is susceptible to overflow.

The modified operation that does not have this pitfall is:
$A(\text{state}(\bmod{Q})) - R(\text{state}/Q) + M\delta(\text{state})$

$Q$ and $R$ are the quotient and remainder of $M/A$.

$\delta$ evaluates to 0 or 1 depending on the subtraction of the first 2 terms.

This $R (\text{state}/Q)$ is low limit/bound but I don't know the tag.

I don't get how these expressions are equivalent i.e. produce the same result.

Could you please help me?

  • 0
    I guess Schrage's multiplication algorithm: [PDF here](http://beam.acclab.helsinki.fi/~djurabek/mc/Schrage_proof.pdf), [here](http://mathworld.wolfram.com/SchragesAlgorithm.html).2012-04-03

0 Answers 0