En passant par l' opération Modulo (l'avenue dans laquelle j'ai pénétré en explorant la différence entre rem
etmod
), je suis tombé sur:
En mathématiques, le résultat de l'opération modulo est le reste de la division euclidienne. Cependant, d'autres conventions sont possibles. Les ordinateurs et les calculatrices ont différentes manières de stocker et de représenter des nombres; ainsi, leur définition de l'opération modulo dépend du langage de programmation et / ou du matériel sous-jacent.
Des questions:
- En passant par la division euclidienne, j'ai trouvé que le reste de cette opération est toujours positif (ou 0). Quelle limitation du matériel informatique sous-jacent oblige les concepteurs de langage de programmation à différer des mathématiques?
- Chaque langage de programmation a sa règle prédéfinie ou indéfinie selon laquelle le résultat de l'opération modulo obtient son signe. Quelle justification est adoptée lors de l'élaboration de ces règles? Et si le matériel sous-jacent est la préoccupation, les règles ne devraient-elles pas changer en conséquence, indépendamment du langage de programmation?
programming-languages
language-design
math
arithmetic
design-decisions
Doigts saignants
la source
la source
(-3)/2 == -1
. Cette définition peut être utile. Lorsque vous voulez%
être cohérent avec cette division,x == (x/y)*y + x % y
vous vous retrouvez avec la définition de%
utilisé en C #.Réponses:
Le matériel de tous les ordinateurs modernes est suffisamment puissant pour implémenter des opérations de mod de l'un ou l'autre signe sans impact (ou trivial) sur les performances. Ce n'est pas la raison.
La plupart des langages informatiques s'attendent à ce que (a div b) * b + (a mod b) = a. En d'autres termes, div et mod considérés ensemble divisent un nombre en parties qui peuvent être reconstituées de manière fiable. Cette exigence est explicite dans la norme C ++. Le concept est étroitement lié à l'indexation des tableaux multidimensionnels. Je l'ai souvent utilisé.
De cela, on peut voir que div et mod conserveront le signe de a si b est positif (comme c'est généralement le cas).
Certains langages fournissent une fonction 'rem ()' qui est liée au mod et a une autre justification mathématique. Je n'ai jamais eu besoin de l'utiliser. Voir par exemple frem () dans Gnu C. [édité]
la source
rem(a,b)
c'est plus probablemod(a,b)
si c'est positif oumod(a,b) + b
non.(a div b) * b + (a mod b) = a
- ça, tellement. En fait, contrairement à la façon dont Wikipedia décrit son extension aux nombres négatifs dans la division euclidienne (en particulier "Le reste est le seul des quatre nombres qui ne peut jamais être négatif.") Me confond parce que j'ai toujours appris que le reste peut être négatif dans chaque classe de mathématiques à ce niveau.Pour la programmation, vous voulez généralement
X == (X/n)*n + X%n
; par conséquent, la façon dont le module est défini dépend de la façon dont la division entière a été définie.Dans cet esprit, vous vous demandez vraiment " Quelle justification est utilisée lorsque les concepteurs de langage de programmation décident comment fonctionne la division entière? "
Il y a en fait environ 7 choix:
Considérez maintenant
-( (-X) / n) == X/n
. Je voudrais que cela soit vrai, car tout le reste semble incohérent (c'est vrai pour la virgule flottante) et illogique (une cause probable de bogues et également une optimisation potentiellement manquée). Cela rend les 2 premiers choix pour la division entière (arrondi vers l'un ou l'autre infini) indésirables.Tous les choix "arrondis au plus proche" sont pénibles pour la programmation, surtout lorsque vous faites quelque chose comme des bitmaps (par exemple
offset = index / 8; bitNumber = index%8;
).Cela laisse l'arrondi vers zéro comme le choix "potentiellement le plus sain d'esprit", ce qui implique que modulo renvoie une valeur avec le même signe que le numérateur (ou zéro).
Remarque: Vous remarquerez également que la plupart des processeurs (tous les processeurs que je connais) effectuent une division entière de la même manière "arrondie à zéro". Ce sera probablement pour les mêmes raisons.
la source
(a+b*c)/b == a % b
eta >> n == a / 2 ** n
, pour laquelle la division au sol a un comportement sain.1 >> -2 == a / 2 ** (-2)
).(a + b * c) % b == a % b
dire, c'est-à-dire que l'%
opérateur est diviseur-périodique dans le dividende, ce qui est souvent important. Par exemple, avec une division au sol,day_count % 7
vous donne le jour de la semaine, mais avec une division tronquée, cela interrompt les dates antérieures à l'époque.Tout d'abord, je répète qu'un modulo b doit être égal à a - b * (a div b), et si un langage ne le fournit pas, vous êtes dans un horrible gâchis mathématique. Cette expression a - b * (a div b) est en fait le nombre d'implémentations qui calculent un modulo b.
Il y a quelques raisons possibles. La première est que vous voulez une vitesse maximale, donc un div b est défini comme ce que le processeur utilisé fournira. Si votre processeur a une instruction "div", alors un div b est ce que fait cette instruction div (tant qu'elle n'est pas totalement folle).
La seconde est que vous voulez un comportement mathématique spécifique. Supposons d'abord b> 0. Il est tout à fait raisonnable que vous vouliez que le résultat d'un div b soit arrondi vers zéro. Donc 4 div 5 = 0, 9 div 5 = 1, -4 div 5 = -0 = 0, -9 div 5 = -1. Cela vous donne (-a) div b = - (a div b) et (-a) modulo b = - (a modulo b).
C'est tout à fait raisonnable mais pas parfait; par exemple (a + b) div b = (a div b) + 1 ne tient pas, disons si a = -1. Avec un b> 0 fixe, il y a généralement (b) des valeurs possibles pour a telles que div b donne le même résultat, sauf qu'il y a 2b - 1 valeurs a de -b + 1 à b-1 où a div b est égal à 0 Cela signifie également qu'un modulo b sera négatif si a est négatif. Nous voudrions qu'un modulo b soit toujours un nombre compris entre 0 et b-1.
D'un autre côté, il est également tout à fait raisonnable de demander qu'à mesure que vous parcourez les valeurs successives de a, un modulo b doit passer par les valeurs de 0 à b-1 puis recommencer par 0. Et pour demander que (a + b) div b soit (a div b) + 1. Pour y parvenir, vous voulez que le résultat d'un div b soit arrondi vers -infini, donc -1 div b = -1. Encore une fois, il y a des inconvénients. (-a) div b = - (a div b) ne tient pas. Diviser plusieurs fois par deux ou par n'importe quel nombre b> 1 ne vous donnera pas finalement un résultat de 0.
Puisqu'il y a des conflits, les langues devront décider quel ensemble d'avantages est le plus important pour elles et décider en conséquence.
Pour b négatif, la plupart des gens ne peuvent pas comprendre ce qu'un div b et un modulo b devraient être en premier lieu, donc un moyen simple est de définir qu'un div b = (-a) div (-b) et a modulo b = (-a) modulo (-b) si b <0, ou quel que soit le résultat naturel de l'utilisation du code pour b positif.
la source