Abstraction: ratintvl Version: 2 Date: 4 November 2002; revised 5 November 2002 Author: Mike O'Donnell Changes: Added member_ratintvl?, simplest_ratintvl->rational, choose_ratintvl->rational, std_ratintvl->rational. Minor polish to language and categories. Values in the ratintvl abstraction are closed intervals [r1, r2] with rational endpoints. They are intended to represent approximate information about real numbers, but all procedures are defined in terms of their effects on the intervals. Constructors ------------ (make_ratintvl r1 r2) takes rationals r1 and r2, and returns a representation of the closed interval [r1, r2]. If r1, r2 are not both rationals, report an error. If r1 > r2, report an error. (rational->ratintvl r) returns the closed interval containing only the given rational r. If r is not a rational, report an error. Predicates ---------- (ratintvl? expr) returns #t if expr is a ratintvl, #f otherwise. (point_ratintvl? ri) returns #t if ri is a ratintvl containing precisely one real, #f otherwise. If ri is not a ratintvl, report an error. (member_ratintvl? r ri) returns #t if the rational r is a member of the ratintvl ri, #f otherwise. If r is not a rational, or ri is not a ratintvl, report an error. (contained_ratintvl? ri1 ri2) returns #t if ri1 is a subinterval (possibly equal) of ri2, #f otherwise. If either of ri1, ri2 is not a ratintvl, report an error. (equal_ratintvl? ri1 ri2) returns #t if ri1=ri2, #f otherwise. If either of ri1, ri2 is not a ratintvl, report an error. (precedes_ratinvtl? ri1 ri2) returns #t if all reals in ri1 strictly precede all reals in ri2. If either of ri1, ri2 is not a ratintvl, report an error. (overlaps_ratintvl? ri1 ri2) returns #t if there is at least one real number that is a member of both ri1 and ri2 (equivalently, if the intersection of ri1 and ri2 is not empty), #f otherwise. If either of ri1, ri2 is not a ratintvl, report an error. (lbounds_ratintvl? ri1, ri2) returns #t if ri1 contains at least one real less than all reals in ri2, #f otherwise. If either of ri1, ri2 is not a ratintvl, report an error. (ubounded_ratintvl? ri1, ri2) returns #t if ri2 contains at least one real greater than all reals in ri1, #f otherwise. If either of ri1, ri2 is not a ratintvl, report an error. Operations ---------- (union_ratintvl ri1 ri2) returns the ratintvl containing all reals in ri1 and all reals in ri2. If ri1 and ri2 are not overlapping ratintvls, report an error. (intersect_ratintvl ri1 ri2) returns the ratintvl containing all reals that are in both of ri1 and ri2. If ri1 and ri2 are not overlapping ratintvls, report an error. (add_ratintvl ri1 ri2) returns the ratintvl containing all sums of one real in ri1 plus one real in ri2. If either of ri1, ri2 is not a ratintvl, report an error. (sub_ratintvl ri1 ri2) returns the ratintvl containing all differences of one real in ri1 minus one real in ri2. If either of ri1, ri2 is not a ratintvl, report an error. (mult_ratintvl ri1 ri2) returns the ratintvl containing all products of one real in ri1 times one real in ri2. If either of ri1, ri2 is not a ratintvl, report an error. (div_ratintvl ri1 ri2) returns the ratintvl containing all ratios of one real in ri1 divided by one real in ri2. If either of ri1, ri2 is not a ratintvl, or if ri2 contains 0, report an error. (power_ratintvl ri int) returns the ratintvl containing all values of one real in ri to the integer power int. If ri is not a ratintvl, or if int is not an integer, or if ri contains 0 and int=0, report an error. (simplest_ratintvl ri size) returns the simplest ratintvl containing the ratintvl ri and no bigger than the rational size. The complexity of the ratintvl [nl/dl, nu/du], where nl/dl and nu/du are in lowest terms, is the absolute value of the product of the nonzero values of nl, dl, nu, du. That is, the complexity is usually nl*dl*nu*du, but if either or both of nl, nu =0, it is omitted from the product. If ri is larger than size, report an error. Selectors --------- (min_ratintvl->rational ri) returns the left rational endpoint of ri. If ri is not a ratintvl, report an error. (max_ratintvl->rational ri) returns the right rational endpoint of ri. If ri is not a ratintvl, report an error. Type conversions ---------------- (mid_ratintvl->rational ri) returns the rational midpoint of ri. If ri is not a ratintvl, report an error. (simplest_ratintvl->rational ri) returns the simplest rational in the ratintvl ri. The complexity of the rational n/d, where n/d is in lowest terms, is |n*d|. If ri is not a ratintvl, report an error. (choose_ratintvl->rational ri) returns any rational in the ratintvl ri. The implementation may choose this rational nondeterministically for efficiency. For the interval [n1/d1, n2/d2], a pretty good choice is (n1+n2)/(d1+d2). If ri is not a ratintvl, report an error. String representations ---------------------- (std_ratintvl->string ri) returns a character string representing the ratintvl ri. Use the following format: [,] and are rationals, in the standard Scheme notation. If ri is not a ratintvl, report an error. (decimal_sn_ratintlv->string ri) returns a character string displaying the most accurate decimal representation of ri in scientific notation. Use the following format: .E Each of and is either "-" or "". is one decimal digit from 0-9. is a sequence of 0 or more decimal digits. is a sequence of 1 or more decimal digits. The first , and every digit in , must be significant (i.e., correct for every real in ri). must have no leading 0s, except for a single 0 if the exponent value is 0. If ri is not a ratintvl, or if the most accurate decimal representation has no significant digits, report an error. (decimal_ratintlv->string ri) returns a character string displaying the most accurate representation of ri in normal decimal notation. Use the following format: . is either "-" or "". is a sequence of 1 or more decimal digits. is a sequence of 0 or more decimal digits. Every digit in and must be significant (i.e., correct for every real in ri). must have no leading 0s, except for a single 0 if the integer part is 0. must have trailing 0s if they are significant. If ri is not a ratintvl, or if the most accurate decimal representation has no significant digits, report an error.