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
  49 ARTICLE: "math-intervals-sets" "Set-theoretic operations on intervals"
  50 { $subsection interval-contains? }
  51 { $subsection interval-subset? }
  52 { $subsection interval-intersect }
  53 { $subsection interval-union }
  54 { $subsection interval-closure }
  55 { $subsection integral-closure } ;
  56
  57 ARTICLE: "math-intervals-compare" "Comparing intervals"
  58 { $subsection interval< }
  59 { $subsection interval<= }
  60 { $subsection interval> }
  61 { $subsection interval>= }
  62 { $subsection assume< }
  63 { $subsection assume<= }
  64 { $subsection assume> }
  65 { $subsection assume>= } ;
  66
  67 ARTICLE: "math-interval-properties" "Properties of interval arithmetic"
  68 "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."
  69 $nl
  70 "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" } "."
  71 $nl
  72 "In other words, the resulting interval might be an overestimate, but it is never an underestimate." ;
  73
  74 ARTICLE: "math-intervals" "Intervals"
  75 "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."
  76 { $subsection "math-interval-properties" }
  77 "The class of intervals:"
  78 { $subsection interval }
  79 { $subsection interval? }
  80 "Interval operations:"
  81 { $subsection "math-intervals-new" }
  82 { $subsection "math-intervals-arithmetic" }
  83 { $subsection "math-intervals-sets" }
  84 { $subsection "math-intervals-compare" } ;
  85
  86 ABOUT: "math-intervals"
  87
  88 HELP: interval
  89 { $class-description "An interval represents a set of real numbers between two endpoints; the endpoints can either be included or excluded from the interval."
  90 $nl
  91 "The " { $link interval-from } " and " { $link interval-to } " slots store endpoints, represented as arrays of the shape " { $snippet "{ number included? }" } "."
  92 $nl
  93 "Intervals are created by calling " { $link [a,b] } ", " { $link (a,b) } ", " { $link [a,b) } ", " { $link (a,b] } " or " { $link [a,a] } "." } ;
  94
  95 HELP: <interval> ( from to -- interval )
  96 { $values { "from" "a " { $snippet "{ point included? }" } " pair" } { "to" "a " { $snippet "{ point included? }" } " pair" } { "interval" interval } }
  97 { $description "Creates a new interval. Usually it is more convenient to create intervals using one of the following words instead:"
  98     { $list
  99         { $link [a,b] }
 100         { $link (a,b) }
 101         { $link [a,b) }
 102         { $link (a,b] }
 103         { $link [a,inf] }
 104         { $link (a,inf] }
 105         { $link [-inf,a) }
 106         { $link [-inf,a] }
 107     }
 108 } ;
 109
 110 HELP: [a,b]
 111 { $values { "a" real } { "b" real } { "interval" interval } }
 112 { $description "Creates a new interval that includes both endpoints." } ;
 113
 114 HELP: (a,b)
 115 { $values { "a" real } { "b" real } { "interval" interval } }
 116 { $description "Creates a new interval that excludes both endpoints." } ;
 117
 118 HELP: [a,b)
 119 { $values { "a" real } { "b" real } { "interval" interval } }
 120 { $description "Creates a new interval that includes the lower endpoint and excludes the upper endpoint." } ;
 121
 122 HELP: (a,b]
 123 { $values { "a" real } { "b" real } { "interval" interval } }
 124 { $description "Creates a new interval that excludes the lower endpoint and includes the upper endpoint." } ;
 125
 126 HELP: [a,a]
 127 { $values { "a" real } { "interval" interval } }
 128 { $description "Creates a new interval consisting of a single point." } ;
 129
 130 HELP: [-inf,a]
 131 { $values { "a" real } { "interval" interval } }
 132 { $description "Creates a new interval containing all real numbers less than or equal to " { $snippet "a" } ", together with negative infinity." } ;
 133
 134 HELP: [-inf,a)
 135 { $values { "a" real } { "interval" interval } }
 136 { $description "Creates a new interval containing all real numbers less than " { $snippet "a" } ", together with negative infinity." } ;
 137
 138 HELP: [a,inf]
 139 { $values { "a" real } { "interval" interval } }
 140 { $description "Creates a new interval containing all real numbers greater than or equal to " { $snippet "a" } ", together with positive infinity." } ;
 141
 142 HELP: (a,inf]
 143 { $values { "a" real } { "interval" interval } }
 144 { $description "Creates a new interval containing all real numbers greater than " { $snippet "a" } ", together with positive infinity." } ;
 145
 146 HELP: interval+
 147 { $values { "i1" interval } { "i2" interval } { "i3" interval } }
 148 { $description "Adds two intervals." } ;
 149
 150 HELP: interval-
 151 { $values { "i1" interval } { "i2" interval } { "i3" interval } }
 152 { $description "Subtracts " { $snippet "i2" } " from " { $snippet "i1" } "." } ;
 153
 154 HELP: interval*
 155 { $values { "i1" interval } { "i2" interval } { "i3" interval } }
 156 { $description "Multiplies two intervals." } ;
 157
 158 HELP: interval-shift
 159 { $values { "i1" interval } { "i2" interval } { "i3" "an " { $link interval } " or " { $link f } } }
 160 { $description "Shifts " { $snippet "i1" } " to the left by " { $snippet "i2" } " bits. Outputs " { $link f } " if the endpoints of either " { $snippet "i1" } " or " { $snippet "i2" } " are not integers." } ;
 161
 162 HELP: interval-max
 163 { $values { "i1" interval } { "i2" interval } { "i3" interval } }
 164 { $description "Outputs the interval values obtained by lifting the " { $link max } " word to " { $snippet "i1" } " and " { $snippet "i2" } "." } ;
 165
 166 HELP: interval-mod
 167 { $values { "i1" interval } { "i2" interval } { "i3" interval } }
 168 { $description "Outputs an interval containing all possible values obtained by aplying " { $link mod } " to elements of " { $snippet "i1" } " and " { $snippet "i2" } "." } ;
 169
 170 HELP: interval-rem
 171 { $values { "i1" interval } { "i2" interval } { "i3" interval } }
 172 { $description "Outputs an interval containing all possible values obtained by aplying " { $link rem } " to elements of " { $snippet "i1" } " and " { $snippet "i2" } "." } ;
 173
 174 HELP: interval-bitand
 175 { $values { "i1" interval } { "i2" interval } { "i3" interval } }
 176 { $description "Outputs an interval containing all possible values obtained by aplying " { $link bitand } " to elements of " { $snippet "i1" } " and " { $snippet "i2" } "." } ;
 177
 178 HELP: interval-bitor
 179 { $values { "i1" interval } { "i2" interval } { "i3" interval } }
 180 { $description "Outputs an interval containing all possible values obtained by aplying " { $link bitor } " to elements of " { $snippet "i1" } " and " { $snippet "i2" } "." } ;
 181
 182 HELP: interval-bitxor
 183 { $values { "i1" interval } { "i2" interval } { "i3" interval } }
 184 { $description "Outputs an interval containing all possible values obtained by aplying " { $link bitxor } " to elements of " { $snippet "i1" } " and " { $snippet "i2" } "." } ;
 185
 186 HELP: interval-min
 187 { $values { "i1" interval } { "i2" interval } { "i3" interval } }
 188 { $description "Outputs the interval values obtained by lifting the " { $link min } " word to " { $snippet "i1" } " and " { $snippet "i2" } "." } ;
 189
 190 HELP: interval-1+
 191 { $values { "i1" interval } { "i2" interval } }
 192 { $description "Adds 1 to an interval." } ;
 193
 194 HELP: interval-1-
 195 { $values { "i1" interval } { "i2" interval } }
 196 { $description "Subtracts 1 from an interval." } ;
 197
 198 HELP: interval-neg
 199 { $values { "i1" interval } { "i2" interval } }
 200 { $description "Negates an interval." } ;
 201
 202 HELP: interval-abs
 203 { $values { "i1" interval } { "i2" interval } }
 204 { $description "Absolute value of an interval." } ;
 205
 206 HELP: interval-intersect
 207 { $values { "i1" interval } { "i2" interval } { "i3" "an " { $link interval  } " or " { $link f } } }
 208 { $description "Outputs the set-theoretic intersection of " { $snippet "i1" } " and " { $snippet "i2" } ". If " { $snippet "i1" } " and " { $snippet "i2" } " do not intersect, outputs " { $link f } "." } ;
 209
 210 HELP: interval-union
 211 { $values { "i1" interval } { "i2" interval } { "i3" interval } }
 212 { $description "Outputs the smallest interval containing the set-theoretic union of " { $snippet "i1" } " and " { $snippet "i2" } " (the union itself may not be an interval)." } ;
 213
 214 HELP: interval-subset?
 215 { $values { "i1" interval } { "i2" interval } { "?" "a boolean" } }
 216 { $description "Tests if every point of " { $snippet "i1" } " is contained in " { $snippet "i2" } "." } ;
 217
 218 HELP: interval-contains?
 219 { $values { "x" real } { "int" interval } { "?" "a boolean" } }
 220 { $description "Tests if " { $snippet "x" } " is contained in " { $snippet "int" } "." } ;
 221
 222 HELP: interval-closure
 223 { $values { "i1" interval } { "i2" interval } }
 224 { $description "Outputs the smallest closed interval containing the endpoints of " { $snippet "i1" } "." } ;
 225
 226 HELP: interval/
 227 { $values { "i1" interval } { "i2" interval } { "i3" interval } }
 228 { $description "Divides " { $snippet "i1" } " by " { $snippet "i2" } ", using " { $link / } " to perform the division." } ;
 229
 230 HELP: interval/i
 231 { $values { "i1" interval } { "i2" interval } { "i3" interval } }
 232 { $description "Divides " { $snippet "i1" } " by " { $snippet "i2" } ", using " { $link /i } " to perform the division." } ;
 233
 234 HELP: interval/f
 235 { $values { "i1" interval } { "i2" interval } { "i3" interval } }
 236 { $description "Divides " { $snippet "i1" } " by " { $snippet "i2" } ", using " { $link /f } " to perform the division." } ;
 237
 238 HELP: interval-recip
 239 { $values { "i1" interval } { "i2" interval } }
 240 { $description "Outputs the reciprocal of an interval. Outputs " { $link f } " if " { $snippet "i1" } " contains points arbitrarily close to zero." } ;
 241
 242 HELP: interval-2/
 243 { $values { "i1" interval } { "i2" interval } }
 244 { $description "Shifts an interval to the right by one bit." } ;
 245
 246 HELP: interval-bitnot
 247 { $values { "i1" interval } { "i2" interval } }
 248 { $description "Computes the bitwise complement of the interval." } ;
 249
 250 HELP: points>interval
 251 { $values { "seq" "a sequence of " { $snippet "{ point included? }" } " pairs" } { "interval" interval } }
 252 { $description "Outputs the smallest interval containing all of the endpoints." }
 253 ;
 254
 255 HELP: interval-shift-safe
 256 { $values { "i1" interval } { "i2" interval } { "i3" "an " { $link interval } " or " { $link f } } }
 257 { $description "Shifts " { $snippet "i1" } " to the left by " { $snippet "i2" } " bits. Outputs " { $link f } " 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." } ;
 258
 259 HELP: incomparable
 260 { $description "Output value from " { $link interval<= } ", " { $link interval< } ", " { $link interval>= } " and " { $link interval> } " in the case where the result of the comparison is ambiguous." } ;
 261
 262 HELP: interval<=
 263 { $values { "i1" interval } { "i2" interval } { "?" "a boolean or " { $link incomparable } } }
 264 { $description "Compares " { $snippet "i1" } " with " { $snippet "i2" } ", and outputs one of the following:"
 265     { $list
 266         { { $link t } " if every point in " { $snippet "i1" } " is less than or equal to every point in " { $snippet "i2" } }
 267         { { $link f } " if every point in " { $snippet "i1" } " is greater than every point in " { $snippet "i2" } }
 268         { { $link incomparable } " if neither of the above conditions hold" }
 269     }
 270 } ;
 271
 272 HELP: interval<
 273 { $values { "i1" interval } { "i2" interval } { "?" "a boolean or " { $link incomparable } } }
 274 { $description "Compares " { $snippet "i1" } " with " { $snippet "i2" } ", and outputs one of the following:"
 275     { $list
 276         { { $link t } " if every point in " { $snippet "i1" } " is less than every point in " { $snippet "i2" } }
 277         { { $link f } " if every point in " { $snippet "i1" } " is greater than or equal to every point in " { $snippet "i2" } }
 278         { { $link incomparable } " if neither of the above conditions hold" }
 279     }
 280 } ;
 281
 282 HELP: interval>=
 283 { $values { "i1" interval } { "i2" interval } { "?" "a boolean or " { $link incomparable } } }
 284 { $description "Compares " { $snippet "i1" } " with " { $snippet "i2" } ", and outputs one of the following:"
 285     { $list
 286         { { $link t } " if every point in " { $snippet "i1" } " is greater than or equal to every point in " { $snippet "i2" } }
 287         { { $link f } " if every point in " { $snippet "i1" } " is less than every point in " { $snippet "i2" } }
 288         { { $link incomparable } " if neither of the above conditions hold" }
 289     }
 290 } ;
 291
 292 HELP: interval>
 293 { $values { "i1" interval } { "i2" interval } { "?" "a boolean or " { $link incomparable } } }
 294 { $description "Compares " { $snippet "i1" } " with " { $snippet "i2" } ", and outputs one of the following:"
 295     { $list
 296         { { $link t } " if every point in " { $snippet "i1" } " is greater than every point in " { $snippet "i2" } }
 297         { { $link f } " if every point in " { $snippet "i1" } " is less than or equal to every point in " { $snippet "i2" } }
 298         { { $link incomparable } " if neither of the above conditions hold" }
 299     }
 300 } ;
 301
 302 HELP: interval>points
 303 { $values { "int" interval } { "from" "a " { $snippet "{ point included? }" } " pair" } { "to" "a " { $snippet "{ point included? }" } " pair" } }
 304 { $description "Outputs both endpoints of the interval." } ;
 305
 306 HELP: assume<
 307 { $values { "i1" interval } { "i2" interval } { "i3" "an " { $link interval } " or " { $link f } } }
 308 { $description "Outputs the interval consisting of points from " { $snippet "i1" } " which are less than all points in " { $snippet "i2" } ". If the resulting interval is empty, outputs " { $link f } "." } ;
 309
 310 HELP: assume<=
 311 { $values { "i1" interval } { "i2" interval } { "i3" "an " { $link interval } " or " { $link f } } }
 312 { $description "Outputs the interval consisting of points from " { $snippet "i1" } " which are less or equal to all points in " { $snippet "i2" } ". If the resulting interval is empty, outputs " { $link f } "." } ;
 313
 314 HELP: assume>
 315 { $values { "i1" interval } { "i2" interval } { "i3" "an " { $link interval } " or " { $link f } } }
 316 { $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 } "." } ;
 317
 318 HELP: assume>=
 319 { $values { "i1" interval } { "i2" interval } { "i3" "an " { $link interval } " or " { $link f } } }
 320 { $description "Outputs the interval consisting of points from " { $snippet "i1" } " which are greater than or equal to all points in " { $snippet "i2" } ". If the resulting interval is empty, outputs " { $link f } "." } ;
 321
 322 HELP: integral-closure
 323 { $values { "i1" "an " { $link interval } " with integer end-points" } { "i2" "a closed " { $link interval } " with integer end-points" } }
 324 { $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)." } ;