Title

Exact Infinities

Author

Chongkai Zhu

This SRFI is currently in ``draft'' status. To see an explanation of each status that a SRFI can hold, see here. It will remain in draft status until 2005/08/17, or as amended. To provide input on this SRFI, please mailto:srfi-73@srfi.schemers.org. See instructions here to subscribe to the list. You can access previous messages via the archive of the mailing list.

Abstract

Many Scheme implementations support exact arbitrary-precision integer arithmetic as well as exact rational number computation. This SRFI extends the rational numbers of R5RS by adding two rational infinities (1/0, -1/0).

With infinities added to the number system we find that division by zero "works". It lets initialization of variables precede bounds checks and gives flexibility in placement of those checks.

Issues

SRFI-70 compatible

Actually this SRFI was inspired by SRFI-70 (inexact infinities). I once discussed exact infinities in SRFI-70 mail list with Aubrey Jaffer, but he didn't intend to include exact infinities in SRFI-70. So here I define them as another SRFI. For no ambiguity, in the rationale and specification part I will use #e1/0 for rational infinity and #i1/0 for inexact infinity. Since SRFI-70 is still in draft status, I think we should work together to make SRFI-70 and this SRFI to be compatible to each other. In the current specification part, I leave many "..." to indicate this part should be defined in SRFI-70, or, leave unchanged as in R5RS. Nearly all changes on R5RS are orthogonal to SRFI-70, with the only exception that I define infinite? instead of finite?.

Finally, I have to say that the semantics of infinities in SRFI-70 and this SRFI is different. According to SRFI-70:

"The interpretation of real infinities is that #i1/0 represents real numbers greater than can be encoded by finite inexacts in the implementation (> 179.76931348623158e306 for IEEE-754 64-bit flonums) and that #i-1/0 represents numbers less than can be encoded by finite inexacts in the implementation (< -179.76931348623158e306 for IEEE-754 64-bit flonums)."

The interpretation of rational infinities here is that they are exact, rational numbers with denominator 0.

Should there be a #e0/0?

SRFI-70 defines an optional #i0/0. Should I also define an (optional) #e0/0?

Rationale

The exact rational operations of addition, subtraction, multiplication, and division, plus a variety of other useful operations (comparison, reading, writing) form a useful suite of routines and is defined in Scheme spec. The construction of these programs depends on the availability of arbitrary precision integer arithmetic.

This SRFI extend the rational numbers of R5RS by adding two rational infinities (#e1/0, #e-1/0). These infinities arise as the result of exact division by 0.

There are two rationales for adding exact infinity: aesthetic and utilitarian. Aesthetically, having exact infinites allows one level of calculation (exact division by 0) to be executed before bounds checking, just as SRFI-70 has inexact infinites to enable inexact division by 0. A Scheme with only inexact infinity but no exact infinity is also not aesthetically satisfied. Another rationale is utility. For example, interval arithmetic may need rational infinity.

Because there are both positive infinity and negative infinity, we are forced to have two zeroes: positive 0 and negative -0. Among other reasons for preferring it, this model is more suited to transcendental functions allowing one to describe branch cuts more specifically. (The idea "-0" comes from Richard J. Fateman, see references for detail.)

For any operation that involves both exact (infinity) and inexact numbers, it is a common arithmetic that all exact numbers will first be coerced into inexact and then the computation continues. So in this SRFI I will not concern on inexact numbers.

Specification

(Based on R5RS. "..." means this part should be defined same as SRFI-70)

6.2.4 Syntax of numerical constants

...

Negative exact infinity is written "#e-1/0". Positive exact infinity is written "#e1/0" or "#e+1/0". The positive exact zero is written "0" or "+0". The negative exact zero is written "-0".

...

6.2.5 Numerical operations

The reader is referred to section 1.3.3 Entry format for a summary of the naming conventions used to specify restrictions on the types of arguments to numerical routines.

The examples used in this section assume that any numerical constant written using an exact notation is indeed represented as an exact number. Some examples also assume that certain numerical constants written using an inexact notation can be represented without loss of accuracy; the inexact constants were chosen so that this is likely to be true in implementations that use flonums to represent inexact numbers.

 

procedure: number? obj
 
procedure: complex? obj
 
procedure: real? obj
 
procedure: rational? obj
 
procedure: integer? obj
These numerical type predicates can be applied to any kind of argument, including non-numbers. They return #t if the object is of the named type, and otherwise they return #f. In general, if a type predicate is true of a number then all higher type predicates are also true of that number. Consequently, if a type predicate is false of a number, then all lower type predicates are also false of that number.

If z is an inexact complex number, then `(real? z)' is true if and only if `(zero? (imag-part z))' is true. If x is an inexact real number, then `(integer? x)' is true if and only if

    (and (not (infinite? x)) (= x (round x)))
(complex? 3+4i)                        ==>  #t
(complex? 3)                           ==>  #t
(real? 3)                              ==>  #t
(real? -2.5+0.0i)                      ==>  #t
(real? #e1e10)                         ==>  #t
(rational? 6/10)                       ==>  #t
(rational? 6/3)                        ==>  #t
(integer? 3+0i)                        ==>  #t
(integer? 3.0)                         ==>  #t
(integer? 8/4)                         ==>  #t
(complex? #e1/0)                       ==>  #t
(real? #e-1/0)                         ==>  #t
(rational? #e1/0)                      ==>  #t
(integer? #e-1/0)                      ==>  #f

Note: The behavior of these type predicates on inexact numbers is unreliable, since because any inaccuracy may affect the result.

Note: In many implementations the rational? procedure will be the same as real?, and the complex? procedure will be the same as number?, but unusual implementations may be able to represent some irrational numbers exactly or may extend the number system to support some kind of non-complex numbers.

 

procedure: exact? z
 
procedure: inexact? z
These numerical predicates provide tests for the exactness of a quantity. For any Scheme number, precisely one of these predicates is true.
(exact? #e1/0)               ==>  #t
procedure: = z1 z2 z3 ...
 
procedure: < x1 x2 x3 ...
 
procedure: > x1 x2 x3 ...
 
procedure: <= x1 x2 x3 ...
 
procedure: >= x1 x2 x3 ...
These procedures return #t if their arguments are (respectively): equal, monotonically increasing, monotonically decreasing, monotonically nondecreasing, or monotonically nonincreasing.
(= #e1/0 #e1/0)                 ==>  #t
(= #e-1/0 #e1/0)                ==>  #f
(= #e-1/0 #e-1/0)               ==>  #t
(= #i1/0 #e1/0)                 ==>  #t
(= #e-1/0 #i-1/0)               ==>  #t
(= 0 -0)                        ==>  #t

For any finite positive number x:

(< #e-1/0 -x -0 0 x 1/0))       ==>  #t

These predicates are required to be transitive.

Note: The traditional implementations of these predicates in Lisp-like languages are not transitive.

Note: While it is not an error to compare inexact numbers using these predicates, the results may be unreliable because a small inaccuracy may affect the result; this is especially true of = and zero?. When in doubt, consult a numerical analyst.

 

library procedure: infinite? z
 
library procedure: zero? z
 
library procedure: positive? x
 
library procedure: negative? x
 
library procedure: odd? n
 
library procedure: even? n
These numerical predicates test a number for a particular property, returning #t or #f. See note above.
(positive? #e1/0)             ==>  #t
(negative? #e-1/0)            ==>  #t
(infinite? #e-1/0)            ==>  #t
(infinite? #e0/0)             ==>  #t
(positive? 0)                 ==>  #f
(negative? -0)                ==>  #f

 

library procedure: max x1 x2 ...
 
library procedure: min x1 x2 ...
These procedures return the maximum or minimum of their arguments.
(max 3 4)                              ==>  4    ; exact
(max 3.9 4)                            ==>  4.0  ; inexact

For any finite exact number x, any finite inexact number y:

(max #e1/0 x)                            ==>  #e1/0
(max #e1/0 y)                            ==>  #i1/0

Note: If any argument is inexact, then the result will also be inexact (unless the procedure can prove that the inaccuracy is not large enough to affect the result, which is possible only in unusual implementations). If `min' or `max' is used to compare numbers of mixed exactness, and the numerical value of the result cannot be represented as an inexact number without loss of accuracy, then the procedure may report a violation of an implementation restriction.

 

procedure: + z1 ...
 
procedure: * z1 ...
These procedures return the sum or product of their arguments.
(+ 3 4)                                ==>  7
(+ 3)                                  ==>  3
(+)                                    ==>  0
(+ #e1/0 #e1/0)                        ==>  #e1/0
(+ #e1/0 #e-1/0)                       ==>  #i0/0, or raise an error if the Scheme implementation doesn't support #i0/0
(+ 0 -0)                               ==>  0
(+ 0 0)                                ==>  0
(+ -0 -0)                              ==>  -0

(* 4)                                  ==>  4
(*)                                    ==>  1
(* 5 #e1/0)                            ==>  #e1/0
(* -5 #e1/0)                           ==>  #e-1/0
(* #e1/0 #e1/0)                        ==>  #e1/0
(* #e1/0 #e-1/0)                       ==>  #e-1/0
(* 0 #e1/0)                            ==>  #i0/0, or raise an error if the Scheme implementation doesn't support #i0/0
(* 0 -0)                               ==>  -0
(* 0 2)                                ==>  0
(* -0 -2)                              ==>  0
(* -0 2)                               ==>  -0
(* 0 #e1/0)                            ==>  #i0/0, or raise an error if the Scheme implementation doesn't support #i0/0

For any finite exact number z:

(+ #e1/0 z)                            ==>  #e1/0
(+ #e-1/0 z)                           ==>  #e-1/0

 

procedure: - z1 z2
 
procedure: - z
 
optional procedure: - z1 z2 ...
 
procedure: / z1 z2
 
procedure: / z
 
optional procedure: / z1 z2 ...
With one argument, these procedures return the additive or multiplicative inverse of their argument.

With two or more arguments:

(- z1 . z2)   =>   (apply + z1 (map - z2))
(/ z1 . z2)   =>   (apply * z1 (map / z2))

(- 0)                                  ==>  -0
(- -0)                                 ==>  0
(- #e1/0)                              ==>  #e-1/0
(- #-e1/0)                             ==>  #e1/0
(- 3)                                  ==>  -3

(/ 0)                                  ==>  #e1/0
(/ -0)                                 ==>  #e-1/0
(/ #e1/0)                              ==>  #0
(/ #e-1/0)                             ==>  #-0
(/ 3)                                  ==>  1/3

 

library procedure: abs x
`Abs' returns the absolute value of its argument.
(abs -7)                               ==>  7
(abs #e-1/0)                           ==>  #e1/0
(abs -0)                               ==>  0
...
procedure: numerator q
 
procedure: denominator q
These procedures return the numerator or denominator of their argument; the result is computed as if the argument was represented as a fraction in lowest terms. The denominator is always positive or zero. The denominator of 0 is defined to be 1.
(numerator (/ 6 4))                    ==>  3
(denominator (/ 6 4))                  ==>  2
(denominator
  (exact->inexact (/ 6 4)))            ==> 2.0
(denominator #e1/0)                    ==>  1
(denominator #e-1/0)                   ==>  -1
(numerator #e1/0)                      ==>  0
(numerator #e-1/0)                     ==>  0

 

procedure: floor x
 
procedure: ceiling x
 
procedure: truncate x
 
procedure: round x
These procedures return integers. `Floor' returns the largest integer not larger than x. `Ceiling' returns the smallest integer not smaller than x. `Truncate' returns the integer closest to x whose absolute value is not larger than the absolute value of x. `Round' returns the closest integer to x, rounding to even when x is halfway between two integers.

Rationale: `Round' rounds to even for consistency with the default rounding mode specified by the IEEE floating point standard.

Note: If the argument to one of these procedures is inexact, then the result will also be inexact. If an exact value is needed, the result should be passed to the `inexact->exact' procedure.

(floor -4.3)                           ==>  -5.0
(ceiling -4.3)                         ==>  -4.0
(truncate -4.3)                        ==>  -4.0
(round -4.3)                           ==>  -4.0

(floor 3.5)                            ==>  3.0
(ceiling 3.5)                          ==>  4.0
(truncate 3.5)                         ==>  3.0
(round 3.5)                            ==>  4.0  ; inexact

(round 7/2)                            ==>  4    ; exact
(round 7)                              ==>  7

(floor #e1/0)                          ==>  #e1/0
(ceiling #e-1/0)                       ==>  #e-1/0

...

procedure: exact->inexact z
 
procedure: inexact->exact z
`Exact->inexact' returns an inexact representation of z. The value returned is the inexact number that is numerically closest to the argument. If an exact argument has no reasonably close inexact equivalent, then a violation of an implementation restriction may be reported.

`Inexact->exact' returns an exact representation of z. The value returned is the exact number that is numerically closest to the argument. If an inexact argument has no reasonably close exact equivalent, then a violation of an implementation restriction may be reported.

These procedures implement the natural one-to-one correspondence between exact and inexact integers throughout an implementation-dependent range. See section 6.2.3 Implementation restrictions.

(exact->inexact #e1/0)                  ==>  #i1/0
(inexact->exact #i1/0)                  ==>  #e1/0

6.2.6 Numerical input and output

 

 

procedure: number->string z
 
procedure: number->string z radix
Radix must be an exact integer, either 2, 8, 10, or 16. If omitted, radix defaults to 10. The procedure `number->string' takes a number and a radix and returns as a string an external representation of the given number in the given radix such that
(let ((number number)
      (radix radix))
  (eqv? number
        (string->number (number->string number
                                        radix)
                        radix)))

is true. It is an error if no possible result makes this expression true.

If z is inexact, the radix is 10, and the above expression can be satisfied by a result that contains a decimal point, then the result contains a decimal point and is expressed using the minimum number of digits (exclusive of exponent and trailing zeroes) needed to make the above expression true [howtoprint], [howtoread]; otherwise the format of the result is unspecified.

The result returned by `number->string' never contains an explicit radix prefix.

Note: The error case can occur only when z is not a complex number or is a complex number with a non-rational real or imaginary part.

Rationale: If z is an inexact number represented using flonums, and the radix is 10, then the above expression is normally satisfied by a result containing a decimal point. The unspecified case allows for infinities, NaNs, and non-flonum representations.

 

procedure: string->number string
 
procedure: string->number string radix
Returns a number of the maximally precise representation expressed by the given string. Radix must be an exact integer, either 2, 8, 10, or 16. If supplied, radix is a default radix that may be overridden by an explicit radix prefix in string (e.g. "#o177"). If radix is not supplied, then the default radix is 10. If string is not a syntactically valid notation for a number, then `string->number' returns #f.
(string->number "100")                 ==>  100
(string->number "100" 16)              ==>  256
(string->number "1e2")                 ==>  100.0
(string->number "15##")                ==>  1500.0
(string->number "#e1/0")               ==>  #e1/0
(string->number "#e-1/0")              ==>  #e-1/0

Note: The domain of `string->number' may be restricted by implementations in the following ways. `String->number' is permitted to return #f whenever string contains an explicit radix prefix. If all numbers supported by an implementation are real, then `string->number' is permitted to return #f whenever string uses the polar or rectangular notations for complex numbers. If all numbers are integers, then `string->number' may return #f whenever the fractional notation is used. If all numbers are exact, then `string->number' may return #f whenever an exponent marker or explicit exactness prefix is used, or if a # appears in place of a digit. If all inexact numbers are integers, then `string->number' may return #f whenever a decimal point is used.

Implementation

Here is my implementation, which is based on a Scheme implementation that supports arbitrary-big integer arithmetic as well as exact rational number computation. To avoid confusion with identifies in base-Scheme, all procedures defined in this SRFI (except infinite?) and prefixed with "my" or "my-". This reference implementation also requires SRFI-9, SRFI-13, SRFI-16, and SRFI-23.

(separate file attached)

Examples:

> (exact->string (my-max (string->exact "-1/2")
                         (string->exact "-1"))) ;(max -1/2 -1)
"-1/2"
> (exact->string (my+ (string->exact "-1/2")
                      (string->exact "1/3")
                      (string->exact "0")))
"-1/6"
> (exact->string (my* (string->exact "-0")
                      (string->exact "0")))
"-0"
> (exact->string (my- (string->exact "0")
                      (string->exact "1/0")))
"-1/0"

References

Copyright

Copyright (C) Chongkai Zhu (2005). All Rights Reserved.

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.



Author: Chongkai Zhu
Editors: Mike Sperber