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

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?

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]

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.

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.