doc/info/pslq.texi

   1 @menu
   2 * Introduction to pslq::
   3 * Functions and Variables for pslq::
   4 @end menu
   5
   6 @node Introduction to pslq, Functions and Variables for pslq, Package pslq, Package pslq
   7 @section Introduction to pslq
   8
   9 Package @code{pslq} contains two functions.
  10
  11 (1) @code{guess_exact_value} tries to find
  12 an exact equivalent for an inexact number (float or bigfloat).
  13
  14 (2) @code{pslq_integer_relation} tries to find
  15 integer coefficients such that a linear combination of inexact numbers
  16 is approximately zero.
  17
  18 @node Functions and Variables for pslq, , Introduction to pslq, Package pslq
  19 @section Functions and Variables for pslq
  20
  21 @anchor{guess_exact_value}
  22 @deffn {Function} guess_exact_value (@var{x})
  23
  24 When @var{x} is a floating point number or bigfloat,
  25 @code{guess_exact_value} tries to find an exact expression
  26 (in terms of radicals, logarithms, exponentials, and the constant @code{%pi})
  27 which is nearly equal to the given number.
  28 If @code{guess_exact_value} cannot find such an expression,
  29 @var{x} is returned unchanged.
  30
  31 When @var{x} is rational number or other mapatom
  32 (other than a float or bigfloat),
  33 @var{x} is returned unchanged.
  34
  35 Otherwise, @var{x} is a nonatomic expression,
  36 and @code{guess_exact_value} is applied to each of the arguments of @var{x}.
  37
  38 Example:
  39
  40 @c ===beg===
  41 @c load ("pslq.mac");
  42 @c root: float (sin (%pi/12));
  43 @c guess_exact_value (root);
  44 @c L: makelist (root^i, i, 0, 4);
  45 @c m: pslq_integer_relation(%);
  46 @c makelist (x^i, i, 0, 4) . m;
  47 @c solve(%);
  48 @c ===end===
  49 @example
  50 (%i1) load ("pslq.mac");
  51 (%o1)                       pslq.mac
  52 (%i2) root: float (sin (%pi/12));
  53 (%o2)                  0.2588190451025207
  54 (%i3) guess_exact_value (root);
  55                         sqrt(2 - sqrt(3))
  56 (%o3)                   -----------------
  57                                 2
  58 (%i4) L: makelist (root^i, i, 0, 4);
  59 (%o4) [1.0, 0.2588190451025207, 0.06698729810778066,
  60                        0.01733758853025369, 0.004487298107780675]
  61 (%i5) m: pslq_integer_relation(%);
  62 (%o5)                 [- 1, 0, 16, 0, - 16]
  63 (%i6) makelist (x^i, i, 0, 4) . m;
  64                              4        2
  65 (%o6)                 (- 16 x ) + 16 x  - 1
  66 (%i7) solve(%);
  67              sqrt(sqrt(3) + 2)      sqrt(sqrt(3) + 2)
  68 (%o7) [x = - -----------------, x = -----------------,
  69                      2                      2
  70                         sqrt(2 - sqrt(3))      sqrt(2 - sqrt(3))
  71                   x = - -----------------, x = -----------------]
  72                                 2                      2
  73 @end example
  74 @end deffn
  75
  76 @deffn {Function} pslq_integer_relation (@var{L})
  77
  78 Implements the PSLQ algorithm [1] to find integer relations between bigfloat numbers.
  79
  80 For a given list @var{L} of floating point numbers,
  81 @code{pslq_integer_relation} returns a list of integers @var{m}
  82 such that @code{@var{m} . @var{L} = 0}
  83 (with absolute residual error less than @code{pslq_threshold}).
  84
  85 [1] D.H.Bailey: Integer Relation Detection and Lattice Reduction.
  86
  87 Example:
  88
  89 @c ===beg===
  90 @c load ("pslq.mac");
  91 @c root: float (sin (%pi/12));
  92 @c L: makelist (root^i, i, 0, 4);
  93 @c m: pslq_integer_relation(%);
  94 @c m . L;
  95 @c float (10^(2 - fpprec));
  96 @c is (abs (m . L) < 10^(2 - fpprec));
  97 @c ===end===
  98 @example
  99 (%i1) load ("pslq.mac");
 100 (%o1)                       pslq.mac
 101 (%i2) root: float (sin (%pi/12));
 102 (%o2)                  0.2588190451025207
 103 (%i3) L: makelist (root^i, i, 0, 4);
 104 (%o3) [1.0, 0.2588190451025207, 0.06698729810778066,
 105                        0.01733758853025369, 0.004487298107780675]
 106 (%i4) m: pslq_integer_relation(%);
 107 (%o4)                 [- 1, 0, 16, 0, - 16]
 108 (%i5) m . L;
 109 (%o5)                - 2.359223927328458E-16
 110 (%i6) float (10^(2 - fpprec));
 111 (%o6)                        1.0E-14
 112 (%i7) is (abs (m . L) < 10^(2 - fpprec));
 113 (%o7)                         true
 114 @end example
 115 @end deffn
 116
 117 @defvr {Variable} pslq_precision
 118 Default value: @code{10^(fpprec - 2)}
 119
 120 Maximum magnitude of some intermediate results in @code{pslq_integer_relation}.
 121 The search fails if one of the intermediate results has elements
 122 larger than @code{pslq_precision}.
 123
 124 @end defvr
 125
 126 @defvr {Variable} pslq_threshold
 127 Default value: @code{10^(2 - fpprec)}
 128
 129 Threshold for absolute residual error of integer relation found by @code{pslq_integer_relation}.
 130
 131 @end defvr
 132
 133 @defvr {Variable} pslq_depth
 134 Default value: @code{20 * @var{n}}
 135
 136 Number of iterations of the PSLQ algorithm.
 137
 138 The default value is 20 times @var{n},
 139 where @var{n} is the length of the list of numbers supplied to @code{pslq_integer_relation}.
 140
 141 @end defvr
 142
 143 @defvr {Variable} pslq_status
 144
 145 Indicates success or failure for an integer relation search by @code{pslq_integer_relation}.
 146
 147 When @code{pslq_status} is 1, it indicates an integer relation was found,
 148 and the absolute residual error is less than @code{pslq_threshold}.
 149
 150 When @code{pslq_status} is 2, it indicates an integer relation was not found
 151 because some intermediate results are larger than @code{pslq_precision}.
 152
 153 When @code{pslq_status} is 3, it indicates an integer relation was not found
 154 because the number of iterations @code{pslq_depth} was reached.
 155
 156 @end defvr
 157
 158 @c SEEMS TO OBSCURE FOR USER-LEVEL DOCUMENTATION
 159 @c @defvr {Variable} pslq_fail_norm
 160 @c @end defvr
 161