Chapter 11

Arithmetic

This chapter describes Scheme’s libraries for more specialized numerical operations: fixnum and flonum arithmetic, as well as bitwise operations on exact integer objects.

11.1  Bitwise operations

A number of procedures operate on the binary two’s-complement representations of exact integer objects: Bit positions within an exact integer object are counted from the right, i.e. bit 0 is the least significant bit. Some procedures allow extracting bit fields, i.e., number objects representing subsequences of the binary representation of an exact integer object. Bit fields are always positive, and always defined using a finite number of bits.

11.2  Fixnums

Every implementation must define its fixnum range as a closed interval

such that w is a (mathematical) integer w ≥ 24. Every mathematical integer within an implementation’s fixnum range must correspond to an exact integer object that is representable within the implementation. A fixnum is an exact integer object whose value lies within this fixnum range.

This section describes the (rnrs arithmetic fixnums (6))library, which defines various operations on fixnums. Fixnum operations perform integer arithmetic on their fixnum arguments, but raise an exception with condition type &implementation-restriction if the result is not a fixnum.

This section uses fx, fx₁, fx₂, etc., as parameter names for arguments that must be fixnums.

Returns #t if obj is an exact integer object within the fixnum range, #f otherwise.

These procedures return w, - 2^w-1 and 2^w-1 - 1: the width, minimum and the maximum value of the fixnum range, respectively.

These procedures return #t if their arguments are (respectively): equal, monotonically increasing, monotonically decreasing, monotonically nondecreasing, or monotonically nonincreasing, #f otherwise.

These numerical predicates test a fixnum for a particular property, returning #t or #f. The five properties tested by these procedures are: whether the number object is zero, greater than zero, less than zero, odd, or even.

These procedures return the maximum or minimum of their arguments.

These procedures return the sum or product of their arguments, provided that sum or product is a fixnum. An exception with condition type &implementation-restriction is raised if that sum or product is not a fixnum.

With two arguments, this procedure returns the difference fx₁ - fx₂, provided that difference is a fixnum.

With one argument, this procedure returns the additive inverse of its argument, provided that integer object is a fixnum.

An exception with condition type &assertion is raised if the mathematically correct result of this procedure is not a fixnum.

(fx- (least-fixnum))     &assertion exception

Fx₂ must be nonzero. These procedures implement number-theoretic integer division and return the results of the corresponding mathematical operations specified in report section on “Integer division”.

(fxdiv fx₁ fx₂)                 ⇒ fx₁ div fx₂
(fxmod fx₁ fx₂)                 ⇒ fx₁ mod fx₂
(fxdiv-and-mod fx₁ fx₂)     
                ⇒ fx₁ div fx₂, fx₁ mod fx₂
; two return values
(fxdiv0 fx₁ fx₂)                ⇒ fx₁ divsb0 fx₂
(fxmod0 fx₁ fx₂)                ⇒ fx₁ modsb0 fx₂
(fxdiv0-and-mod0 fx₁ fx₂)   
                ⇒ fx₁ fx₁ divsb0 fx₂, fx₁ modsb0 fx₂
; two return values

Returns the two fixnum results of the following computation:

(let* ((s (+ fx₁ fx₂ fx₃))
       (s0 (mod0 s (expt 2 (fixnum-width))))
       (s1 (div0 s (expt 2 (fixnum-width)))))
  (values s0 s1))

Returns the two fixnum results of the following computation:

(let* ((d (- fx₁ fx₂ fx₃))
       (d0 (mod0 d (expt 2 (fixnum-width))))
       (d1 (div0 d (expt 2 (fixnum-width)))))
  (values d0 d1))

Returns the two fixnum results of the following computation:

(let* ((s (+ (* fx₁ fx₂) fx₃))
       (s0 (mod0 s (expt 2 (fixnum-width))))
       (s1 (div0 s (expt 2 (fixnum-width)))))
  (values s0 s1))

Returns the unique fixnum that is congruent mod 2^w to the one’s-complement of fx.

These procedures return the fixnum that is the bit-wise “and”, “inclusive or”, or “exclusive or” of the two’s complement representations of their arguments. If they are passed only one argument, they return that argument. If they are passed no arguments, they return the fixnum (either - 1 or 0) that acts as identity for the operation.

Returns the fixnum that is the bit-wise “if” of the two’s complement representations of its arguments, i.e. for each bit, if it is 1 in fx₁, the corresponding bit in fx₂ becomes the value of the corresponding bit in the result, and if it is 0, the corresponding bit in fx₃ becomes the corresponding bit in the value of the result. This is the fixnum result of the following computation:

(fxior (fxand fx₁ fx₂)
       (fxand (fxnot fx₁) fx₃))

If fx is non-negative, this procedure returns the number of 1 bits in the two’s complement representation of fx. Otherwise it returns the result of the following computation:

(fxnot (fxbit-count (fxnot ei)))

Returns the number of bits needed to represent fx if it is positive, and the number of bits needed to represent (fxnot fx) if it is negative, which is the fixnum result of the following computation:

(do ((result 0 (+ result 1))
     (bits (if (fxnegative? fx)
               (fxnot fx)
               fx)
           (fxarithmetic-shift-right bits 1)))
    ((fxzero? bits)
     result))

Returns the index of the least significant 1 bit in the two’s complement representation of fx. If fx is 0, then - 1 is returned.

(fxfirst-bit-set 0)                ⇒  -1
(fxfirst-bit-set 1)                ⇒  0
(fxfirst-bit-set -4)               ⇒  2

Fx₂ must be non-negative and less than (fixnum-width). The fxbit-set? procedure returns #t if the fx₂th bit is 1 in the two’s complement representation of fx₁, and #f otherwise. This is the fixnum result of the following computation:

(not
  (fxzero?
    (fxand fx₁
           (fxarithmetic-shift-left 1 fx₂))))

Fx₂ must be non-negative and less than (fixnum-width). Fx₃ must be 0 or 1. The fxcopy-bit procedure returns the result of replacing the fx₂th bit of fx₁ by fx₃, which is the result of the following computation:

(let* ((mask (fxarithmetic-shift-left 1 fx₂)))
  (fxif mask
        (fxarithmetic-shift-left fx₃ fx₂)
        fx₁))

Fx₂ and fx₃ must be non-negative and less than (fixnum-width). Moreover, fx₂ must be less than or equal to fx₃. The fxbit-field procedure returns the number represented by the bits at the positions from fx₂ (inclusive) to fx₃ (exclusive), which is the fixnum result of the following computation:

(let* ((mask (fxnot
              (fxarithmetic-shift-left -1 fx₃))))
  (fxarithmetic-shift-right (fxand fx₁ mask)
                            fx₂))

Fx₂ and fx₃ must be non-negative and less than (fixnum-width). Moreover, fx₂ must be less than or equal to fx₃. The fxcopy-bit-field procedure returns the result of replacing in fx₁ the bits at positions from fx₂ (inclusive) to fx₃ (exclusive) by the corresponding bits in fx₄, which is the fixnum result of the following computation:

(let* ((to    fx₁)
       (start fx₂)
       (end   fx₃)
       (from  fx₄)
       (mask1 (fxarithmetic-shift-left -1 start))
       (mask2 (fxnot
               (fxarithmetic-shift-left -1 end)))
       (mask (fxand mask1 mask2)))
  (fxif mask
        (fxarithmetic-shift-left from start)
        to))

The absolute value of fx₂ must be less than (fixnum-width). If

(floor (* fx₁ (expt 2 fx₂)))

is a fixnum, then that fixnum is returned. Otherwise an exception with condition type &implementation-restriction is raised.

Fx₂ must be non-negative, and less than (fixnum-width). The fxarithmetic-shift-left procedure behaves the same as fxarithmetic-shift, and (fxarithmetic-shift-right fx₁ fx₂) behaves the same as (fxarithmetic-shift fx₁ (fx- fx₂)).

Fx₂, fx₃, and fx₄ must be non-negative and less than (fixnum-width). Fx₂ must be less than or equal to fx₃. Fx₄ must be less than the difference between fx₃ and fx₂. The fxrotate-bit-field procedure returns the result of cyclically permuting in fx₁ the bits at positions from fx₂ (inclusive) to fx₃ (exclusive) by fx₄ bits towards the more significant bits, which is the result of the following computation:

(let* ((n     fx₁)
       (start fx₂)
       (end   fx₃)
       (count fx₄)
       (width (fx- end start)))
  (if (fxpositive? width)
      (let* ((count (fxmod count width))
             (field0
               (fxbit-field n start end))
             (field1
               (fxarithmetic-shift-left
                 field0 count))
             (field2
               (fxarithmetic-shift-right
                 field0 (fx- width count)))
             (field (fxior field1 field2)))
        (fxcopy-bit-field n start end field))
      n))

Fx₂ and fx₃ must be non-negative and less than (fixnum-width). Moreover, fx₂ must be less than or equal to fx₃. The fxreverse-bit-field procedure returns the fixnum obtained from fx₁ by reversing the order of the bits at positions from fx₂ (inclusive) to fx₃ (exclusive).

(fxreverse-bit-field #b1010010 1 4)    
                ⇒  88 ; #b1011000

11.3  Flonums

This section describes the (rnrs arithmetic flonums (6))library.

This section uses fl, fl₁, fl₂, etc., as parameter names for arguments that must be flonums, and ifl as a name for arguments that must be integer-valued flonums, i.e., flonums for which the integer-valued? predicate returns true.

Returns #t if obj is a flonum, #f otherwise.

Returns the best flonum representation of x.

The value returned is a flonum that is numerically closest to the argument.

Note:   If flonums are represented in binary floating point, then implementations should break ties by preferring the floating-point representation whose least significant bit is zero.

These procedures return #t if their arguments are (respectively): equal, monotonically increasing, monotonically decreasing, monotonically nondecreasing, or monotonically nonincreasing, #f otherwise. These predicates must be transitive.

(fl= +inf.0 +inf.0)                   ⇒  #t
(fl= -inf.0 +inf.0)                   ⇒  #f
(fl= -inf.0 -inf.0)                   ⇒  #t
(fl= 0.0 -0.0)                        ⇒  #t
(fl< 0.0 -0.0)                        ⇒  #f
(fl= +nan.0 fl)                       ⇒  #f
(fl< +nan.0 fl)                       ⇒  #f

These numerical predicates test a flonum for a particular property, returning #t or #f. The flinteger? procedure tests whether the number object is an integer, flzero? tests whether it is fl=? to zero, flpositive? tests whether it is greater than zero, flnegative? tests whether it is less than zero, flodd? tests whether it is odd, fleven? tests whether it is even, flfinite? tests whether it is not an infinity and not a NaN, flinfinite? tests whether it is an infinity, and flnan? tests whether it is a NaN.

(flnegative? -0.0)           ⇒ #f
(flfinite? +inf.0)           ⇒ #f
(flfinite? 5.0)              ⇒ #t
(flinfinite? 5.0)            ⇒ #f
(flinfinite? +inf.0)         ⇒ #t

Note:   (flnegative? -0.0) must return #f, else it would lose the correspondence with (fl< -0.0 0.0), which is #f according to IEEE 754 [7].

These procedures return the maximum or minimum of their arguments. They always return a NaN when one or more of the arguments is a NaN.

These procedures return the flonum sum or product of their flonum arguments. In general, they should return the flonum that best approximates the mathematical sum or product. (For implementations that represent flonums using IEEE binary floating point, the meaning of “best” is defined by the IEEE standards.)

(fl+ +inf.0 -inf.0)              ⇒  +nan.0
(fl+ +nan.0 fl)                  ⇒  +nan.0
(fl* +nan.0 fl)                  ⇒  +nan.0

With two or more arguments, these procedures return the flonum difference or quotient of their flonum arguments, associating to the left. With one argument, however, they return the additive or multiplicative flonum inverse of their argument. In general, they should return the flonum that best approximates the mathematical difference or quotient. (For implementations that represent flonums using IEEE binary floating point, the meaning of “best” is reasonably well-defined by the IEEE standards.)

(fl- +inf.0 +inf.0)              ⇒  +nan.0

For undefined quotients, fl/ behaves as specified by the IEEE standards:

(fl/ 1.0 0.0)          ⇒ +inf.0
(fl/ -1.0 0.0)         ⇒ -inf.0
(fl/ 0.0 0.0)          ⇒ +nan.0

Returns the absolute value of fl.

These procedures implement number-theoretic integer division and return the results of the corresponding mathematical operations specified in report section on “Integer division”. For zero divisors, these procedures may return a NaN or some unspecified flonum.

(fldiv fl₁ fl₂)                 ⇒ fl₁ div fl₂
(flmod fl₁ fl₂)                 ⇒ fl₁ mod fl₂
(fldiv-and-mod fl₁ fl₂)     
                ⇒ fl₁ div fl₂, fl₁ mod fl₂
; two return values
(fldiv0 fl₁ fl₂)                ⇒ fl₁ div₀ fl₂
(flmod0 fl₁ fl₂)                ⇒ fl₁ mod₀ fl₂
(fldiv0-and-mod0 fl₁ fl₂)   
                ⇒ fl₁ div₀ fl₂, fl₁ mod₀ fl₂
; two return values

These procedures return the numerator or denominator of fl as a flonum; the result is computed as if fl was represented as a fraction in lowest terms. The denominator is always positive. The denominator of 0.0 is defined to be 1.0.

(flnumerator +inf.0)                   ⇒  +inf.0
(flnumerator -inf.0)                   ⇒  -inf.0
(fldenominator +inf.0)                 ⇒  1.0
(fldenominator -inf.0)                 ⇒  1.0
(flnumerator 0.75)                     ⇒  3.0 ; probably
(fldenominator 0.75)                   ⇒  4.0 ; probably

Implementations should implement following behavior:

(flnumerator -0.0)                     ⇒ -0.0

These procedures return integral flonums for flonum arguments that are not infinities or NaNs. For such arguments, flfloor returns the largest integral flonum not larger than fl. The flceiling procedure returns the smallest integral flonum not smaller than fl. The fltruncate procedure returns the integral flonum closest to fl whose absolute value is not larger than the absolute value of fl. The flround procedure returns the closest integral flonum to fl, rounding to even when fl represents a number halfway between two integers.

Although infinities and NaNs are not integer objects, these procedures return an infinity when given an infinity as an argument, and a NaN when given a NaN:

(flfloor +inf.0)                               ⇒  +inf.0
(flceiling -inf.0)                             ⇒  -inf.0
(fltruncate +nan.0)                            ⇒  +nan.0

These procedures compute the usual transcendental functions. The flexp procedure computes the base-e exponential of fl. The fllog procedure with a single argument computes the natural logarithm of fl (not the base ten logarithm); (fllog fl₁ fl₂) computes the base-fl₂ logarithm of fl₁. The flasin, flacos, and flatan procedures compute arcsine, arccosine, and arctangent, respectively. (flatan fl₁ fl₂) computes the arc tangent of fl₁/fl₂.

See report section on “Transcendental functions” for the underlying mathematical operations. In the event that these operations do not yield a real result for the given arguments, the result may be a NaN, or may be some unspecified flonum.

Implementations that use IEEE binary floating-point arithmetic should follow the relevant standards for these procedures.

(flexp +inf.0)                        ⇒ +inf.0
(flexp -inf.0)                        ⇒ 0.0
(fllog +inf.0)                        ⇒ +inf.0
(fllog 0.0)                           ⇒ -inf.0
(fllog -0.0)                          ⇒ unspecified
; if -0.0 is distinguished
(fllog -inf.0)                        ⇒ +nan.0
(flatan -inf.0)               
                ⇒ -1.5707963267948965
; approximately
(flatan +inf.0)               
                ⇒ 1.5707963267948965
; approximately

Returns the principal square root of fl. For - 0.0, flsqrt should return - 0.0; for other negative arguments, the result may be a NaN or some unspecified flonum.

(flsqrt +inf.0)                       ⇒  +inf.0
(flsqrt -0.0)                         ⇒  -0.0

Either fl₁ should be non-negative, or, if fl₁ is negative, fl₂ should be an integer object. The flexpt procedure returns fl₁ raised to the power fl₂. If fl₁ is negative and fl₂ is not an integer object, the result may be a NaN, or may be some unspecified flonum. If fl₁ is zero, then the result is zero.

These condition types could be defined by the following code:

(define-condition-type &no-infinities
    &implementation-restriction
  make-no-infinities-violation
  no-infinities-violation?)

(define-condition-type &no-nans
    &implementation-restriction
  make-no-nans-violation no-nans-violation?)

These types describe that a program has executed an arithmetic operations that is specified to return an infinity or a NaN, respectively, on a Scheme implementation that is not able to represent the infinity or NaN. (See report section on “Representability of infinities and NaNs”.)

Returns a flonum that is numerically closest to fx.

Note:   The result of this procedure may not be numerically equal to fx, because the fixnum precision may be greater than the flonum precision.

11.4  Exact bitwise arithmetic

This section describes the (rnrs arithmetic bitwise (6))library. The exact bitwise arithmetic provides generic operations on exact integer objects. This section uses ei, ei₁, ei₂, etc., as parameter names that must be exact integer objects.

Returns the exact integer object whose two’s complement representation is the one’s complement of the two’s complement representation of ei.

These procedures return the exact integer object that is the bit-wise “and”, “inclusive or”, or “exclusive or” of the two’s complement representations of their arguments. If they are passed only one argument, they return that argument. If they are passed no arguments, they return the integer object (either - 1 or 0) that acts as identity for the operation.

Returns the exact integer object that is the bit-wise “if” of the two’s complement representations of its arguments, i.e. for each bit, if it is 1 in ei₁, the corresponding bit in ei₂ becomes the value of the corresponding bit in the result, and if it is 0, the corresponding bit in ei₃ becomes the corresponding bit in the value of the result. This is the result of the following computation:

(bitwise-ior (bitwise-and ei₁ ei₂)
             (bitwise-and (bitwise-not ei₁) ei₃))

If ei is non-negative, this procedure returns the number of 1 bits in the two’s complement representation of ei. Otherwise it returns the result of the following computation:

(bitwise-not (bitwise-bit-count (bitwise-not ei)))

Returns the number of bits needed to represent ei if it is positive, and the number of bits needed to represent (bitwise-not ei) if it is negative, which is the exact integer object that is the result of the following computation:

(do ((result 0 (+ result 1))
     (bits (if (negative? ei)
               (bitwise-not ei)
               ei)
           (bitwise-arithmetic-shift bits -1)))
    ((zero? bits)
     result))

Returns the index of the least significant 1 bit in the two’s complement representation of ei. If ei is 0, then - 1 is returned.

(bitwise-first-bit-set 0)                ⇒  -1
(bitwise-first-bit-set 1)                ⇒  0
(bitwise-first-bit-set -4)               ⇒  2

Ei₂ must be non-negative. The bitwise-bit-set? procedure returns #t if the ei₂th bit is 1 in the two’s complement representation of ei₁, and #f otherwise. This is the result of the following computation:

(not (zero?
       (bitwise-and
         (bitwise-arithmetic-shift-left 1 ei₂)
         ei₁)))

Ei₂ must be non-negative, and ei₃ must be either 0 or 1. The bitwise-copy-bit procedure returns the result of replacing the ei₂th bit of ei₁ by the ei₂th bit of ei₃, which is the result of the following computation:

(let* ((mask (bitwise-arithmetic-shift-left 1 ei₂)))
  (bitwise-if mask
            (bitwise-arithmetic-shift-left ei₃ ei₂)
            ei₁))

Ei₂ and ei₃ must be non-negative, and ei₂ must be less than or equal to ei₃. The bitwise-bit-field procedure returns the number represented by the bits at the positions from ei₂ (inclusive) to ei₃ (exclusive), which is the result of the following computation:

(let ((mask
       (bitwise-not
        (bitwise-arithmetic-shift-left -1 ei₃))))
  (bitwise-arithmetic-shift-right
    (bitwise-and ei₁ mask)
    ei₂))

Ei₂ and ei₃ must be non-negative, and ei₂ must be less than or equal to ei₃. The bitwise-copy-bit-field procedure returns the result of replacing in ei₁ the bits at positions from ei₂ (inclusive) to ei₃ (exclusive) by the corresponding bits in ei₄, which is the fixnum result of the following computation:

(let* ((to    ei₁)
       (start ei₂)
       (end   ei₃)
       (from  ei₄)
       (mask1
         (bitwise-arithmetic-shift-left -1 start))
       (mask2
         (bitwise-not
           (bitwise-arithmetic-shift-left -1 end)))
       (mask (bitwise-and mask1 mask2)))
  (bitwise-if mask
              (bitwise-arithmetic-shift-left from
                                             start)
              to))

Returns the result of the following computation:

(floor (* ei₁ (expt 2 ei₂)))

Examples:

(bitwise-arithmetic-shift -6 -1) 
                ⇒ -3
(bitwise-arithmetic-shift -5 -1) 
                ⇒ -3
(bitwise-arithmetic-shift -4 -1) 
                ⇒ -2
(bitwise-arithmetic-shift -3 -1) 
                ⇒ -2
(bitwise-arithmetic-shift -2 -1) 
                ⇒ -1
(bitwise-arithmetic-shift -1 -1) 
                ⇒ -1

Ei₂ must be non-negative. The bitwise-arithmetic-shift-left procedure returns the same result as bitwise-arithmetic-shift, and

(bitwise-arithmetic-shift-right ei₁ ei₂)

returns the same result as

(bitwise-arithmetic-shift ei₁ (- ei₂)).

Ei₂, ei₃, ei₄ must be non-negative, ei₂ must be less than or equal to ei₃, and ei₄ must be non-negative. procedure returns the result of cyclically permuting in ei₁ the bits at positions from ei₂ (inclusive) to ei₃ (exclusive) by ei₄ bits towards the more significant bits, which is the result of the following computation:

(let* ((n     ei₁)
       (start ei₂)
       (end   ei₃)
       (count ei₄)
       (width (- end start)))
  (if (positive? width)
      (let* ((count (mod count width))
             (field0
               (bitwise-bit-field n start end))
             (field1 (bitwise-arithmetic-shift-left
                       field0 count))
             (field2 (bitwise-arithmetic-shift-right
                       field0
                       (- width count)))
             (field (bitwise-ior field1 field2)))
        (bitwise-copy-bit-field n start end field))
      n))

Ei₂ and ei₃ must be non-negative, and ei₂ must be less than or equal to ei₃. The bitwise-reverse-bit-field procedure returns the result obtained from ei₁ by reversing the order of the bits at positions from ei₂ (inclusive) to ei₃ (exclusive).

(bitwise-reverse-bit-field #b1010010 1 4)   
                ⇒  88 ; #b1011000