Return to Question

-- find an intermediate fraction between p1/q1 and p2/q2.
--
-- The fraction chosen is the highest fraction in the Stern-Brocot
-- tree which falls strictly between the specified values. This is
-- intended to avoid going deeper in the tree unnecessarily when the
-- list is already sparse due to deletion or moving of items, but in
-- fact the case when the two items are already adjacent in the tree
-- is common so we shortcut it. As a bonus, this method always
-- generates fractions in lowest terms, so there is no need for GCD
-- calculations anywhere.
--
-- Inputs must not be null (caller's responsibility), but the value
-- p2=1 q2=0 is allowed for the upper bound without causing any
-- division by zero errors.
 
CREATE OR REPLACE FUNCTION find_intermediate(p1 INTEGER, q1 INTEGER,
                                             p2 INTEGER, q2 INTEGER,
                                             OUT p INTEGER, OUT q INTEGER)
  LANGUAGE plpgsql immutable strict
AS $f$
  DECLARE
    pl INTEGER := 0;
    ql INTEGER := 1;
    ph INTEGER := 1;
    qh INTEGER := 0;
  BEGIN
    IF (p1::BIGINT*q2 + 1) <> (p2::BIGINT*q1) THEN
      loop
        p := pl + ph;
        q := ql + qh;
        IF (p::BIGINT*q1 <= q::BIGINT*p1) THEN
          pl := p; ql := q;
        elsif (p2::BIGINT*q <= q2::BIGINT*p) THEN
          ph := p; qh := q;
        ELSE
          exit;
        END IF;
      END loop;
    ELSE
      p := p1 + p2;
      q := q1 + q2;
    END IF;
  END;
$f$;