rationalize number with limit denominator

Question

I know that Maxima CAS can rationalize floating point number ( convert to ratio):

(%i215) rat(0.1667);

(%o215) 1667/10000

Is it possible to rationalize floating point number with limit denominator like in python ?

I would like to set limit denominator to 10 and have the result 1/6.

 (%i216) float(1/6);

 (%o216) 0.1666666666666666

Have a look at the "Farley Algorithm", e.g. here: https://www.johndcook.com/blog/2010/10/20/best-rational-approximation/ — chtz, Aug 18 '20 at 12:11

slitvinov · Accepted Answer · 2020-10-11T06:39:32.397

This is a translation of an algorithm from python:

(%i1) limit_denominator(x, max_denominator):=
block([p0, q0, p1, q1, n, d, a, q2, k, bound1, bound2, ratprint: false],
  [p0, q0, p1, q1]: [0, 1, 1, 0],
  [n, d]: ratexpand([ratnum(x), ratdenom(x)], 0),
  if d <= max_denominator then x else
  (catch(
    do block(
      a: quotient(n, d),
      q2: q0+a*q1,
      if q2 > max_denominator then throw('done),
      [p0, q0, p1, q1]: [p1, q1, p0+a*p1, q2],
      [n, d]: [d, n-a*d])),
  k: quotient(max_denominator-q0, q1),
  bound1: (p0+k*p1)/(q0+k*q1),
  bound2: p1/q1,
  if abs(bound2 - x) <= abs(bound1 - x) then bound2 else bound1))$

(%i2) x: 3.141592653589793 $

(%i3) limit_denominator(x, 10);
                                      22
(%o3)                                 --
                                      7
(%i4) limit_denominator(x, 100);
                                      311
(%o4)                                 ---
                                      99
(%i5) limit_denominator(4321/8765, 10000);
                                     4321
(%o5)                                ----
                                     8765

rationalize number with limit denominator

1 Answers1