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

So I’m basicly 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 is into it’s decimal expansion I have now two algorithms.

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

The second is:

Let be $ a \in \{1,2,\ldots\}$ 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 good but it is hard to control the accuarcy 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 seams I can controll with $ a$ that at least $ a-1$ decimal places are correct.

But I’m not sure if this will alwasy 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 basicly is does anybody have suggestion on improving the algorithm or is maybe another algorithm that does the job even better (a.i. fast)?