Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

 
discard

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

Browse other questions tagged or ask your own question.