2
$\begingroup$

I already asked this question over on Mathematics and got the suggestion to ask it here.

So I'm basically implementing a number type that can represent all fractions and was working on an algorithm to compute the decimal expansion for said fractions.

Let's say we have the reduced fraction $\frac{n}{m}$. For converting it into its decimal expansion I now have two algorithms.

The first algorithm is simply long division to calculate the decimal expansion up to a given number of decimal places.

The second is:

Let $a \in \{1,2,\ldots\}$ be a specifier for accuracy.

Calculate: $$ \begin{align} p &= \lceil \log_{10}(m) \rceil + a \\\\ f &= \lfloor \frac{10^p}{m} \rfloor \\\\ v &= n \cdot f \end{align} $$ Then in $v$ insert the decimal comma at the correct place or add 0. with leading zeros.

Which works well but it is hard to control the accuracy with $a$. For example if I have the fraction $\dfrac{884279719003555}{281474976710656} \approx \pi$ then I get:

 a | dec. exp.
---|--------------------------------
     v acc 0
 1 | 3.0949790165124425
       v acc 1
 2 | 3.13919300246262025
        v acc 1
 3 | 3.14096156190062736
             v acc 7
 8 | 3.14159264580768862709685
              v acc 8
 9 | 3.14159265288192637912529
                  v acc 12
10 | 3.141592653589350154328134
                  v acc 12
11 | 3.141592653589350154328134
                  v acc 12
12 | 3.141592653589350154328134
                     v acc 15
f  = 3.1415926535897931159979634...

pi = 3.1415926535897932384626433...

So its seems I can control with $a$ that at least $a-1$ decimal places are correct.

But I'm not sure if this will always be the case.

Also, I benchmarked both algorithms, and the second is more than 5 times faster. So I really want it to be controllable.

Method Mean Error StdDev
first 4,929.2 ns 24.34 ns 20.33 ns
second 848.8 ns 4.00 ns 3.54 ns

So my question basically is: does anybody have suggestions on improving the algorithm or maybe another algorithm that does the job even better (a.i. fast)?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
4
$\begingroup$

All we need is a function $f$ that gives the whole part of a fraction. One can define this one using integer division:

$$f(a, b) = \lfloor a / b\rfloor$$

Finally let's assume we have routine $g(a, b)$ that reduces a fraction to its simplest form. This can be done with the Euclidean algorithm.

Let's first take the integer part of a fraction out using $f$, and reduce our fraction using $g$, giving us $\frac{a}{b} < 1$. Then we can repeatedly ask for the next decimal $d$ and continue with $10\cdot \frac{a}{b} - d$:

  1. $d := f(10a, b)$
  2. $a, b := g(10a - b\cdot d, b)$

This algorithm will perfectly give you all digits ad infinitum, and $g$ makes sure the numbers stay small and manageable.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Thanks for the suggestion. I implemented it and benchmarked it. Sadly it is much slower: (for 20 decimal places) over 29 times slower than the log/exp algorithm and over 5 times slower than long divison (which is already perfectly controllable and precise); (for 200 decimal places ) over 11 times slower than log/exp and over 3 times slower than long division. $\endgroup$
    – Ackdari
    Apr 24, 2020 at 14:25
  • 1
    $\begingroup$ @Ackdari Well your other algorithms will overflow or simply give wrong results for large enough decimal places. You can speed up the above algorithm by doing multiple digits at a time, e.g. replace $10$ by $1000$ to get three digits at a time. You just have to make sure that $10^k\cdot a$ doesn't overflow whatever integer type you're using. $\endgroup$
    – orlp
    Apr 24, 2020 at 14:29
  • $\begingroup$ Overflow is not a problem since I use an interger type with unlimited precision for the nominator and denominator. The idea with not using $10$ but a power of $10$ is accually almost as fast as log/exp and better for controllability (since it is definityl correct). So just $v = \lfloor \frac{a}{b} \cdot 10^\lambda \rfloor$, where $\lambda$ is the amount of decimal places and then inserting the decimal comma/point $\endgroup$
    – Ackdari
    Apr 24, 2020 at 16:49
  • $\begingroup$ @Ackdari Ah well if you have access to an unlimited precision integer type you can just use that. The above algorithm also works with just finite precision integers though (which are much faster). $\endgroup$
    – orlp
    Apr 24, 2020 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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