float result for two smallest integer division

Question

I want to know the two integer number that division of them is this float. for example

x / y = 1.333333333....

$x$ and $y$ can be 8, 6 and 4, 3 ... i need x = 4 and y = 3.

For next example my number is 1.41 what are x and y? how can i find them ?

Answer 1

As in J.D.'s edit the best method is to use continued fractions :

At each step (for the evaluation of $x$) :

• note the integer part $j\leftarrow \lfloor x\rfloor$ (illustrated in blue)
• compute the new fraction $f$ as illustrated :
  • write the previous fraction
  • multiply the numerator and denominator by $j$
  • add the numerator and denominator of the previous previous fraction (starting with $\frac 10$)
• evaluate the fractional part $x\leftarrow x-j$
• stop when $x$ becomes $0$ or at least very small (depending of the precision of your evaluation) or when you decide too...
• else compute $x$'s multiplicative inverse $x\leftarrow \frac 1x$ and repeat

(as an alternative you could keep the 'rounded' integer and subtract it instead of the integer part)

Complete process for $x=1.41$ :
the succession of fractions is $\frac 10\to\frac 11\to\frac 32\to \frac 75\to \cdots\to \frac {141}{10}$
(note how these fractions 'shift' in the second fraction from the right)

$ \begin{array} {l|r|ccccc} x&j&&&&&f\\ \hline\\ 1.41 & \color{#0000ff}{1} & \color{#0000ff}{1}&=&\frac {\color{#0000ff}{1}}1&=&\frac 11\\ 1/0.41=2.43902\cdots & \color{#0000ff}{2} &1+\cfrac 1{\color{#0000ff}{2}}&=& \frac {1\cdot \color{#0000ff}{2}+1}{1\cdot \color{#0000ff}{2} +0}&=&\frac 32\\ 1/0.4390\cdots=2,2777\cdots & \color{#0000ff}{2}&1+\cfrac 1{2+\cfrac 1{\color{#0000ff}{2}}}&=& \frac {3\cdot \color{#0000ff}{2}+1}{2\cdot \color{#0000ff}{2} +1}&=&\frac 75\\ 1/0.2777\cdots=3.6 &\color{#0000ff}{3}&1+\cfrac 1{2+\cfrac 1{2+\cfrac 1{\color{#0000ff}{3}}}}&=& \frac {7\cdot \color{#0000ff}{3}+3}{5\cdot \color{#0000ff}{3} +2}&=&\frac {24}{17}\\ 1/0.6=1.6666\cdots & \color{#0000ff}{1}&\cdots&=&\frac {24\cdot \color{#0000ff}{1}+7}{17\cdot \color{#0000ff}{1} +5}&=&\frac {31}{22}\\ 1/0.6666\cdots=1.5\cdots & \color{#0000ff}{1}&\cdots&=& \frac {31\cdot \color{#0000ff}{1}+24}{22\cdot \color{#0000ff}{1} +17}&=&\frac {55}{39}\\ 1/0.5=2 & \color{#0000ff}{2}&\cdots&=& \frac {55\cdot \color{#0000ff}{2}+31}{39\cdot \color{#0000ff}{2}+22}&=&\frac {141}{100}\\ \text{stop!} &\\ \end{array} $

Since we started with a rational number the process ended in a finite number of steps (returning the exact $\frac {141}{100}$ here). For a quadratic number (like $\sqrt{3}+1$) the j integers produced will repeat. For none of these the $j$ number produced won't repeat (up to machine precision of course!).

Hoping this helped too,

Answer 2

What you're looking for is the irreducible fraction. I will quote from the Wiki page:

A fraction that is reducible can be reduced by dividing both the numerator and denominator by a common factor. It can be fully reduced to lowest terms if both are divided by their greatest common divisor. In order to find the greatest common divisor, the Euclidean algorithm may be used. Using the Euclidean algorithm is a simple method that can even be performed without a calculator.

So you need to divide out both $x,y$ by the greatest common divisor (GCD) of $(x,y).$ There is a simple fast algorithm for computing GCD: Euclidean algorithm.

For example, if $x = 8$ and $y = 6,$ then compute $d = \gcd(8, 6) = 2,$ and the reduced pair is then $x/d = 4, y/d = 3.$

For $1.41,$ start with $x = 141, y = 100.$ Since $\gcd(141, 100) = 1,$ the fraction $x/y$ is in reduced form already.

---

As gt6989b pointed out, my answer above assumes you have $x$ and $y.$ A better approximation is via continued fractions. See here and here.

Answer 3

To make this cover all possible cases, to convert a decimal into a fraction, you must have an infinitely repeating decimal pattern starting after some digit (e.g. 1.23454545... will work but $\pi$ will not because it's decimal pattern does not infinitely repeat).

If your repeating pattern is 0, e.g. 1.41=1.4100.., use Mariano Suárez-Alvarez's idea in the comments to your question - take all digits without decimal point as the first integer (i.e. 141 here) and take $10^n$ where $n$ is the number of digits after the decimal point as the second integer (here $10^2=100$ and use J.D.'s answer with the GCD to simplify the fraction (in our example, $141/100$ does not simplify).

If your pattern is not 0 (e.g. 1.2345[45] as above), then break the fraction into 2 parts, isolating the repeating pattern, and scale it by the right power of 10 to make it start at the first decimal point, i.e.

$1.23[45] = 1.23 + 0.45[45]/100.$

In that form, the infinitely repeating decimal can be written as a fraction where the top is the repeating pattern (here 45) and the bottom is the number of 9's equal to the digits in the pattern (here 2 digits, so 99). So 0.45[45] = 45/99 and overall you get [transforming the first part using the previously-given algorithm]:

$1.23[45] = \frac{123}{100} + \frac{45}{99 \cdot 100}$, and now add fractions appropriately and use GCD algorithm below to simplify common fractions.

Answer 4

Given a real number, $r>0$, for any positive integer $N$, a simple pigeon hole argument shows that $r$ can be approximated by a rational $p/q$ so that $q>N$ and $$ \left|\;\frac{p}{q}-r\;\right|<\frac1{q^2} $$ Continued Fractions will always give such an approximation.

Furthermore, if $r\not\in\mathbb{Q}$ and the approximation is such that $$ \left|\;\frac{p}{q}-r\;\right|<\frac1{2q^2} $$ then $p/q$ is arrived at using Continued Fractions.