5
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Most likely calculators store the fraction directly, and when needing to print in decimal (or use it in an expression somewhere), it is evaluated. $\endgroup$ – Ryan Jun 10 '15 at 0:36
  • $\begingroup$ A Google search on "convert decimal to fraction" will answer your question $\endgroup$ – Bob Brown Jun 10 '15 at 0:42
  • $\begingroup$ I ended up here while trying to use Google to find the answer to this question. So far I have been unsuccessful. I would appreciate if @Bob or someone could share answers found with more skillful searching, but I'll keep trying. When grading calculus exams I ran into an example making me wonder if a continued fraction algorithm is used on TI graphing calculators. A student asked her calculator to convert $\frac23(37\sqrt{37}-10\sqrt{10})$ to a fraction and it said $\frac{453551}{3517}$, which is the 7th convergent of the continued fraction, right before a large denominator of $144$. $\endgroup$ – Jonas Meyer Mar 10 '16 at 18:51
  • $\begingroup$ That doesn't necessarily suggest that it used a continued fraction algorithm, but continued fractions at least can help explain why the calculator thought it was close enough to give it as an answer. $\endgroup$ – Jonas Meyer Mar 10 '16 at 19:14
  • $\begingroup$ In fact, your algorithm won't work at all. It will occur an error (0/0). $\endgroup$ – Huy Ngo Feb 22 '17 at 14:38
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.