Exact float conv

[adegert]

An alternative to the current algorithm + new function rational_limit_denominator

[begriffs]

Can you tell me more about this algorithm? What does it improve, and does it have any disadvantages compared with the existing one?

[adegert]

Am So., 24. Nov. 2019 um 18:09 Uhr schrieb Joe Nelson < notifications@github.com>:

@begriffs commented on this pull request.

In pg_rational.c https://github.com/begriffs/pg_rational/pull/13#discussion_r349935200:

@@ -464,6 +470,81 @@ rational_larger(PG_FUNCTION_ARGS) ** INTERNAL *** */

+/* +limit_denomintor() uses continued fractions to convert the +rational n/d into the rational n'/d' with d' < max_denominator +and n' <= INT32_MAX and smallest |d/n-d'/n'|.

Is there a paper or a description of this algorithm you can link to in the comment?

You can find the calculation formula for continued fractions in https://en.wikipedia.org/wiki/Continued_fraction#Calculating_continued_fraction_representations the recursive formula for numerator and denominator is explained in https://en.wikipedia.org/wiki/Continued_fraction#Infinite_continued_fractions_and_convergents and the program uses variables p/q instead h/k. This algorithm is also used in the Python fractions module https://github.com/python/cpython/blob/036fe85bd3e6cd01093d836d71792a1966f961e8/Lib/fractions.py#L227 Calculation ends when either the numerator or the denominator would get too big, or if we are done because the continued fraction is finished (its finite) or the fraction is equal to the target number (this can happen earlier because of finite numerical precision). Then the secondary convergent with the largest possible numerator and denominator (with respect to the limits) is calculated and taken as result if the error is smaller than for the fraction calculated above ( https://en.wikipedia.org/wiki/Continued_fraction#Semiconvergents). This algorithm is a bit slower than the original one (depends on the number range, about 20% - 50% slower according to my measurements), but more exact and numerically quite stable (try to look at what happens with z in the original algorithm when the iteration gets close to the maximum achievable numerical precision). Please feel free to put this text or parts of it into the C function comment if you are interested.

[begriffs]

Thanks for suggesting this alternate way to do it. I merged your other PR because the changes are smaller, but we can discuss which way to do it on the pg hackers list.

In the meantime I'll be releasing another version of the extension to get your fix out there.

[begriffs]

Could you rebase this PR please?

[robertlagrant]

@adegert :)

[begriffs]

@adegert are you still interested in continuing development on this?