<p dir="ltr"><br>
On Jul 29, 2013 1:37 PM, "Serhiy Storchaka" <<a href="mailto:storchaka@gmail.com">storchaka@gmail.com</a>> wrote:<br>
><br>
> 29.07.13 19:09, MRAB написав(ла):<br>
><br>
>> I'm surprised that Fraction(1/3) != Fraction(1, 3); after all, floats<br>
>> are approximate anyway, and the float value 1/3 is more likely to be<br>
>> Fraction(1, 3) than Fraction(6004799503160661, 18014398509481984).<br>
><br>
><br>
> >>> def approximate_fraction(f):<br>
>     prev_numer, numer = 0, 1<br>
>     prev_denom, denom = 1, 0<br>
>     r = f<br>
>     while True:<br>
>         i = math.floor(r)<br>
>         prev_numer, numer = numer, i * numer + prev_numer<br>
>         prev_denom, denom = denom, i * denom + prev_denom<br>
>         if i == r or numer / denom == f:<br>
>             break<br>
>         r = 1 / (r - i)<br>
><br>
>     return Fraction(numer, denom)<br>
><br>
> >>> approximate_fraction(1/3)<br>
> Fraction(1, 3)<br>
> >>> approximate_fraction(1e-17)<br>
> Fraction(1, 100000000000000000)<br>
> >>> approximate_fraction(math.pi)<br>
> Fraction(245850922, 78256779)<br>
><br>
> I guess the Fraction constructor is more faster than this function.</p>
<p dir="ltr">You might be able to speed it up a bit with numpy and the observation that the update is a matrix multiplication. But I don't think that you can get away from it being an iterative algorithm.<br>
</p>