Algorithms – Page 3 – The Renegade Coder

Remember learning to round in grade school? Me too! The only problem is I don't use the idea very often. As a result, I don't always remember how to round a number in programming contexts like Python. Luckily, I've pieced together a little article for myself. Hopefully, you get some value out of it as well. As it turns out, there are a ton of ways to a round a number in Python. For instance, we could truncate the fraction altogether using a cast to int: `int()`python. Of course, there are more sophisticated options like the `round()`python function which rounds to the nearest even number for midway values like 7.5. That said, feel free to roll your own solution. I built my own "round-half-up" solution using the ternary operator: `int(x + .5) if x >= 0 else int(x - .5)`python. Check out the rest of the article for details. Problem Description Rounding is one of those operations we sort of take for granted in everyday life. For instance, I use Acorns which rounds up my purchases to the nearest whole dollar and invests the excess on my behalf. Unfortunately, rounding to whole numbers isn't an obvious operation in programming. There's no operator for rounding in most languages, and I doubt there ever will be. Instead, we often have to lean on a library or roll own one. To make things more complicated, rounding isn't always an obvious operation. For example, how do we know when to round up or down? The way I was taught in school was to round numbers up (away from zero) when the decimal is .5 or greater. As it turns out, there are a lot of different ways to round a whole number. In fact, I found this interesting article in the Electronic Engineering Times which outlines several different rounding methods. To summarize, here are a few options: Round-toward-nearest: round to the closest number (but, what about .5?)Round-half-up: round-toward-nearest where .5 rounds away from zero (e.g 4.5 rounds to 5)Round-half-down: round-toward-nearest where .5 rounds toward zero (e.g. 4.5 rounds to 4) Round-half-even: round-toward-nearest where .5 rounds toward the nearest even number (e.g. 4.5 rounds to 4 while 5.5 rounds to 6)Round-half-odd: round-toward-nearest where .5 rounds toward the nearest odd number (e.g. 4.5 rounds to 5 while 5.5. rounds to 5)Round-alternate: round-toward-nearest where .5 alternates between rounding up and down over time (e.g. 4.5 rounds to 5 then 5.5 rounds to 5)Round-random: round-toward-nearest where .5 rounds up or down randomly (e.g 4.5 could round to either 4 or 5)Round-cieling: round all decimals toward positive infinity (e.g 4.3 rounds to 5 while -4.7 rounds to -4)Round-floor: round all decimals toward negative infinity (e.g. 4.7 rounds to 4 while -4.7 rounds to -5)Round-toward-zero: round all decimals toward zero (e.g. 4.7 rounds to 4 while -4.7 rounds to -4)Round-away-from-zero: round all decimals away from zero (e.g. 4.3 rounds to 5 while -4.3 rounds to -5) Clearly, there are a lot of ways to round numbers. For the purposes of this article, we'll be using the "round-half-up" method. In other words, numbers like 3.5, 5.5, and -2.5 will all round up to 4, 6, and -3, respectively. Solutions In this article, we'll take a look at a few different ways of rounding numbers in Python. As always, we'll start with the straightforward or brute force solutions. Then, we'll move our way through more common solutions. Rounding by Truncation One way to round a number is to trim the decimal place off through truncation: x = int(5.3) # stores 5 In this example, `x`python will store 5 as we trim off the .3. If we were to change the example value to something should round up, we'll be disappointed: x = int(5.7) # stores 5 Clearly, this isn't the "round-half-up" solution we discussed above, but it's a nice shortcut if we just need to remove the decimal place (i.e. "round-toward-zero"). That said, the simplicity of this solution gives us a nice benefit: truncation works for negative numbers as well: x = int(-5.7) # stores -5 Of course, if we want a true "round-half-up" solution, we'll need to try something else. Rounding by Control Flow If we think about how "round-half-up" works, then we can probably piece together some if statements to get it done: x = 5.3 fraction = x - int(x) if abs(fraction) >= .5: offset = 1 - fraction x = x + offset else: x = x - fraction Here, we can compute the fractional portion of a number by using our previous truncation solution. In other words, we can subtract the truncated value from the actual value to get the fraction. In this case, `int(x)`python will return 5 which we'll subtract from 5.3. As a result, `fraction`python stores .3 (ish). Then, we can use that fraction to perform some control flow. For instance, if the absolute value of `fraction`python is greater than or equal to .5, we know we need to round up. Here, the absolute value accounts for the fact that `fraction`python could be positive or negative. Otherwise, we might have to write a slightly more annoying if statement. If you want to learn more about computing absolute value in Python, I have a whole separate article on that. At any rate, to round a number up, we need to compute the distance to the next number which we call `offset`python. We can compute that by subtracting `fraction`python from 1. Now, it's just a matter of adding the offset to `x`python, and we're done. On the other hand, if we find that the absolute value of `fraction`python is actually less than .5, we can subtract that fraction directly from `x`python. This will work regardless of if `x`python is positive or negative. If we want to go the extra mile, we could cast `x`python to an integer. That said, this should get the job done—barring any pesky rounding errors. Rounding by Arithmetic Another really clever way to "round-half-up" is to take advantage of the truncation solution from above with a slight modification: x = int(5.3 + .5) Here, we've added .5 directly to `x`python. If the fractional portion of `x`python happens to be .5 or greater, `x`python will roll over into the next number. Then, when we truncate `x`python, we'll have successfully rounded it. On the other hand, if the fractional portion of `x`python is below .5, the whole number portion of `x`python will stay the same. As a result, truncating `x`python will have the effect of rounding the number. Unfortunately, this solution won't work when `x`python is negative. To handle that case, we'll need some sort of branch. Because I'm lazy, and I like one-liners, I'm going to opt for the ternary: x = 5.3 int(x + .5) if x >= 0 else int(x - .5) Now, if `x`python is negative, we'll subtract .5 rather than adding it. If there's a more clever solution, let me know in the comments. Rounding With the `round()`python Function If writing a rounding algorithm by hand is out of the question, Python actually provides a built-in rounding function: round(5.3) Unfortunately, it's behavior doesn't quite map out to our "round-half-up" algorithm. Instead, it's a bit more complicated. Let's take a look at a few examples: >>> round(.5) 0 >>> round(-.5) 0 >>> round(1.5) 2 >>> round(2.5) 2 >>> round(3.5) 4 >>> round(-1.5) -2 >>> round(-2.5) -2 >>> round(-3.5) -4 If we look back at our list of rounding algorithms, we'll find that the Python developers have actually implemented the "round-half-even" algorithm. When I did some research on this algorithm, I found that it's sometimes called bankers rounding—the more you know! Honestly, there's not much else to say about this solution. However, it's important to note that the round function in Python can actually work for floating point values as well. For example, we can round out to the tenths place as follows: >>> round(3.52, 1) 3.5 How cool is that? Performance With the solutions out of the way, let's take a look at how they perform. To do that, we'll need to capture each solution in a string: setup = """ x = 2.5 """ truncation = """ int(x) """ control_flow = """ fraction = x - int(x) if abs(fraction) >= .5: offset = 1 - fraction x + offset else: x - fraction """ arithmetic = """ int(x + .5) if x >= 0 else int(x - .5) """ banker = """ round(x) """ With our strings ready to go, all we need to do is load in the `timeit`python library and launch our tests: >>> import timeit >>> min(timeit.repeat(setup=setup, stmt=truncation)) 0.1537370000005467 >>> min(timeit.repeat(setup=setup, stmt=control_flow)) 0.43060659999900963 >>> min(timeit.repeat(setup=setup, stmt=arithmetic)) 0.2925704000008409 >>> min(timeit.repeat(setup=setup, stmt=banker)) 0.25559939999948256 Perhaps unsurprisingly, truncation wins in the speed contest. However, the built-in `round()`python function is actually quite quick! I imagine that's because the function is implemented in a lower level language. As always, take these measurements with a grain of salt. I ran each of them on a Windows 10 machine with Python 3.7.3. Also, if you're interested in this performance testing process, I have a whole article about it. Challenge When it comes to rounding, there are a ton of different algorithms. And for each algorithm, there are probably thousands of contexts where they are used. Naturally, I thought it would be fun to make you apply the rounding algorithm in one of those contexts, but I figured it might be more fun to dig into other rounding algorithms instead. For this challenge, I'm asking you to implement the bankers rounding algorithm (or you can come up with your own like I "did"). If you choose to stick with the bankers rounding algorithm, wrap it in a function and test it on the following inputs: DescriptionInputOutputNear Zero0.50Standard Case0.71Standard Case1.21Even Round Up1.52Even Round Down2.52Even Round Up Negative-1.5-2Even Round Down Negative-2.5-2 Then, when you're ready, share your solution on Twitter! Don't forget to tag your solution #RenegadePython. To kick things off, here's my solution using the floor and ceiling functions of the math class: https://twitter.com/RenegadeCoder94/status/1269750560368078848?s=20 I'm excited to see what you come up with! A Little Recap At long last, we've reached the end of this post. As always, here's a list of each solution used in this article: x = 17.1 # Truncation int(x) # Control flow rounding fraction = x - int(x) if abs(fraction) >= .5: offset = 1 - fraction x + offset else: x - fraction # Arithmetic rounding int(x + .5) if x >= 0 else int(x - .5) # Functional rounding round(x) If you got any value out of this article, consider supporting The Renegade Coder by heading over to my list of ways to help grow the site. Otherwise, consider checking out some of these Python resources on Amazon (ad): Doing Math with Python: Use Programming to Explore Algebra, Statistics, Calculus, and More!Python Playground: Geeky Projects for the Curious Programmer In addition, you might find value in the following related posts: How to Compute Absolute Value in PythonThe Remainder Operator Works on Doubles in Java With all that said, thanks for stopping by. Hope to see you back here soon!