0

I have a fraction $\dfrac{a}{b}$ where $a$ and $b$ are both two large integers with $30$ digits each. I wish to approximate this fraction with a new fraction $\dfrac{c}{d}$ where $c$ and $d$ are both $10$-digit integers.

I came up with two ways:

  1. divide $a$ and $b$ repeatedly by $10$ until they both contain $10$ digits each.
  2. Get the decimal representation of $\dfrac{a}{b}$ and take the first $10$ digits. Divide this by $10^n$ where $n$ is the amount of digits in the first $10$ digits which come after the decimal point. So if the decimal representation is $125.65471263236454545654$ then the approximation is: $$\dfrac{1256547126}{10^7} = 125.6547126$$

Are both methods equivalent? Which one is better/more precise?

entrelac
  • 4,681
Héctor van den Boorn
  • 549

1 Answers1

2

To add emphasis, the simple continued fraction of a rational number is finite. It can be found using computer operations that exclusively use integers. For your purpose, the most important part is that, if your rational number is $r,$ and we have consecutive "convergents" $p/q$ and $s/t,$ then $$ \left| r - \frac{p}{q} \right| \leq \frac{1}{qt} < \frac{1}{q^2}. $$ This means that, for $q > 10^9,$ we get $\left| r - \frac{p}{q} \right| < 10^{-18}$

https://en.wikipedia.org/wiki/Continued_fraction#Finite_continued_fractions

Alright, gp-pari has continued fractions. I wrote my own version in C++ with GMP, all I really wanted was the extended GCD, that is, given integers $a,b$ with $\gcd(a,b) = 1,$ find integers $x,y$ so $ax+by = 1.$

Where was I: to do many such fractions, all you need to do is implement the Euclidean Algorithm, with the extra step that, every time you calculate an intermediate partial quotient command "m / n" which is $$ \left\lfloor \frac{m}{n} \right\rfloor $$ you update the "convergent."

Will Jagy
  • 139,541