Alogorytm modulo - wyjaśnienie

Question

Cześć,

Czy może ktoś pomóc w zrozumieniu tego algorytmu?

Załóżmy, że chcemy wyznaczyć 12345(mod100).
Skorzystamy z następującego algorytmu:

reszta=1(mod100)

reszta=(reszta∗10+2)(mod100)

reszta=(reszta∗10+3)(mod100)

reszta=(reszta∗10+4)(mod100)

reszta=(reszta∗10+5)(mod100)

reszta=45

Sama idea jest jasna: bierzemy pierwszą cyfrę i z niej resztę z dzielenia przez sto. W kolejnym kroku otrzymaną wcześniej resztę mnożymy przez dziesięć , dodajemy kolejną cyfrę i wyznaczamy resztę z dzielenia przez sto, itd.
Dlaczego na początku bierzemy pojedynczą cyfrę 1, mimo to, że jest to cyfra dziesiątek tysięcy i wyznaczamy jej resztę, a nie startujemy na przykład od 5? Później nagle mnożymy przez 10 i dodajemy kolejną cyfrę. Dlaczego to działa?

Answer 1

Spróbuje to wyjaśnić na prostszym przykładzie. Powiedzmy że masz liczbę 50 i chesz policzyć 50 modulo 3. Ale zapomnijmy na razie, że to jest 50 i skupmy się na pierwszej cyfrze tej liczby czyli 5.

5 % 3 = 2, czyli pisząc inaczej 1*3 + 2 = 5

To co zrobiliśmy to zapisaliśmy 5 jako sumę pewnej ilości trójek i jednej dwójki. I teraz popatrz czym jest liczba 50. 50 to tak naprawdę dziesięć tych piątek. No to pomnóżmy wyżej otrzymany wynik przez 10.

(1*3 + 2)*10 = 10*3 + 20 = 50

Jak widać powyższy zapis przedstawia liczbę 50, ale jest mały problem, gdyż reszta 20 jest większa od 3, a to jest niedopuszczalne. Ale nic nie stoi na przeszkodzie, aby wziać tę resztę modulo 3.

20 % 3 = 6*3 + 2

Czyli liczbę 50 można inaczej zapisać jako 10*3 + 6*3 + 2 = 16*3 + 2 i tym samym otrzymujemy wynik działania 50 % 3.

To samo rozumowanie można zastosować dla dowolnej innej liczby. Tak samo w Twoim przykładzie z 12345 % 100 wzieliśmy na początku 1 % 100, ale w kolejnych krokach pomnożymy to 1 cztery razy przez 10, czyli to 1 zamieni się w 10000. Dwójkę pomnożymy trzy razy przez 10 i zamieni się w 2000, tak samo 3 mnożymy dwa razy przez dziesięć, a 4 raz.

Po zsumowaniu wychodzi nam, że otrzymamy 10000 + 2000 + 300 + 40 + 5 = 12345

Comments

Dzięki za wyjaśnienia, ale tak myślę, że na pytanie: Dlaczego to działa? wystarczyłoby odpowiedzieć, że działa, ponieważ jest to zwykłe dzielenie pod kreską ( po usunięciu tego mnożenia przez 10, nie jest potrzebne, wystarczy do wyniku doklejać kolejną cyfrę : +"2", +"3", itd.). Przecież to właśnie jest tam robione. Zaczyna się od ile razy 1 mieści się w 100? 0, więc piszemy 1-0=1 i doklejamy "2", itd.