newRPL: Alpha demo 0.9 released [UPDATED 2017-10-25]

[The Shadow]

(08-19-2017 06:58 PM)Claudio L. Wrote:  

(08-19-2017 05:36 PM)The Shadow Wrote:  I've been playing around with continued fractions, and I'm curious what algorithm you're using for ->Q. It's really fast, but also seems to be 'overshooting' in terms of precision - the last six to ten terms or so of the continued fractions of irrational numbers are consistently gobbledegook.

I've coded a version of ->Q that stops when it gets beyond the set precision, but it's 6 times slower than the built-in version.

I don't understand what you mean by "overshooting". ->Q will use signed 64-bit integers for the numerator and denominator to approximate the number as good as possible. The limited precision will show when you try to convert small numbers (smaller than 1E-18), since the smallest fraction that can be represented is 1/max_denom = 2^-63.
More precision doesn't make much sense: if you need more than 18 digits to represent the denominator, you are probably better off working with the real number. Too much precision will hurt the algorithm when trying to find simple fractions

I can see I'm explaining myself badly. Perhaps an example would illustrate what I mean better:

When I run ->Q on the golden ratio, I get (leaving out a lot of digits for brevity):

'1.349E19/8.335E18'

When I run my version on the golden ratio, I get:

'5.528E15/3.416E15'

It turns out those two values are equally precise, but yours has much higher values for the numerator and denominator - hence it is not an actual convergent, which translates into extraneous digits in the continued fraction.

When I expand those two answers into continued fractions, mine consists of 76 1's, just as it should. Yours is 84 entries long, and ends in { 2 5 1 2 1 1 5 1 3 2 }.

Nor is the golden ratio an isolated case. I get similar results with every number I've tried so far; it's just easier to check the golden ratio because it has such a simple expansion.

(I should add that it would in principle be possible to get even smaller numerators and denominators at the expense of the continued fraction expansion by walking the Stern-Brocot tree. But that would likely be slow, and for some unfortunate cases VERY slow.)