How do calculators convert from decimal to fraction?

Question

Sorry if this question is either obvious or ignorant. I am a high school student with only the computer science knowledge I have taught myself.

Calculators have a function that can convert numbers from decimal to fractional equivalents. For example, 0.5 becomes 1/2, and 0.666666667 becomes 2/3.

I doubt that the calculator has these values kept in storage to look up, so there must be an algorithm for this to be determined.

The simplest possible algorithm I can imagine would resemble this:

for (double i = 0; i < someLimit; i++){
    for (double j = 0; j < someLimit; j += 1){
        if (i / j == decimal){ //return these values }
    }
}

This seems far too inefficient to be the algorithm used by calculators. Even on low power scientific calculators, this operation completes quickly.

How do calculators calculate the fractional equivalent of a decimal?

Answer 1

I don't know what calculators actually use, but there are definitely better algorithms than your brute force search.

There are several notions of “best approximation” of a real number by a rational. Depending on how you rate the benefit of a good approximation compared to the cost of a large denominator, you get different notions.

One of these is the best approximation with a bounded denominator: given $x \in \mathbb{R}$ (real to approximate) and $n \in \mathbb{N}^*$ (denominator bound), find $p/q$ with $p \in \mathbb{Z}$, $q \in \mathbb{N} \cap [1,n]$ that minimizes $x-p/q$. The sequence of best approximations for increasing values of $n$ turns out to be relatively easy to calculate and to have other nice mathematical properties: it's the continued fraction expansion of $x$. The continued fraction expansion is a way to construct an infinite sequence of rationals that converges to $x$, and its terms are exactly¹ the best bounded-denominator approximations of $x$. The series is easy to calculate incrementally.

In a calculator, you don't necessarily want the best approximation in that sense: what denominator bound would you pick? If you pick one that's too low, you'll miss some “interesting” rationals. If you pick one that's too large, you end up treating basically everything as some large integer divided by a power of ten.

¹ _{Except for some boundary effects when $x$ is rational, see a reference for details.}

Answer 2

Back in the CS pleistocene, early calculators like the HP35 (1972-1975) had a chip that supported bit shift, add, subtract, test for negative, and some memory. In those days, many of the mathematical operations like multiplication, division, trig and hyperbolic trig functions were done with what were known as CORDIC (COordinate Rotation DIgital Computer) algorithms. Some people find this interesting enough to look up: how on earth do you compute sines with such a limited collection of operations?

Now, of course, a modern calculator (or a smart phone, or, probably even a thermostat) has computational power that you couldn't have bought at any price 40 years ago, so I suspect that your suggested answer might very well be what they use today, perhaps with the embedded Java Virtual Machine that's part of the calculator.