Jakie uzasadnienie stosuje się, gdy projektanci języków programowania decydują, jaki znak ma wynik działania modulo?

9

Przechodząc przez operację Modulo (aleję, którą wszedłem, badając różnicę między remimod ) natknąłem się na:

W matematyce wynikiem operacji modulo jest pozostała część podziału euklidesowego. Możliwe są jednak inne konwencje. Komputery i kalkulatory mają różne sposoby przechowywania i reprezentowania liczb; dlatego ich definicja działania modulo zależy od języka programowania i / lub podstawowego sprzętu.

Pytania:

  • Przechodząc przez dywizję euklidesową odkryłem, że zakończenie tej operacji jest zawsze dodatnie (lub 0). Jakie ograniczenia podstawowego sprzętu komputerowego zmuszają projektantów języków programowania do odróżnienia się od matematyki?
  • Każdy język programowania ma zdefiniowaną lub niezdefiniowaną regułę, zgodnie z którą wynik operacji modulo otrzymuje swój znak. Jakie uzasadnienie przyjmuje się przy tworzeniu tych zasad? A jeśli chodzi o podstawowy sprzęt, to czy zasady nie powinny się zmieniać zgodnie z tym, niezależnie od języka programowania?
Krwawiące palce
źródło
1
W moim kodzie prawie zawsze potrzebuję modulo, a nie reszty. Nie mam pojęcia, dlaczego reszta jest tak popularna.
CodesInChaos
8
Powiązane Jaka jest różnica? Remainder vs Modulus - Blog Erica Lipperta (autorstwa jednego z projektantów C #, ale wierzę, że dołączył do zespołu po podjęciu tej decyzji)
CodesInChaos
1
Jeśli nadal czytasz artykuł z Wikipedii (poza cytowaną częścią), wyjaśnia to, co zacytowałeś całkiem nieźle. Co powiesz na to wyjaśnienie?
Robert Harvey
1
Jedno pokrewne pytanie dotyczy tego, które z tych operacji bezpośrednio odwzorowują instrukcje CPU. W c jest zdefiniowana implementacja, która jest zgodna z filozofią c polegającą na bezpośrednim mapowaniu do sprzętu na jak największej liczbie platform. Nie określa więc rzeczy, które mogą się różnić między procesorami.
CodesInChaos
5
@BleedingFingers Programowanie często wykorzystuje dzielenie liczb całkowitych, które idzie w kierunku zera, np (-3)/2 == -1. Ta definicja może być przydatna. Jeśli chcesz %zachować spójność z tym podziałem, to kończysz x == (x/y)*y + x % ysię definicją %używaną w C #.
CodesInChaos

Odpowiedzi:

7

Sprzęt wszystkich współczesnych komputerów ma wystarczającą moc, aby zaimplementować operacje modowe dowolnego znaku bez wpływu (lub trywialnego) na wydajność. To nie jest powód.

Powszechnym oczekiwaniem większości języków komputerowych jest to, że (a div b) * b + (a mod b) = a. Innymi słowy, div i mod rozpatrywane razem dzielą liczbę na części, które można niezawodnie połączyć ponownie. To wymaganie jest wyraźnie określone w standardzie C ++. Koncepcja jest ściśle związana z indeksowaniem tablic wielowymiarowych. Używałem go często.

Z tego wynika, że ​​div i mod zachowają znak a, jeśli b jest dodatnie (jak zwykle jest).

Niektóre języki zapewniają funkcję „rem ()”, która jest powiązana z modem i ma inne matematyczne uzasadnienie. Nigdy nie potrzebowałem tego używać. Zobacz na przykład frem () w Gnu C. [edytowany]

david.pfx
źródło
Myślę, że tak rem(a,b)jest bardziej, mod(a,b)jeśli jest to pozytywne lub mod(a,b) + bjeśli nie jest.
user40989,
3
(a div b) * b + (a mod b) = a- to bardzo. W rzeczywistości, w przeciwieństwie do tego, jak Wikipedia opisuje rozszerzanie go na liczby ujemne w podziale euklidesowym (zwłaszcza „reszta jest jedyną z czterech liczb, które nigdy nie mogą być ujemne”). Mylą mnie, ponieważ zawsze uczono mnie, że reszta może być ujemna w każdej klasie matematyki na tym poziomie.
Izkata
@ user40989: Powiedziałem, że nigdy go nie użyłem. Zobacz edycję!
david.pfx
4

Do programowania zwykle chcesz X == (X/n)*n + X%n; dlatego sposób definiowania modulo zależy od sposobu zdefiniowania podziału na liczby całkowite.

Mając to na uwadze, naprawdę pytasz: „ Jakie uzasadnienie stosuje się, gdy projektanci języków programowania decydują o działaniu podziału liczb całkowitych?

Istnieje właściwie około 7 opcji:

  • zaokrąglenie do ujemnej nieskończoności
  • zaokrąglanie do dodatniej nieskończoności
  • zaokrąglić do zera
  • kilka wersji „zaokrąglić do najbliższego” (z różnicami w zaokrąglaniu czegoś takiego jak 0,5)

Teraz zastanów się -( (-X) / n) == X/n. Chciałbym, aby było to prawdą, ponieważ wszystko inne wydaje się niespójne (dotyczy to zmiennoprzecinkowego) i nielogiczne (prawdopodobna przyczyna błędów, a także potencjalnie pominięta optymalizacja). To sprawia, że ​​pierwsze 2 opcje podziału liczb całkowitych (zaokrąglanie do dowolnej nieskończoności) są niepożądane.

Wszystkie „okrągłe do najbliższych” wyborów są uciążliwe w programowaniu, szczególnie gdy robisz coś w rodzaju bitmap (np offset = index / 8; bitNumber = index%8;.).

To pozostawia zaokrąglenie w kierunku zera jako „potencjalnie najbardziej rozsądnego” wyboru, co oznacza, że ​​modulo zwraca wartość o tym samym znaku, co licznik (lub zero).

Uwaga: Zauważysz również, że większość procesorów (wszystkie znane mi procesory) dzielą liczby całkowite w ten sam sposób „zaokrąglając do zera”. Prawdopodobnie dzieje się tak z tych samych powodów.

Brendan
źródło
Ale obcinanie dywizji ma również swoje niespójności: łamie się, (a+b*c)/b == a % ba a >> n == a / 2 ** ndla których dywersja podziałowa ma rozsądne zachowanie.
dan04
Twój pierwszy przykład nie ma sensu. Twój drugi przykład jest bałaganem dla programistów: dla dodatniego a i dodatniego n jest on spójny, dla ujemnego a i dodatniego n zależy od tego, jak zdefiniowane jest przesunięcie w prawo (arytmetyka vs. logika), a dla ujemnego n jest zepsute (np 1 >> -2 == a / 2 ** (-2).).
Brendan
Pierwszym przykładem była literówka: miałem na myśli (a + b * c) % b == a % bto, że %operator jest dywidendowo-okresowy w dywidendzie, co często jest ważne. Na przykład w przypadku podziału na podziałkę day_count % 7podaje dzień tygodnia, ale w przypadku podziału na skróty przedziały dla dat sprzed epoki.
dan04
0

Najpierw powtórzę, że moduł b powinien być równy a - b * (div b), a jeśli język tego nie zapewnia, masz straszny bałagan matematyczny. To wyrażenie a - b * (div b) jest w rzeczywistości liczbą implementacji obliczających moduł b.

Istnieje kilka możliwych uzasadnień. Po pierwsze, chcesz maksymalnej prędkości, więc div b jest zdefiniowane jako wszystko, co zapewni procesor. Jeśli twój procesor ma instrukcję „div”, wtedy div b jest wszystkim, co robi instrukcja div (o ile nie jest to coś całkowicie szalonego).

Drugi polega na tym, że chcesz mieć określone zachowanie matematyczne. Załóżmy najpierw, że b> 0. Jest całkiem rozsądne, że chcesz, aby wynik div b był zaokrąglany w kierunku zera. Więc 4 dział 5 = 0, 9 dział 5 = 1, -4 dział 5 = -0 = 0, -9 dział 5 = -1. To daje ci (-a) div b = - (a div b) i (-a) modulo b = - (modulo b).

Jest to całkiem rozsądne, ale nie idealne; na przykład (a + b) div b = (a div b) + 1 nie zachowuje, powiedzmy, jeśli a = -1. Przy stałym b> 0 zwykle są (b) możliwe wartości dla takiego, że div b daje ten sam wynik, z tym wyjątkiem, że istnieją wartości 2b - 1 a od -b + 1 do b-1, gdzie div b wynosi 0 Oznacza to również, że moduł b będzie ujemny, jeśli a jest ujemne. Chcielibyśmy, aby moduł b był zawsze liczbą z zakresu od 0 do b-1.

Z drugiej strony rozsądne jest również żądanie, aby w miarę przechodzenia przez kolejne wartości a moduł b przechodził przez wartości od 0 do b-1, a następnie zaczynał od 0 ponownie. I zażądać, aby (a + b) div b było (a div b) + 1. Aby to osiągnąć, chcesz, aby wynik div b był zaokrąglany w kierunku-nieskończoności, więc -1 div b = -1. Ponownie są wady. (-a) div b = - (a div b) nie obowiązuje. Wielokrotne dzielenie przez dwa lub dowolną liczbę b> 1 ostatecznie nie da wyniku 0.

Ponieważ istnieją konflikty, języki będą musiały zdecydować, który zestaw korzyści jest dla nich ważniejszy i odpowiednio zdecydować.

W przypadku ujemnego b większość ludzi nie może obrócić głowy o to, czym powinny być div b i moduł b, więc prosty sposób polega na zdefiniowaniu, że div b = (-a) div (-b) i modulo b = (-a) modulo (-b), jeśli b <0, lub cokolwiek to naturalny wynik użycia kodu dla dodatniego b.

gnasher729
źródło