[Solved]: How do calculators convert from decimal to fraction?

Problem Detail: 

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?

Asked By : erdekhayser

Answered By : Gilles

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.}

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/43448

 Ask a Question

 Download Related Notes/Documents