basis/math/intervals/intervals-docs.factor

   1 USING: help.markup help.syntax math math.order ;
   2 IN: math.intervals
   3
   4 ARTICLE: "math-intervals-new" "Creating intervals"
   5 "Standard constructors:"
   6 { $subsection [a,b] }
   7 { $subsection (a,b) }
   8 { $subsection [a,b) }
   9 { $subsection (a,b] }
  10 "One-point interval constructor:"
  11 { $subsection [a,a] }
  12 "Open-ended interval constructors:"
  13 { $subsection [-inf,a] }
  14 { $subsection [-inf,a) }
  15 { $subsection [a,inf] }
  16 { $subsection (a,inf] }
  17 "The set of all real numbers with infinities:"
  18 { $subsection [-inf,inf] }
  19 "The empty set:"
  20 { $subsection empty-interval }
  21 "Another constructor:"
  22 { $subsection points>interval } ;
  23
  24 ARTICLE: "math-intervals-arithmetic" "Interval arithmetic"
  25 "Binary operations on intervals:"
  26 { $subsection interval+ }
  27 { $subsection interval- }
  28 { $subsection interval* }
  29 { $subsection interval/ }
  30 { $subsection interval/i }
  31 { $subsection interval-mod }
  32 { $subsection interval-rem }
  33 { $subsection interval-min }
  34 { $subsection interval-max }
  35 "Bitwise operations on intervals:"
  36 { $subsection interval-shift }
  37 { $subsection interval-bitand }
  38 { $subsection interval-bitor }
  39 { $subsection interval-bitxor }
  40 "Unary operations on intervals:"
  41 { $subsection interval-1+ }
  42 { $subsection interval-1- }
  43 { $subsection interval-neg }
  44 { $subsection interval-bitnot }
  45 { $subsection interval-recip }
  46 { $subsection interval-2/ }
  47 { $subsection interval-abs }
  48 { $subsection interval-log2 } ;
  49
  50 ARTICLE: "math-intervals-sets" "Set-theoretic operations on intervals"
  51 { $subsection interval-contains? }
  52 { $subsection interval-subset? }
  53 { $subsection interval-intersect }
  54 { $subsection interval-union }
  55 { $subsection interval-closure }
  56 { $subsection integral-closure } ;
  57
  58 ARTICLE: "math-intervals-compare" "Comparing intervals"
  59 { $subsection interval< }
  60 { $subsection interval<= }
  61 { $subsection interval> }
  62 { $subsection interval>= }
  63 { $subsection assume< }
  64 { $subsection assume<= }
  65 { $subsection assume> }
  66 { $subsection assume>= } ;
  67
  68 ARTICLE: "math-interval-properties" "Properties of interval arithmetic"
  69 "For some operations, interval arithmetic yields inaccurate results, either because the result of lifting some operations to intervals does not result in intervals (bitwise operations, for example) or for the sake of simplicity of implementation."
  70 $nl
  71 "However, one important property holds for all operations. Suppose " { $emphasis "I, J" } " are intervals and " { $emphasis "op" } " is an operation. If " { $emphasis "x" } " is an element of " { $emphasis "I" } " and " { $emphasis "y" } " is an element of " { $emphasis "J" } ", then " { $emphasis "x op y" } " is an element of " { $emphasis "I op J" } "."
  72 $nl
  73 "In other words, the resulting interval might be an overestimate, but it is never an underestimate." ;
  74
  75 ARTICLE: "math-intervals" "Intervals"
  76 "Interval arithmetic is performed on ranges of real numbers, rather than exact values. It is used by the Factor compiler to convert arbitrary-precision arithmetic to machine arithmetic, by inferring bounds for integer calculations."
  77 { $subsection "math-interval-properties" }
  78 "The class of intervals:"
  79 { $subsection interval }
  80 { $subsection interval? }
  81 "Interval operations:"
  82 { $subsection "math-intervals-new" }
  83 { $subsection "math-intervals-arithmetic" }
  84 { $subsection "math-intervals-sets" }
  85 { $subsection "math-intervals-compare" } ;
  86
  87 ABOUT: "math-intervals"
  88
  89 HELP: interval
  90 { $class-description "An interval represents a set of real numbers between two endpoints; the endpoints can either be included or excluded from the interval."
  91 $nl
  92 "The " { $snippet "from" } " and " { $snippet "to" } " slots store endpoints, represented as arrays of the shape " { $snippet "{ number included? }" } "."
  93 $nl
  94 "Intervals are created by calling " { $link [a,b] } ", " { $link (a,b) } ", " { $link [a,b) } ", " { $link (a,b] } " or " { $link [a,a] } "." } ;
  95
  96 HELP: <interval>
  97 { $values { "from" "a " { $snippet "{ point included? }" } " pair" } { "to" "a " { $snippet "{ point included? }" } " pair" } { "interval" interval } }
  98 { $description "Creates a new interval. Usually it is more convenient to create intervals using one of the following words instead:"
  99     { $list
 100         { $link [a,b] }
 101         { $link (a,b) }
 102         { $link [a,b) }
 103         { $link (a,b] }
 104         { $link [a,inf] }
 105         { $link (a,inf] }
 106         { $link [-inf,a) }
 107         { $link [-inf,a] }
 108     }
 109 } ;
 110
 111 HELP: [a,b]
 112 { $values { "a" real } { "b" real } { "interval" interval } }
 113 { $description "Creates a new interval that includes both endpoints." } ;
 114
 115 HELP: (a,b)
 116 { $values { "a" real } { "b" real } { "interval" interval } }
 117 { $description "Creates a new interval that excludes both endpoints." } ;
 118
 119 HELP: [a,b)
 120 { $values { "a" real } { "b" real } { "interval" interval } }
 121 { $description "Creates a new interval that includes the lower endpoint and excludes the upper endpoint." } ;
 122
 123 HELP: (a,b]
 124 { $values { "a" real } { "b" real } { "interval" interval } }
 125 { $description "Creates a new interval that excludes the lower endpoint and includes the upper endpoint." } ;
 126
 127 HELP: [a,a]
 128 { $values { "a" real } { "interval" interval } }
 129 { $description "Creates a new interval consisting of a single point." } ;
 130
 131 HELP: [-inf,a]
 132 { $values { "a" real } { "interval" interval } }
 133 { $description "Creates a new interval containing all real numbers less than or equal to " { $snippet "a" } ", together with negative infinity." } ;
 134
 135 HELP: [-inf,a)
 136 { $values { "a" real } { "interval" interval } }
 137 { $description "Creates a new interval containing all real numbers less than " { $snippet "a" } ", together with negative infinity." } ;
 138
 139 HELP: [a,inf]
 140 { $values { "a" real } { "interval" interval } }
 141 { $description "Creates a new interval containing all real numbers greater than or equal to " { $snippet "a" } ", together with positive infinity." } ;
 142
 143 HELP: (a,inf]
 144 { $values { "a" real } { "interval" interval } }
 145 { $description "Creates a new interval containing all real numbers greater than " { $snippet "a" } ", together with positive infinity." } ;
 146
 147 HELP: interval+
 148 { $values { "i1" interval } { "i2" interval } { "i3" interval } }
 149 { $description "Adds two intervals." } ;
 150
 151 HELP: interval-
 152 { $values { "i1" interval } { "i2" interval } { "i3" interval } }
 153 { $description "Subtracts " { $snippet "i2" } " from " { $snippet "i1" } "." } ;
 154
 155 HELP: interval*
 156 { $values { "i1" interval } { "i2" interval } { "i3" interval } }
 157 { $description "Multiplies two intervals." } ;
 158
 159 HELP: interval-shift
 160 { $values { "i1" interval } { "i2" interval } { "i3" interval } }
 161 { $description "Shifts " { $snippet "i1" } " to the left by " { $snippet "i2" } " bits. Outputs " { $link full-interval } " if the endpoints of either " { $snippet "i1" } " or " { $snippet "i2" } " are not integers." } ;
 162
 163 HELP: interval-max
 164 { $values { "i1" interval } { "i2" interval } { "i3" interval } }
 165 { $description "Outputs the interval values obtained by lifting the " { $link max } " word to " { $snippet "i1" } " and " { $snippet "i2" } "." } ;
 166
 167 HELP: interval-mod
 168 { $values { "i1" interval } { "i2" interval } { "i3" interval } }
 169 { $description "Outputs an interval containing all possible values obtained by aplying " { $link mod } " to elements of " { $snippet "i1" } " and " { $snippet "i2" } "." } ;
 170
 171 HELP: interval-rem
 172 { $values { "i1" interval } { "i2" interval } { "i3" interval } }
 173 { $description "Outputs an interval containing all possible values obtained by aplying " { $link rem } " to elements of " { $snippet "i1" } " and " { $snippet "i2" } "." } ;
 174
 175 HELP: interval-bitand
 176 { $values { "i1" interval } { "i2" interval } { "i3" interval } }
 177 { $description "Outputs an interval containing all possible values obtained by aplying " { $link bitand } " to elements of " { $snippet "i1" } " and " { $snippet "i2" } "." } ;
 178
 179 HELP: interval-bitor
 180 { $values { "i1" interval } { "i2" interval } { "i3" interval } }
 181 { $description "Outputs an interval containing all possible values obtained by aplying " { $link bitor } " to elements of " { $snippet "i1" } " and " { $snippet "i2" } "." } ;
 182
 183 HELP: interval-bitxor
 184 { $values { "i1" interval } { "i2" interval } { "i3" interval } }
 185 { $description "Outputs an interval containing all possible values obtained by aplying " { $link bitxor } " to elements of " { $snippet "i1" } " and " { $snippet "i2" } "." } ;
 186
 187 HELP: interval-min
 188 { $values { "i1" interval } { "i2" interval } { "i3" interval } }
 189 { $description "Outputs the interval values obtained by lifting the " { $link min } " word to " { $snippet "i1" } " and " { $snippet "i2" } "." } ;
 190
 191 HELP: interval-1+
 192 { $values { "i1" interval } { "i2" interval } }
 193 { $description "Adds 1 to an interval." } ;
 194
 195 HELP: interval-1-
 196 { $values { "i1" interval } { "i2" interval } }
 197 { $description "Subtracts 1 from an interval." } ;
 198
 199 HELP: interval-neg
 200 { $values { "i1" interval } { "i2" interval } }
 201 { $description "Negates an interval." } ;
 202
 203 HELP: interval-abs
 204 { $values { "i1" interval } { "i2" interval } }
 205 { $description "Absolute value of an interval." } ;
 206
 207 HELP: interval-log2
 208 { $values { "i1" interval } { "i2" interval } }
 209 { $description "Integer-valued Base-2 logarithm of an interval." } ;
 210
 211 HELP: interval-intersect
 212 { $values { "i1" interval } { "i2" interval } { "i3" "an " { $link interval  } " or " { $link f } } }
 213 { $description "Outputs the set-theoretic intersection of " { $snippet "i1" } " and " { $snippet "i2" } ". If " { $snippet "i1" } " and " { $snippet "i2" } " do not intersect, outputs " { $link f } "." } ;
 214
 215 HELP: interval-union
 216 { $values { "i1" interval } { "i2" interval } { "i3" interval } }
 217 { $description "Outputs the smallest interval containing the set-theoretic union of " { $snippet "i1" } " and " { $snippet "i2" } " (the union itself may not be an interval)." } ;
 218
 219 HELP: interval-subset?
 220 { $values { "i1" interval } { "i2" interval } { "?" "a boolean" } }
 221 { $description "Tests if every point of " { $snippet "i1" } " is contained in " { $snippet "i2" } "." } ;
 222
 223 HELP: interval-contains?
 224 { $values { "x" real } { "int" interval } { "?" "a boolean" } }
 225 { $description "Tests if " { $snippet "x" } " is contained in " { $snippet "int" } "." } ;
 226
 227 HELP: interval-closure
 228 { $values { "i1" interval } { "i2" interval } }
 229 { $description "Outputs the smallest closed interval containing the endpoints of " { $snippet "i1" } "." } ;
 230
 231 HELP: interval/
 232 { $values { "i1" interval } { "i2" interval } { "i3" interval } }
 233 { $description "Divides " { $snippet "i1" } " by " { $snippet "i2" } ", using " { $link / } " to perform the division." } ;
 234
 235 HELP: interval/i
 236 { $values { "i1" interval } { "i2" interval } { "i3" interval } }
 237 { $description "Divides " { $snippet "i1" } " by " { $snippet "i2" } ", using " { $link /i } " to perform the division." } ;
 238
 239 HELP: interval/f
 240 { $values { "i1" interval } { "i2" interval } { "i3" interval } }
 241 { $description "Divides " { $snippet "i1" } " by " { $snippet "i2" } ", using " { $link /f } " to perform the division." } ;
 242
 243 HELP: interval-recip
 244 { $values { "i1" interval } { "i2" interval } }
 245 { $description "Outputs the reciprocal of an interval. Outputs " { $link f } " if " { $snippet "i1" } " contains points arbitrarily close to zero." } ;
 246
 247 HELP: interval-2/
 248 { $values { "i1" interval } { "i2" interval } }
 249 { $description "Shifts an interval to the right by one bit." } ;
 250
 251 HELP: interval-bitnot
 252 { $values { "i1" interval } { "i2" interval } }
 253 { $description "Computes the bitwise complement of the interval." } ;
 254
 255 HELP: points>interval
 256 { $values { "seq" "a sequence of " { $snippet "{ point included? }" } " pairs" } { "interval" interval } }
 257 { $description "Outputs the smallest interval containing all of the endpoints." }
 258 ;
 259
 260 HELP: interval-shift-safe
 261 { $values { "i1" interval } { "i2" interval } { "i3" interval } }
 262 { $description "Shifts " { $snippet "i1" } " to the left by " { $snippet "i2" } " bits. Outputs " { $link full-interval } " if the endpoints of either " { $snippet "i1" } " or " { $snippet "i2" } " are not integers, or if the endpoints of " { $snippet "i2" } " are so large that the resulting interval will consume too much memory." } ;
 263
 264 HELP: incomparable
 265 { $description "Output value from " { $link interval<= } ", " { $link interval< } ", " { $link interval>= } " and " { $link interval> } " in the case where the result of the comparison is ambiguous." } ;
 266
 267 HELP: interval<=
 268 { $values { "i1" interval } { "i2" interval } { "?" "a boolean or " { $link incomparable } } }
 269 { $description "Compares " { $snippet "i1" } " with " { $snippet "i2" } ", and outputs one of the following:"
 270     { $list
 271         { { $link t } " if every point in " { $snippet "i1" } " is less than or equal to every point in " { $snippet "i2" } }
 272         { { $link f } " if every point in " { $snippet "i1" } " is greater than every point in " { $snippet "i2" } }
 273         { { $link incomparable } " if neither of the above conditions hold" }
 274     }
 275 } ;
 276
 277 HELP: interval<
 278 { $values { "i1" interval } { "i2" interval } { "?" "a boolean or " { $link incomparable } } }
 279 { $description "Compares " { $snippet "i1" } " with " { $snippet "i2" } ", and outputs one of the following:"
 280     { $list
 281         { { $link t } " if every point in " { $snippet "i1" } " is less than every point in " { $snippet "i2" } }
 282         { { $link f } " if every point in " { $snippet "i1" } " is greater than or equal to every point in " { $snippet "i2" } }
 283         { { $link incomparable } " if neither of the above conditions hold" }
 284     }
 285 } ;
 286
 287 HELP: interval>=
 288 { $values { "i1" interval } { "i2" interval } { "?" "a boolean or " { $link incomparable } } }
 289 { $description "Compares " { $snippet "i1" } " with " { $snippet "i2" } ", and outputs one of the following:"
 290     { $list
 291         { { $link t } " if every point in " { $snippet "i1" } " is greater than or equal to every point in " { $snippet "i2" } }
 292         { { $link f } " if every point in " { $snippet "i1" } " is less than every point in " { $snippet "i2" } }
 293         { { $link incomparable } " if neither of the above conditions hold" }
 294     }
 295 } ;
 296
 297 HELP: interval>
 298 { $values { "i1" interval } { "i2" interval } { "?" "a boolean or " { $link incomparable } } }
 299 { $description "Compares " { $snippet "i1" } " with " { $snippet "i2" } ", and outputs one of the following:"
 300     { $list
 301         { { $link t } " if every point in " { $snippet "i1" } " is greater than every point in " { $snippet "i2" } }
 302         { { $link f } " if every point in " { $snippet "i1" } " is less than or equal to every point in " { $snippet "i2" } }
 303         { { $link incomparable } " if neither of the above conditions hold" }
 304     }
 305 } ;
 306
 307 HELP: interval>points
 308 { $values { "int" interval } { "from" "a " { $snippet "{ point included? }" } " pair" } { "to" "a " { $snippet "{ point included? }" } " pair" } }
 309 { $description "Outputs both endpoints of the interval." } ;
 310
 311 HELP: assume<
 312 { $values { "i1" interval } { "i2" interval } { "i3" interval } }
 313 { $description "Outputs the interval consisting of points from " { $snippet "i1" } " which are less than all points in " { $snippet "i2" } "." } ;
 314
 315 HELP: assume<=
 316 { $values { "i1" interval } { "i2" interval } { "i3" interval } }
 317 { $description "Outputs the interval consisting of points from " { $snippet "i1" } " which are less or equal to all points in " { $snippet "i2" } "." } ;
 318
 319 HELP: assume>
 320 { $values { "i1" interval } { "i2" interval } { "i3" "an " { $link interval } " or " { $link f } } }
 321 { $description "Outputs the interval consisting of points from " { $snippet "i1" } " which are greater than all points in " { $snippet "i2" } ". If the resulting interval is empty, outputs " { $link f } "." } ;
 322
 323 HELP: assume>=
 324 { $values { "i1" interval } { "i2" interval } { "i3" interval } }
 325 { $description "Outputs the interval consisting of points from " { $snippet "i1" } " which are greater than or equal to all points in " { $snippet "i2" } "." } ;
 326
 327 HELP: integral-closure
 328 { $values { "i1" "an " { $link interval } " with integer end-points" } { "i2" "a closed " { $link interval } " with integer end-points" } }
 329 { $description "Outputs a closed interval which is equal as a set to " { $snippet "i1" } ", when " { $snippet "i1" } " is viewed as an interval over in integers (that is, a discrete set)." } ;