help/cfsim

   1 NAME
   2     cfsim - simplify a value using continued fractions
   3
   4 SYNOPSIS
   5     cfsim(x [,rnd])
   6
   7 TYPES
   8     x           real
   9     rnd         integer, defaults to config("cfsim")
  10
  11     return      real
  12
  13 DESCRIPTION
  14     If x is not an integer, cfsim(x, rnd) returns either the nearest
  15     above x, or the nearest below x, number with denominator less than
  16     den(x).  If x is an integer, cfsim(x, rnd) returns x + 1, x - 1, or 0.
  17     Which of the possible results is returned is controlled
  18     by bits 0, 1, 3 and 4 of the parameter rnd.
  19
  20     For 0 <= rnd < 4, the sign of the remainder x - cfsim(x, rnd) is
  21     as follows:
  22
  23                 rnd             sign of x - cfsim(x, rnd)
  24
  25                 0               +, as if rounding down
  26                 1               -. as if rounding up
  27                 2               sgn(x), as if rounding to zero
  28                 3               -sgn(x), as if rounding from zero
  29
  30     This corresponds to the use of rnd for functions like round(x, n, rnd).
  31
  32     If bit 3 or 4 of rnd is set, the lower order bits are ignored; bit 3
  33     is ignored if bit 4 is set.  Thusi, for rnd > 3, it sufficient to
  34     consider the two cases rnd = 8 and rnd = 16.
  35
  36     If den(x) > 2, cfsim(x, 8) returns the value of the penultimate simple
  37     continued-fraction approximant to x, i.e. if:
  38
  39         x = a_0 + 1/(a_1 + 1/(a_2 + ... + 1/a_n) ...)),
  40
  41     where a_0 is an integer, a_1, ..., a_n are positive integers,
  42     and a_n >= 2, the value returned is that of the continued fraction
  43     obtained by dropping the last quotient 1/a_n.
  44
  45     If den(x) > 2, cfsim(x, 16) returns the nearest number to x with
  46     denominator less than den(x).  In the continued-fraction representation
  47     of x described above, this is given by replacing a_n by a_n - 1.
  48
  49     If den(x) = 2, the definition adopted is to round towards zero for the
  50     approximant case (rnd = 8) and from zero for the "nearest" case (rnd = 16).
  51
  52     For integral x, cfsim(x, 8) returns zero, cfsim(x,16) returns x - sgn(x).
  53
  54     In summary, for cfsim(x, rnd) when rnd = 8 or 16, the results are:
  55
  56         rnd             integer x       half-integer x          den(x) > 2
  57
  58          8              0               x - sgn(x)/2            approximant
  59         16              x - sgn(x)      x + sgn(x)/2            nearest
  60
  61      From either cfsim(x, 0) and cfsim(x, 1), the other is easily
  62      determined: if one of them has value w, the other has value
  63      (num(x) - num(w))/(den(x) - den(w)).  From x and w one may find
  64      other optimal rational numbers near x; for example, the smallest-
  65      denominator number between x and w is (num(x) + num(w))/(den(x) + den(w)).
  66
  67      If x = n/d and cfsim(x, 8) = u/v, then for k * v < d, the k-th member of
  68      the sequence of nearest approximations to x with decreasing denominators
  69      on the other side of x is (n - k * u)/(d - k * v). This is nearer
  70      to or further from x than u/v according as 2 * k * v < or > d.
  71
  72      Iteration of cfsim(x,8) until an integer is obtained gives a sequence of
  73      "good" approximations to x with decreasing denominators and
  74      correspondingly decreasing accuracy; each denominator is less than half
  75      the preceding denominator.  (Unlike the "forward" sequence of
  76      continued-fraction approximants these are not necessarily alternately
  77      greater than and less than x.)
  78
  79      Some other properties:
  80
  81      For rnd = 0 or 1 and any x, or rnd = 8 or 16 and x with den(x) > 2:
  82
  83                 cfsim(n + x, rnd) = n + cfsim(x, rnd).
  84
  85      This equation also holds for the other values of rnd if n + x and x
  86      have the same sign.
  87
  88      For rnd = 2, 3, 8 or 16, and any x:
  89
  90                 cfsim(-x, rnd) = -cfsim(x, rnd).
  91
  92      If rnd = 8 or 16, except for integer x or 1/x for rnd = 8, and
  93      zero x for rnd = 16:
  94
  95                 cfsim(1/x, rnd) = 1/cfsim(x, rnd).
  96
  97 EXAMPLE
  98     > c = config("mode", "frac");
  99
 100     > print cfsim(43/30, 0), cfsim(43/30, 1), cfsim(43/30, 8), cfsim(43/30,16)
 101     10/7 33/23 10/7 33/23
 102
 103     > x = pi(1e-20); c = config("mode", "frac");
 104     > while (!isint(x)) {x = cfsim(x,8); if (den(x) < 1e6) print x,:;}
 105     1146408/364913 312689/99532 104348/33215 355/113 22/7 3
 106
 107 LIMITS
 108     none
 109
 110 LINK LIBRARY
 111     NUMBER *qcfsim(NUMBER *x, long rnd)
 112
 113 SEE ALSO
 114     cfappr
 115