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'm looking for solution to a problem to calculate modulo of very large number that can contain 25000 digits or less (n) with 10 digit number (m). ( n % m ) ?

Pointer to appropriate theory resource is also welcome.

Thanks

share|improve this question
    
You mean on a computer? You'll probably have to use a bignum library of some kind – in which case this is just a programming question, rather than mathematics. –  Zhen Lin Nov 4 '12 at 11:49
    
Do you have the numbers in some special form or are you asking about the general case? –  Karolis Juodelė Nov 4 '12 at 11:49
    
@KarolisJuodelė General Case. –  Jaini Nov 4 '12 at 11:51
    
Why is the case of large number different from the case of small numbers? As Zhen asked, is this a programming problem? –  Karolis Juodelė Nov 4 '12 at 11:55
    
@KarolisJuodelė Yes, this is a programming problem but I do not want to use bignum library. Because I think there must be interesting property of modulo which can do the task efficiently. Any good source for modular arithmetic in and out? –  Jaini Nov 4 '12 at 12:00

1 Answer 1

As small as your modulus is, I don't think you can do significantly better than ordinary long division (typically done in base $2^{64}$) to compute the remainder.

However, you can optimize the individual steps; e.g. by using an algorithm like Barrett reduction to obtain the remainder of a 2 digit x 1 digit remainder calculation.

Writing efficient (or even simply correct) division code is a very irritating task; unless you really, really like this sort of programming or are using a specialized algorithm for a very special case, you are certainly better off with a good (or even just decent) bignum package.

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.