Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Are you sure it is the quotient and remainder of $M/A$ and not of $A/M$? – Arturo Magidin Apr 3 '12 at 16:51
Looks quite like the Schrage multiplication trick... – J. M. Apr 3 '12 at 16:54
@ArturoMagidin:It says M/A unless it is a typo.Also that R<Q must be true to not have overflow – user384706 Apr 3 '12 at 16:54
@JM:What is Schrage trick? – user384706 Apr 3 '12 at 16:55
I guess Schrage's multiplication algorithm: PDF here, here. – user2468 Apr 3 '12 at 16:57

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.