Блог пользователя Tintin

How I do big number (>10^20) mod by a number
Автор Tintin, 13 лет назад, По-английски
How I do big number (>10^20) mod by a number,
thanks
  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

13 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится


→ Ответить
13 лет назад, # |
← Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится


→ Ответить
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
In which form do you have this number? Is there any limitations on modulo?

→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    suppose n=7 and the big number m is=12345678910.........(lenth is 1000), and I want to know m%n
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      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.
      → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Is this question about this problem? ;)
      → Ответить
13 лет назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится
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.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    From where you got this information ? thanks
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      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.
      → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
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
→ Ответить