Tintin's blog

How I do big number (>10^20) mod by a number
By Tintin, 15 years ago, In English
How I do big number (>10^20) mod by a number,
thanks
  • Vote: I like it
  • +9
  • Vote: I do not like it

15 years ago, hide # |
← Rev. 3  
Vote: I like it +3 Vote: I do not like it


→ Reply
15 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it
In which form do you have this number? Is there any limitations on modulo?

→ Reply
  • 15 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it
    suppose n=7 and the big number m is=12345678910.........(lenth is 1000), and I want to know m%n
    → Reply
    • 15 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it
      There are two main approaches:
      1) Use programming language which could handle big numbers (Java, C#, Lisp etc.)
      2) If such operation is the primary task of your exercise, then you obviously should write division manually. It is far easier if the divisor itself is not a big number. Algorithm surely is close to that you study in the middle-school, at math course.
      → Reply
    • 15 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it
      Is this question about this problem? ;)
      → Reply
15 years ago, hide # |
 
Vote: I like it +28 Vote: I do not like it
Just read the number digit-by-digit and maintain the remainder.

For example,
1 mod 7 = 1
12 mod 7 = (1 * 10 + 2) mod 7 = 5
123 mod 7 = (5 * 10 + 3) mod 7 = 4
1234 mod 7 = (4 * 10 + 4) mod 7 = 2
etc.
→ Reply
  • 15 years ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it
    From where you got this information ? thanks
    → Reply
    • 15 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it
      I suppose from primitive number theory, since (an 10n + ..a1 10 + a0)%MODULO = 
      (an10n)%MODULO + ... + (a1 10)%MODULO) + a0%MODULO.
      After this the only thing to do is to implement this algo the best way like Gassa did.
      → Reply
15 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
If the number is given in the form baseexponent then you should consider two ways: Modular exponentiation, which works in O(exponent) or Exponentiation by squaring (modified to mantain the result mod M), which works in O(log(exponent)) so it is very fast also for large exponents
→ Reply