Próbuję wdrożyć prosty algorytm w JavaScript. Gdziekolwiek spojrzę, to wymaga, aby kod zadziałał 1 (mod N). O ile mogę powiedzieć, 1 modulo wszystko (lub 1%N) jest 1.Co oznacza 1 (mod N)?
Czego mi brakuje? Czy to zawsze 1, a jeśli tak, to dlaczego nie użyć 1?
Algorytm chyba mówi coś takiego:
x ≡ 1 (mod N) # x is congruent to 1 (modulo N)
The (mod N) i potrójnych znaku równości oznaczają, że pracujesz z arytmetyki modularnej, nie jest normalne arytmetycznej. Pomyśl o tym jak o zegarach. W arytmetykach modułowych x ≡ 1 oznacza, że x i 1 należą do tego samego residue class. Jeśli masz zegar z podziałem godzinowym N, obrót czasu o 1 lub x spowoduje przesunięcie ręki do tej samej pozycji końcowej.
dla konkretnego przypadku, x ≡ 1 (mod N) może być reprezentowana jako x % N === 1 w JavaScript jeśli x nigdy nie jest ujemny. W przeciwnym razie twoja równość nie będzie się utrzymywać, chociaż powinna: na przykład -1 ≡ 1 (mod 2), ale (-1) % 2 === -1, która nie jest równa 1, mimo że są one "równe" w modułowym znaczeniu arytmetycznym.
Jeśli oczekujesz x być ujemny, można po prostu przestawić kongruencją:
x ≡ 1 (mod N)
⇒ x - 1 ≡ 0 (mod N)
x - 1 będąc przystające do 0 oznacza, że jest podzielna przez samą N, więc można użyć operatora modulo bezpiecznie:
if ((x - 1) % N === 0) {
...
}
Aby wyjaśnić: 'x ≡ 1 (mod N)' jest * naprawdę * 'x% N == 1% N', co upraszcza do' x% N == 1', ponieważ '1% N == 1' (zakładając 'N' nie jest 1). – sevko
Sposób działania operatora modulo (%) zdefiniowano w ECMA-262 §11.5.3. Istnieje kilka dziwactw, operator modulo ECMAScript akceptuje pływaki jak również liczby całkowite:
Dla liczb całkowitych:
1 % -Infinity returns 1
...
1 % -2 returns 1
1 % -1 returns 0
1 % 0 returns NaN
1 % 1 returns 0
1 % 2 returns 1
...
1 % Infinity returns 1
Dla pływaków,
1 % -1.1 returns 1
1 % 0.1 returns 0.09999999999999995
1 % 0.6 returns 0.4
1 % 0.5 returns 0
1 % 0.4 returns 0.19999999999999996
1 % 0.9 returns 0.09999999999999998
1 % 1.1 returns 1
Więc bez kontekstu, w jaki operator modulo jest stosowany, bardzo trudno jest ustalić, dlaczego jest on używany. Najlepszy ze wszystkich byłoby dokumentacja kodu, ale przypuszczam, że nie jest dostępna.
Jednym z zastosowań jest, gdzie oczekuje się liczbą całkowitą, aby ocenić 0 i 1 jako fałszywe i wszystko inne co prawda, tak:
if (1 % n) {
// do this if n is something other than 0 or 1
}
"1 modulo coś (lub 1% N) wynosi 1" - chyba N wynosi 1, w takim przypadku wynik wynosi zero. –
Kluczową rzeczą do zrozumienia jest to, że w notacji matematycznej '(mod n)' odnosi się do * obu * boków wyrażenia, nawet , chociaż zwykle jest napisane tylko po prawej stronie (patrz [Confused about modular notations] (http://math.stackexchange.com/questions/78367/confused-about-modular-notations)). Tak więc, wychodząc z odpowiedzi @ Blendera, wyrażenie 'a ≡ 1 (mod N)' powinno być odczytywane jako "' a ≡ 1' kiedy system jest wzięty 'modulo N'" lub 'a% N == 1 % N' (lub po prostu 'a% N == 1', ponieważ' 1% N' zawsze ma wartość 1). – sevko