How I do big number (>10^20) mod by a number

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

Автор Tintin, 15 лет назад, По-английски

How I do big number (>10^20) mod by a number,
thanks

need help

Tintin
15 лет назад
10

Комментарии (10)

Написать комментарий?

yeputons

15 лет назад, скрыть # |

← Rev. 2 →

→ Ответить

yeputons

15 лет назад, скрыть # |

← Rev. 3 →

→ Ответить

yeputons

15 лет назад, скрыть # |

In which form do you have this number? Is there any limitations on modulo?

→ Ответить

Tintin

15 лет назад, скрыть # ^ |

suppose n=7 and the big number m is=12345678910.........(lenth is 1000), and I want to know m%n

→ Ответить

RodionGork

15 лет назад, скрыть # ^ |

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.

→ Ответить

olpetOdessaONU

15 лет назад, скрыть # ^ |

Is this question about this problem? ;)

→ Ответить

Gassa

15 лет назад, скрыть # |

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

→ Ответить

SmartCoder

15 лет назад, скрыть # ^ |

From where you got this information ? thanks

→ Ответить

_jte_

15 лет назад, скрыть # ^ |

I suppose from primitive number theory, since (a_n 10ⁿ + ..a₁ 10 + a₀)%MODULO =
(a_n10ⁿ)%MODULO + ... + (a₁ 10)%MODULO) + a₀%MODULO.

After this the only thing to do is to implement this algo the best way like Gassa did.

→ Ответить

wil93

15 лет назад, скрыть # |

If the number is given in the form base^exponent 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

→ Ответить