L'opérateur de reste fonctionne sur les doubles en Java

Java

J'enseigne à l'OSU depuis près de deux ans et je suis toujours étonné de voir tout ce que j'apprends de mes étudiants. Par exemple, dans le passé, j'ai demandé à des étudiants d'écrire des morceaux de code étranges que je ne comprenais pas. À ce stade, même après plus de 300 articles de blog, plusieurs vidéos YouTube et même la collecte d'extraits de code dans plus de 100 langues, on pourrait penser que j'ai tout vu. Eh bien, récemment, j'ai vu un étudiant utiliser l'opérateur de reste (% ) en double, et je ne suis plus vraiment le même depuis.

Restant contre opérateur de module

Avant d'entrer dans l'histoire, je voulais faire une distinction entre l'opérateur de reste et l'opérateur de module. En Java, il n'y a pas d'opérateur de module . Au lieu de cela, % est l'opérateur de reste. Pour les nombres positifs, ils sont fonctionnellement équivalents. Cependant, une fois que nous commençons à jouer avec des nombres négatifs, nous verrons une différence surprenante.

J'ai déjà un peu parlé de cette différence dans un article sur le chiffrement RSA. Cela dit, j'ai trouvé une autre excellente source qui compare l'opérateur "modulo" dans différents langages, dont Java, Python, PHP et C.

Pour résumer, l'opérateur de reste fonctionne exactement comme nous nous attendons à ce qu'il fonctionne avec des nombres positifs. Par exemple, si nous prenons 3 % 5 , nous obtiendrions 3 parce que 5 ne va pas du tout dans 3. Si nous commençons à jouer avec des nombres négatifs, les résultats sont similaires. Par exemple, si nous prenons 3 % -5 , nous en aurions encore trois car c'est tout ce qui reste.

Pendant ce temps, si nous retournons le script et rendons le dividende négatif - après tout, le reste est un sous-produit de la division - nous commencerons à voir des restes négatifs. Par exemple, -3 % 5 renvoie -3. De même, -3 % -5 renvoie -3.

Remarquez comment, dans tous ces exemples, nous obtenons les mêmes résultats avec quelques variations sur le signe. En d'autres termes, avec l'opérateur de reste, nous ne sommes pas trop concernés par les signes. Tout ce que nous voulons savoir, c'est combien de fois un nombre va dans un autre nombre. Ensuite, nous examinons le dividende pour déterminer le signe.

D'un autre côté, l'opérateur modulo a un peu plus de nuances. Pour commencer, l'opérande sur le côté droit détermine la plage de valeurs de retour possibles. Si cette valeur est positive, le résultat sera positif. C'est un peu différent de notre opérateur de reste.

Pendant ce temps, l'opérande de gauche détermine la direction dans laquelle nous parcourons la plage de valeurs possibles. Naturellement, cela s'aligne parfaitement avec l'opérateur de reste lorsque les deux valeurs ont le même signe. Malheureusement, ils sont complètement différents dans toutes les autres circonstances :

Expression	Java (reste)	Python (MOD)
`3 % 5`	3	3
`3 % -5`	3	-2
`-3 % 5`	-3	2
`-3 % -5`	-3	-3

Si vous souhaitez en savoir plus sur l'arithmétique modulaire, un autre étudiant m'a inspiré pour écrire un article sur le jeu Rock Paper Scissors utilisant l'arithmétique modulaire.

Opérateur de reste sur les doubles

Lorsque nous pensons à l'opérateur de reste, nous supposons souvent qu'il fonctionne exclusivement avec des nombres entiers - du moins jusqu'à récemment, c'était ma compréhension. Il s'avère que l'opérateur de reste fonctionne en fait sur des nombres à virgule flottante, et cela a du sens.

Inspiration

Plus tôt ce mois-ci, je travaillais avec un étudiant sur un laboratoire qui leur a demandé d'écrire un programme de changement de pièces. Plus précisément, ce programme était censé accepter un certain nombre de centimes de la part de l'utilisateur et produire les coupures en devise américaine (par exemple, dollars, demi-dollars, quarts, dimes, nickels et pennies).

Si vous réfléchissez à la façon dont vous résoudriez ce problème, je vais vous donner un indice :vous pouvez adopter une approche gourmande. En d'autres termes, choisissez d'abord la plus grosse pièce et calculez combien d'entre elles se divisent en votre nombre actuel de cents. Si vous le faites correctement, vous n'avez même pas besoin d'un flux de contrôle. Cependant, vous pouvez nettoyer un peu votre code avec un tableau et une boucle. Comme je suis trop paresseux pour écrire une solution en Java, voici à quoi cela pourrait ressembler en Python :

cents = 150
dollars = cents // 100
cents %= 100
half_dollars = cents // 50
cents %= 50
quarters = cents // 25
cents %= 25
dimes = cents // 10
cents %= 10
nickels = cents // 5
cents %= 5
pennies = cents
print(f'{dollars}, {half_dollars}, {quarters}, {dimes}, {nickels}, {pennies}')

En tout cas, j'avais un étudiant qui interprétait les cents comme des dollars et des cents. En d'autres termes, ils laissent leur utilisateur entrer des montants en dollars comme 1,50 $ au lieu de 150 cents. Pour être juste, ce n'est pas énorme. Tout ce que nous avons à faire est de multiplier le montant en dollars par 100 et d'ajouter les cents restants pour obtenir un nombre entier.

Cependant, ce n'est pas ce que cet étudiant a fait. Au lieu de cela, ils ont traité chaque dénomination comme un double (c'est-à-dire un nombre réel). Ensuite, ils ont procédé à l'utilisation de l'opérateur de reste sans aucune conséquence. Bref, j'étais abasourdi. Après tout, comment cela pourrait-il fonctionner ? Vous ne calculez qu'un reste sur une division longue, n'est-ce pas ? Sinon, il vous reste une décimale et il ne reste rien, du moins c'est ce que je pensais.

Utiliser des doublons

Si nous devions réécrire le programme ci-dessus en utilisant des dollars et des cents, nous aurions peut-être quelque chose qui ressemblerait à ceci :

cents = 1.50
dollars = cents // 1
cents %= 1
half_dollars = cents // .50
cents %= .50
quarters = cents // .25
cents %= .25
dimes = cents // .10
cents %= .1
nickels = cents // .05
cents %= .05
pennies = cents // .01
print(f'{dollars}, {half_dollars}, {quarters}, {dimes}, {nickels}, {pennies}')

Et si nous exécutons ceci, nous obtiendrons exactement le même résultat qu'avant :un dollar et un demi-dollar. Comment est-ce possible ?

Il s'avère que le calcul du reste à l'aide de décimales est parfaitement valide. Tout ce que nous avons à faire est de calculer combien de fois notre dividende va complètement dans notre diviseur. Par exemple, .77 % .25 donnerait "idéalement" 0,02 parce que c'est aussi proche que possible de 0,77 sans dépasser.

Mises en garde

Après avoir découvert qu'il est possible de prendre le reste d'une décimale, je me suis immédiatement demandé pourquoi je ne l'avais pas su plus tôt. Bien sûr, une recherche rapide sur Google vous montre toutes sortes de comportements erronés qui peuvent survenir.

Par exemple, dans l'exemple précédent, j'ai affirmé que 0,02 serait le reste de 0,77 et 0,25, et ce serait, en quelque sorte. Vous voyez, dans la plupart des langages de programmation, les valeurs à virgule flottante par défaut ont une certaine précision dictée par l'architecture binaire sous-jacente. En d'autres termes, il existe des nombres décimaux qui ne peuvent pas être représentés en binaire. Il se trouve que l'un de ces nombres est le résultat de notre expression ci-dessus :

>>> .77 % .25
0.020000000000000018

Lorsque nous travaillons avec des nombres réels, nous rencontrons tout le temps ce genre de problèmes. Après tout, il existe un nombre surprenant de valeurs décimales qui ne peuvent pas être représentées en binaire. En conséquence, nous nous retrouvons avec des scénarios où les erreurs d'arrondi peuvent entraîner l'échec de notre algorithme de changement. Pour prouver cela, j'ai réécrit la solution ci-dessus pour calculer le changement pour les 200 premiers cents :

for i in range(200):
    cents = (i // 100) + (i / 100) % 1
    expected = cents
    dollars = cents // 1
    cents %= 1
    half_dollars = cents // .50
    cents %= .50
    quarters = cents // .25
    cents %= .25
    dimes = cents // .10
    cents %= .1
    nickels = cents // .05
    cents %= .05
    pennies = cents // .01
    actual = dollars + half_dollars * .50 + quarters * .25 + dimes * .10 + nickels * .05 + pennies * .01
    print(f'{expected}: {actual}')

Pour votre santé mentale, je ne viderai pas les résultats, mais je partagerai quelques montants en dollars là où cet algorithme échoue :

0,06 $ (échec lors du calcul des nickels :.06 % .05 )
0,08 $ (échec lors du calcul des centimes :.03 % .01 )
0,09 $ (échec lors du calcul des nickels :.09 % .05 )
0,11 $ (échec lors du calcul des centimes :.11 % .1 )
0,12 $ (échec lors du calcul des centimes :.12 % .1 )
0,13 $ (même problème que 0,08 $)
0,15 $ (échec lors du calcul des centimes :.15 % .1 )
0,16 $ (même problème que 0,06 $)

Déjà, nous commençons à voir une partie alarmante de ces calculs devenir la proie d'erreurs d'arrondi. Dans les seuls 16 premiers cents, nous ne parvenons pas à produire un changement précis 50% du temps (en ignorant 0). Ce n'est pas génial !

De plus, de nombreuses erreurs commencent à se répéter. En d'autres termes, je soupçonne que ce problème s'aggrave avec plus de centimes car il y a plus de risques d'erreurs d'arrondi en cours de route. Bien sûr, je suis allé de l'avant et j'ai modifié le programme une fois de plus pour mesurer réellement le taux d'erreur :

errors = 0
for i in range(1000000):
    cents = (i // 100) + (i / 100) % 1
    expected = cents
    dollars = cents // 1
    cents %= 1
    half_dollars = cents // .50
    cents %= .50
    quarters = cents // .25
    cents %= .25
    dimes = cents // .10
    cents %= .1
    nickels = cents // .05
    cents %= .05
    pennies = cents // .01
    actual = dollars + half_dollars * .50 + quarters * .25 + dimes * .10 + nickels * .05 + pennies * .01
    errors += 0 if expected == actual else 1
print(f"{(errors/1000000) * 100}% ERROR")

Maintenant, je devrais préfacer que cet extrait de code compare les nombres réels en utilisant == ce qui est généralement considéré comme une mauvaise pratique. Par conséquent, il est possible que nous comptions quelques solutions "correctes" comme incorrectes. Cela dit, je pense que c'est une estimation assez bonne pour l'instant.

Lorsque je l'ai exécuté, j'ai constaté que 53,850699999999996 % de tous les calculs de changement étaient incorrects. Ironiquement, même mon calcul d'erreur avait un problème d'arrondi.

Devez-vous utiliser l'opérateur de reste sur les doubles ?

À ce stade, nous devons nous demander s'il est logique d'utiliser l'opérateur de reste sur les doubles en Java. Après tout, si les erreurs d'arrondi sont un tel problème, qui pourrait jamais faire confiance aux résultats ?

Personnellement, mon instinct me dirait d'éviter cette opération à tout prix. Cela dit, j'ai fait quelques recherches et il existe plusieurs façons de contourner ce problème. Par exemple, nous pourrions essayer d'effectuer de l'arithmétique dans une autre base en utilisant une classe qui représente les valeurs à virgule flottante sous la forme d'une chaîne d'entiers (comme la classe Decimal en Python ou la classe BigDecimal en Java).

Bien sûr, ce type de classes a ses propres problèmes de performances, et il n'y a aucun moyen d'échapper aux erreurs d'arrondi en base 10. Après tout, la base 10 ne peut pas représenter des valeurs comme un tiers. Cela dit, vous aurez beaucoup plus de succès avec l'opérateur restant.

En fin de compte, cependant, je n'ai pas personnellement rencontré ce scénario, et je doute que vous le fassiez non plus. Bien sûr, si vous êtes ici, c'est probablement parce que vous avez rencontré ce problème précis. Malheureusement, je n'ai pas beaucoup de solution pour vous.

En tout cas, merci d'être passé. Si vous avez trouvé cet article intéressant, envisagez de lui donner une part. Si vous souhaitez que plus de contenu comme celui-ci arrive dans votre boîte de réception, rendez-vous sur ma page de newsletter et laissez tomber votre adresse e-mail. De plus, vous pouvez soutenir The Renegade Coder en devenant mécène ou en faisant l'une de ces choses étranges.

Pendant que vous êtes ici, consultez l'un de ces articles connexes :

Ciseaux à papier de roche utilisant l'arithmétique modulaire
Encore une autre façon d'apprendre la récursivité
La différence entre les déclarations et les expressions

Sinon, merci d'avoir pris le temps de visiter mon site ! Je vous en suis reconnaissant.