-
Notifications
You must be signed in to change notification settings - Fork 107
TM019 Roughnums
There are two broad categories of Pyret numbers: precise rational numbers and “rough” numbers.
☠ Pyret numbers lie strictly on the Real Line. “Higher” numbers such as complex numbers are treated as matters for libraries. Thus, taking the sqrt of a negative number raises an exception.
Precise rational numbers are the familiar integers and rational
fractions. Integers are represented by sequences of digits with a
possible - sign in front of them.
1 2 -3
It is also possible to suffix them with a decimal point and any number of 0s.
5.0 -6.00
Rational numbers are pairs of integers, one for the numerator and the other for the denominator. They can be represented by the m/n notation, where m is an integer, and n is a positive integer.
2/3 -355/113
In addition, rational numbers may also be represented by decimal notation:
1.75 -6.38
The decimal may also include an exponent of 10 (“scientific notation”):
6.022e23 6.022e+23 1.602e-19
The first two both represent 6.022×10²³, and the last represents 1.602×10¯¹⁹.
Note that the m/n representation covers more cases than the decimal, e.g., 1/5 can be represented as .2 or 0.2, but 1/3 allows no decimal representation. Thus, a notation like 1.75 can be taken as a convenient abbreviation of a more general 7/4. This is the rationale for Pyret storing all rational numbers in m/n format, even if the user is allowed to specify them with decimal notation.
Sufficiently small precise integers directly translate to JavaScript numbers (or “fixnums”), which have a well-defined range, viz., from −(2⁵³−1) to 2⁵³−1. For integers outside this range, a “bignum” implementation is used. However, this happens “under the hood”, and the user does not have to do any explicit housekeeping. Bignum calculations will, however, take longer: or, put another way, smaller nums are optimized.
☠ At least some non-integral rationals could also potentially exploit being directly represented as JavaScript doubles, rather than as pairs of integers (possibly bignums). But we don’t do this because of the following troubles:
-
Even though JavaScript doubles have a large range (larger than JavaScript integers) — viz., they can have a max abs value of 1.7976931348623157×10³⁰⁸ —, they also come with a certain “granularity” (= 5×10¯³²⁴), which implies that multiplication and division even on non-edge cases can stumble. E.g.,
4.099999 - 2.099999
does not quite return 2.
-
Moreover, even if there were no such practical limitations, the JS-double notation is not closed under division, e.g., 1 divided by 3 forces one to retreat to the pair notation 1/3, if one wished to remain precise.
All this to show that one has to be careful optimizing non-integral rationals as JavaScript doubles. Integral rationals, in contrast, hold no such terrors when optimized as JavaScript integers.
Going beyond arithmetic operations,
precise rationals are not closed under algebraic or trigonometric
operations, which can generate irrational numbers.
For this reason, Pyret offers rough numbers,
roughnums for short. Except for edge values we’ll describe
below, roughnums use the same representations
described above for integers and decimal rationals, with a
~ as a prefixed sigil.
~1 ~2.5 ~-3.33
An example roughnum is the result of the sqrt function applied to the precise rational (and integer) 2: it is ~1.4142135623730951.
Users themselves may employ literal roughnums for useful irrational numbers, such as π (~3.141592653589793) or e (~2.718281828459045). A roughnum therefore serves as a rational approximation, but without any indication as to what the error tolerance is.
It is possible to envisage roughnums that correspond to JavaScript’s ±∞, ±0, and NaN. However, after consideration, these were rejected.
Operations that produce ∞ in JavaScript will simply raise error in Pyret. Thus dividing 1 by 0 raises an error.
Similarly, modulo with a second argument of 0, which produces NaN in JavaScript, in Pyret raises an error.
There is a well-defined total ordering of the precise rationals. Given two precise rationals, the first is either equal to, less than, or greater than the second: no four ways about it. Thus: 1 = 1; 1 < 2.5; and 1 > 1/2. Related operations that are possible are: <=, >=, !=, max, min.
Precise rationals cannot be compared against roughnums. Attempts to do so will throw error.
Roughnums cannot be compared for equality with each other. Attempts to do so will throw error.
Roughnums can be compared for < and >. It is possible to retrieve a kind of equality predicate by checking that two roughnums are neither < nor > than each other: but that is the user’s prerogative and risk.
Numbers and objects containing numbers can do fuzzy number
equality via a handful of within functions. As a representative
example, within-abs(err) produces a predicate that compares the
numbers in the corresponding positions inside its two arguments,
and pronounces them equal within err if their difference is
less than err.
within-abs(0.11)(2, 2.1) is true
The 0.11 here is an absolute error: the predicate checks that 2
and 2.1 are indeed within 0.11 of each other. (The difference
has to be less than or equal to the error tolerance. Thus
within-abs(0.1)(2, 2.1) is also true, whereas within-abs(0.09)(2,
2.1) is false.)
The variant within-rel
takes a relative error:
within-rel(0.1)(200, 210) is true
This checks that 200 and 210 are within 0.1 (i.e., 10%) of each other. The fraction is calculated relative to the difference of the two arguments, so the relative error of 0.1 corresponds here to an absolute error of 0.1 × ave(200, 210) = 20.5.
Two other variants are within-abs-now and within-rel-now. These
check that the arguments satisfy the approximation at least at
the time of
the call, and not necessarily in perpetuity.
Since relative tolerance is more commonly used than absolute, the
shorter names within and within-now are provided for
within-rel and within-rel-now respectively.
The within functions take arguments that are arbitrary
structures, and do a component-wise comparison. If the arguments
are known to be numbers, it may be more efficient to use
num-within-abs and num-within-rel (aka num-within).
These are: +, - (subtraction and negation), *, /, num-abs.
The result is guaranteed to be a precise rational if the
arguments are precise rationals. If at least one of the arguments
is rough, the result is rough. Thus, a possible way to get the
roughnum equivalent of a precise rational is to add it to ~0
(but see num-to-roughnum below).
num-floor, num-ceiling, and num-round are three ways to get
an integer from any number. (Floor gives the largest integer
smaller than; ceiling gives the smallest integer larger than; and round
gives the closest integer with a preference for an even result in
case of a tie.)
It was decided that these should return exact results even if the argument is rough. Rationale: the most frequent (only?) use for these operations when applied to a rough argument is to groom that value before feeding it to functions that accept only exact integers.
(A proposed anti-rationale was that it doesn’t make sense for the floor of a rough number such as the population of a country to not also be rough. However, taking the floor on such a value is a strange thing to do anyway, so presumably the user knows what they’re doing.)
Functions such as num-sqrt, num-log, num-exp, num-expt,
num-sin, num-cos, num-tan, num-asin,
num-acos, num-atan often lead to irrational answers despite being
supplied rational arguments. For these, except for extremely
special cases, the Pyret result will be a roughnum.
Thus, num-sin(1) yields ~0.8414709848078965. num-sin(0) however
yields the integer 0. A roughnum argument always produces a
roughnum answer: num-sin(~0) gives ~0.
num-is-rational-
returns true for non-roughnums, viz., integer (whether JS native num or bignum), non-integral rational.
num-is-fixnum-
returns true for rationals that are represented as JS native numbers. (This is a reliable test only for numbers that are integral.)
num-is-integer-
returns true for non-roughnums that are integral.
num-is-roughnum-
returns true for roughnums only.
-
num-is-positive,num-is-negative,num-is-non-positive,num-is-non-negative -
work on all numbers (incl. roughnums) with the appropriate meaning.
These predicates (except for num-is-fixnum) are also provided as type annotations:
NumRational, NumInteger, Roughnum, NumPositive,
NumNegative,
NumNonPositive, NumNonNegative.
(Should the annotation Roughnum be rather NumRoughnum?)
num-to-rational-
removes roughness.
num-to-roughnum-
adds it.
num-to-fixnum-
returns the closest equivalent JS number
|
Note
|
num-to-integer not provided, as trio of
{num-round, num-floor, num-ceiling}
suffices.
|
num-to-rational is aka num-exact.
In the pyret-lang branch named roughnum. Files changed
include the library file from Danny Yoo,
lib/js-numbers/src/js-numbers.js,
with roughnum code added and all the floatpoint, complex and
inexactness code excised.
The most current roughnum branch can be tried online at https://rough-pyret.herokuapp.com/editor.
The test suites are test-roughnum.arr and test-within.arr.