Bisection Search Like A (Human) Boss

Bisection search, or binary search for us developers, is a technique for finding the best value within a given range of values. This post describes tips for when you need to bisection search manually by hand (by “feel”), as opposed to when it can be automated by, say, a computer algorithm.

Bisection search, or binary search for us developers, is a technique for finding the best value within a given range of values.  Technically speaking, Wikipedia says the “bisection method in mathematics is a root-finding method that repeatedly bisects an interval and then selects a subinterval in which a root must lie for further processing.” This post describes tips for when you need to bisection search manually by hand (by “feel”), as opposed to when it can be automated by, say, a computer algorithm.

For example, say you’re very thirsty and need water fast so you pour yourself a glass of water: Pour too fast and it spills but too slow and it takes too long. You want to pour fast enough to quench your thirst as soon as possible but not so fast that it spills. The speed of pouring is your range of values (eg. slow to fast) and the consequences of the speed of pouring (how long it takes and if it spills) are your criteria to decide the best value. You try pouring the glass slowly and it’s too slow: Pour faster. You try pouring the glass faster and it spills: Pour slower but faster than the first time. You try pouring the glass “just right”: It’s fast enough and doesn’t spill. You’ve found the best pouring speed by bisection search!

Continue reading “Bisection Search Like A (Human) Boss”

How to Round to Arbitrary Precision in any Programming Language

How to Round to Arbitrary Precision in any Programming Language: an AMultiply your rounding number by 10^y where y is the precision to round to. Call your language’s built-in round() method on this number. Divide the result by 10^y. Easy peasy. It also makes it easier to implement different rounding methods because you’re always dealing with the digit at the same location in the number.

How to Round to Arbitrary Precision in any Programming Language: Multiply your rounding number by 10^y where y is the precision to round to. Call your language’s built-in round() method on this number. Divide the result by 10^y. Easy peasy. It also makes it easier to implement different rounding methods because you’re always dealing with the digit at the same location in the number.

In javascript:

Then there’s Math.round() which you may not have or may not want to use and, if you’re rounding, at all, you’ll inevitably find yourself looking at various rounding methods. Since Math.round(), and usually all default round() methods in most programming languages, use traditional “half up” rounding, you may find you need a different method, like banker’s rounding which is “half to even”.

To accomplish a different rounding method, create your own round() function, apply the appropriate power to your number. Then, subtract the integer portion of the number. You are left with the fraction portion of your number: This gives you the rounding digit as your final number. With this number, you can then decide whether to truncate the original number or add 1. Once you’re done that, you can then remove the power manipulation you did in the first step and now you’re left with the final rounded number.

In javascript:

The functions Math.floor() (floor and ceiling), Math.pow() (exponentiation), and the modulus operator, are usually already available for most modern languages, under the same names, and don’t really have a need to be re-implemented compared to the need to re-implement rounding. Implementing your own functions for these is usually relatively trivial, however.

There you go! Arbitrary precision rounding in any programming language and, thrown in for good measure, how to implement a different rounding method to boot!