Code – Page 25 – The Renegade Coder

I’ve been teaching at OSU for nearly two years, and it always astounds me how much I learn from my students. For instance, in the past, I’ve had students write strange pieces of code that I didn’t understand. At this point, even after 300+ blog posts, several YouTube videos, and even collecting code snippets from over 100 languages, you’d think I’d seen it all. Well, recently, I saw a student using the remainder operator (%) on doubles, and I haven't really been the same since. Remainder vs. Modulus Operator Before I get into the story, I wanted to come along and make a distinction between the remainder operator and the modulus operator. In Java, there is no modulus operator. Instead, % is the remainder operator. For positive numbers, they are functionally equivalent. However, once we start playing with negative numbers, we'll see a surprising difference. I've talked about this difference a bit already in an article about RSA encryption. That said, I found another great source which compares the "modulo" operator in various languages including Java, Python, PHP, and C. To summarize, the remainder operator works exactly as we'd expect it to function with positive numbers. For example, if we take 3 % 5, we'd get 3 because 5 doesn't go into 3 at all. If we start playing around with negative numbers, the results are similar. For instance, if we take 3 % -5, we'd still get three because that's all that is left over. Meanwhile, if we flip the script and make the dividend negative—after all, remainder is a byproduct of division—we'd start to see negative remainders. For example, -3 % 5 returns -3. Likewise, -3 % -5 returns -3. Notice how in all these examples we get the same results with some variation on the sign. In other words, with the remainder operator, we aren't too concerned with signs. All we want to know is how many times one number goes into another number. Then, we peek at the dividend to determine the sign. On the flip side, the modulo operator has quite a bit more nuance. For starters, the operand on the right side determines the range of possible return values. If that value is positive, the result will be positive. That's a bit different from our remainder operator. Meanwhile, the left operand determines the direction we cycle through the range of possible values. Naturally, this lines up perfectly with the remainder operator when both values have the same sign. Unfortunately, they're completely different in any other circumstance: ExpressionJava (Remainder)Python (MOD)3 % 5333 % -53-2-3 % 5-32-3 % -5-3-3 If you're interested in learning more about modular arithmetic, another student inspired me to write an article on the game Rock Paper Scissors using modular arithmetic. Remainder Operator on Doubles When we think about the remainder operator, we often assume that it works exclusively with integers—at least up until recently that was my understanding. As it turns out, the remainder operator actually works on floating point numbers, and it makes sense. Inspiration Earlier this month, I was working with a student on a lab which asked them to write a coin change program. Specifically, this program was supposed to accept a number of cents from the user and output the denominations in American currency (e.g. dollars, half dollars, quarters, dimes, nickels, and pennies). If you're thinking about how you would solve this problem, I'll give you a hint: you can take a greedy approach. In other words, pick the largest coin first and compute how many of them divide into your current number of cents. If you do it right, you don't even need an control flow. However, you can clean up your code a bit with an array and a loop. Since I'm too lazy to write up a solution in Java, here's what it might look like in 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}') At any rate, I had a student who interpreted cents as dollars and cents. In other words, they let their user enter dollar amounts like $1.50 rather than 150 cents. To be fair, that isn't a huge deal. All we have to do is multiply the dollar amount by 100 and add the leftover cents to get an integer. However, that's not what this student did. Instead, they treated each denomination as a double (i.e. a real number). Then, they proceeded to use the remainder operator without any consequences. Simply put, I was dumbfounded. After all, how could that possibly work? You only calculate a remainder on long division, right? Otherwise, you're left with a decimal and nothing left over—or so I thought. Using Doubles If we were to rewrite the program above using dollars and cents, we might have something that looks like the following: 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}') And if we run this, we'll get exactly the same result as before: one dollar and one half dollar. How is that possible? As it turns out, calculating the remainder using decimals is perfectly valid. All we need to do is compute how many times our dividend goes completely into our divisor. For example, .77 % .25 would "ideally" yield .02 because that's as close as we can get to .77 without going over. Caveats After finding out that it's possible to take the remainder of a decimal, I immediately wondered why I hadn't known about it sooner. Of course, a quick Google search shows you all sorts of erroneous behavior that can arise. For instance, in the previous example, I claimed that .02 would be the remainder of .77 and .25, and it would be, kinda. See, in most programming languages, the default floating point values have a certain precision that is dictated by the underlying binary architecture. In other words, there are decimal numbers that cannot be represented in binary. One of those numbers just so happens to be the result of our expression above: >>> .77 % .25 0.020000000000000018 When working with real numbers, we run into these sort of issues all the time. After all, there are a surprising number of decimal values that cannot be represented in binary. As a result, we end up with scenarios where rounding errors can cause our change algorithm to fail. To prove that, I rewrote the solution above to compute change for the first 200 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}') For your sanity, I won't dump the results, but I will share a few dollar amounts where this algorithm fails: $0.06 (fails when computing nickels: .06 % .05)$0.08 (fails when computing pennies: .03 % .01)$0.09 (fails when computing nickels: .09 % .05)$0.11 (fails when computing dimes: .11 % .1)$0.12 (fails when computing dimes: .12 % .1)$0.13 (same issue as $0.08)$0.15 (fails when computing dimes: .15 % .1)$0.16 (same issue as $0.06) Already, we're starting to see an alarming portion of these calculations fall prey to rounding errors. In the first 16 cents alone, we fail to produce accurate change 50% of the time (ignoring 0). That's not great! In addition, many of the errors begin to repeat themselves. In other words, I suspect that this issue gets worse with more cents as there are more chances for rounding errors along the way. Of course, I went ahead and modified the program once again to actually measure the error rate: 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") Now, I should preface that this code snippet compares real numbers using == which is generally considered bad practice. As a result, it's possible we count a few "correct" solutions as incorrect. That said, I think this is a good enough estimate for now. When I ran it, I found that 53.850699999999996% of all change calculations were incorrect. Ironically, even my error calculation had a rounding issue. Should You Use the Remainder Operator on Doubles? At this point, we have to wonder if it makes sense to use the remainder operator on doubles in Java. After all, if rounding errors are such an issue, who could ever trust the results? Personally, my gut would say avoid this operation at all costs. That said, I did some digging, and there are a few ways around this issue. For instance, we could try performing arithmetic in another base using a class which represents floating point values as a string of integers (like the Decimal class in Python or the BigDecimal class in Java). Of course, these sort of classes have their own performance issues, and there's no way to get away from rounding errors in base 10. After all, base 10 can't represent values like one third. That said, you'll have a lot more success with the remainder operator. At the end of the day, however, I haven't personally run into this scenario, and I doubt you will either. Of course, if you're here, it's likely because you ran into this exact issue. Unfortunately, I don't have much of a solution for you. At any rate, thanks for stopping by. If you found this article interesting, consider giving it a share. If you'd like more content like this to hit your inbox, head on over to my newsletter page and drop your email address. In addition, you can support The Renegade Coder by becoming a Patron or doing one of these weird things. While you're here, check out one of these related articles: Rock Paper Scissors Using Modular ArithmeticYet Another Way to Learn RecursionThe Difference Between Statements and Expressions Otherwise, thanks for taking some time to check out my site! I appreciate it.