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