Tintin's blog

How I do big number (>10^20) mod by a number
By Tintin, 13 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

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


→ Reply
13 years ago, # |
  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
  • 13 years ago, # ^ |
      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
    • 13 years ago, # ^ |
        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
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Is this question about this problem? ;)
      → Reply
13 years ago, # |
  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
  • 13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    From where you got this information ? thanks
    → Reply
    • 13 years ago, # ^ |
        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
13 years ago, # |
  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