Sketchy LISP

An Introduction to Functional Programming in Scheme

2.6 Arithmetics

Because numbers are a very common thing in programs, the first examples in this book used numbers, and many arithmetic procedures already have been introduced in the sections so far. Like other programming languages, Scheme can add, subtract and multiply numbers:

(+ 5 7 9) => 21
(- 5 7 9) => -11
(* 5 7 9) => 315

Unlike most languages, Scheme allows a variable number of arguments in these procedures. + and * accept zero or more arguments. They return the neutral element of the corresponding operation when applied to zero arguments:

(+) => 0
(*) => 1

The - procedure expects at least one argument. When a single argument is passed to it, it negates it, and otherwise it computes the difference of its arguments.

You might have observed that none of the programs discussed before the previous section involved a division, though. This is not because Scheme does not have a procedure for dividing numbers, but because there are several of them. The most versatile of them is the / function, which takes at least one argument and returns the reciprocal value of a single argument or the quotient of two or more arguments:

(/ 2)     => 1/2
(/ 6 3)   => 2
(/ 6 4)   => 3/2
(/ 6 4 2) => 3/4

What is particularly interesting about / is that it returns a rational value, if its result cannot be expressed as an integer. Rational values are a separate type of number, but most procedures which accept integers accept rationals as well. For example you can pass rational values to +:

(+ 2/3 1/3) => 1

The procedure accepts the rational arguments, adds them, and if the result can be expressed as an integer, it returns one.

The quotient procedure limits its result to the integer domain:

(quotient 6 3) => 2
(quotient 6 4) => 1

Quotient implements a function from number theory. Given two numbers a and b, it computes the largest positive integer q so that b*q<=a. Less formally expressed, this is what you get in most programming languages when you divide integers: the integer part of their quotient. Quotient accepts exactly two arguments, which must both be integers. It can never overflow, but when its second argument is larger than its first, it returns zero. When the second argument is zero, its result is undefined:

(quotient x 0) => bottom ; deja vu?

The quotient procedure is accompanied by a bunch of other procedures from number theory. The most frequently used of those are probably modulo and remainder. Both of them can be used to compute the remainder of an integer division:

(remainder 23 5) => 3
(modulo 23 5)    => 3

The difference between modulo and remainder is the sign of their result. When applied to positive values, they evaluate to equal numbers. (Remainder a b) is defined as:

(- a (* (quotient a b) b))

From this formula follows that remainder always delivers a result that has the same sign as its first argument (a):

(remainder +23 +5) => 3
(remainder +23 -5) => 3
(remainder -23 +5) => -3
(remainder -23 -5) => -3

Modulo, on the other hand, makes use of the following formula to compute the division remainder:

(- a (* (floor (/ a b)) b))

The floor procedure takes an integer, rational, or floating point argument and reduces to the greatest integer that is not greater than that argument. Because floor may decrease negative quotients, modulo always delivers a result that has the same sign as its second argument (b):

(modulo +23 +5) => 3
(modulo +23 -5) => -2
(modulo -23 +5) => 2
(modulo -23 -5) => -3

Modulo can be implemented without using floor, too. The following method is based on the observation that floor only has an effect on the result, if the signs of the operands of modulo differ:

(floor (/ 23 5))   = (quotient 23 5)   = 4
(floor (/ -23 -5)) = (quotient -23 -5) = 4
(floor (/ 23 -5))  = (floor -4.6)      = -5
(floor (/ -23 5))  = (floor -4.6)      = -5

and the remainder is non-zero:

if  (remainder x y) => 0  then  (modulo x y) => 0

In the cases where floor causes this effect, it reduces the quotient by one:

(- a (* (- (quotient a b)
           1)
        b))

which can be re-written as follows:

  (- a (* (- (quotient a b)
             1)
          b))
= (+ (- a (* (quotient a b)
             b))
     b)
= (+ (remainder a b) b)

So all modulo has to do is to compute the remainder and then add b if the remainder is non-zero and the signs of its operands differ. Here is the code (the negative? predicate tests whether a number is negative):

(define (modulo a b)
  (let ((rem (remainder a b)))
    (cond ((zero? rem) 0)
          ((eq? (negative? a) (negative? b)) rem)
          (else (+ b rem)))))

Two interesting procedures which make use of remainder are gcd and lcm, which compute the greatest common divisor and least common multiple respectively. Like many other arithmetic procedures, they are variadic:

       (gcd 51) => 51
(gcd 289 34 51) => 17
       (lcm 17) => 17
 (lcm 16 17 68) => 272

There are many other numeric Scheme procedures to discover. A brief and incomplete summary of them is given here:

abs           compute the absolute value
even?         test for n mod 2 = 0
odd?          test for n mod 2 =/= 0
denominator   extract denominator of rational
numerator     extract numerator of rational
sqrt          extract square root
expt          exponentiate
complex?      test for type complex
integer?      test for type integer
rational?     test for type rational
real?         test for type real
ceiling       round towards 1
round         round towards closest integer
truncate      truncate real
sin           compute sine

Some of these procedures require the implementation of the full numeric tower. The full numeric tower encompasses the types integer, rational, floating point, and complex, including representations for inexact numbers.

These concepts are not explained here, because a discussion of the full numeric tower is beyond the scope of this book. You will probably have noticed, though, that there is a complex type, and this fact shall not pass unnoticed.

When you take the square root of a negative number in a Scheme environment implementing the full numeric tower, you will get a result of the type complex, as you would expect it in mathematics:

(sqrt 2) => 1.4142135623730951
(sqrt -2) => 0+1.4142135623730951i

Standard Scheme implementations are not required to include the full numeric tower, but most of them do.