Complex Floor

Eugene McDonnell

IBM Scientific Center
Philadelphia, PA 19063, USA

Abstract

A construction is given for extending the floor function from the real to the complex domain. The use of the extended function is exemplified by discussions of the complex ceiling and residue functions, the classification of systems of least residues, the division theorem and the Euclidean algorithm for complex numbers.
 

0. Introduction

Present implementations of APL are limited to the real numbers, and hence reject as “domain errors” those expressions on real variables which require a complex result. Definitions for the power, product, quotient, sum, difference, and circular functions on complex numbers are in common mathematical use, and could readily be implemented. The functions basic to number theory, however, have not be uniformly extended to complex numbers.

When one investigates the mathematical literature for results in the complex domain on such notions as residue and greatest common divisor, one finds that they are treated by means which are different from those used to treat them in the rational integer case. The work reported on here extends the APL number-theoretic primitives to the complex domain, and shows their application in the study of complete systems of residues, the division theorem, and the Euclidean algorithm for complex integers.
 

1. The Floor Function

The floor function is sometimes called the greatest integer, or integral part, or entier function. It is defined as the function which maps an arbitrary real number x onto the greatest integer not exceeding x , and is denoted by ⌊y .

Although it is used throughout mathematics wherever a number must be approximated by an integer, the floor function obtains its importance primarily from its use in the division algorithm. A quotient of a dividend a with respect to a divisor b is defined as ⌊a÷b . The residue of a with respect to a modulus b , is given by a-b×⌊a÷b+b=0 . The quotient function and residue function are of particular importance in the algorithm for continued fraction expansions, and the residue function is essential to the Euclidean algorithm for greatest common divisor.
 

2. Orthography for Complex Scalars

It has been customary to represent complex numbers in the form a+bi , explicitly stating two separate coefficients for displacement along the real and imaginary axis. Such a notation would seem to suggest that a complex number is in some sense a two-element vector, and would conflict with the general and consistent treatment of arrays in APL. We therefore adopt here the notation that a complex scalar be written in the form aib , in which the digits preceding the letter i are the real component and those following are the imaginary component. A vector made up of three complex scalars might be 3i2 1.4i¯8.6 0i1 . The fact that two separate numerical representations appear on either side of the letter i does not imply that the value so represented is not scalar, any more than it does in the notation such as 3e¯6 .
 

3. Extension of the Floor Function to the Complex Domain

Since the ceiling and residue functions may be defined in terms of the floor function, the central task is to define the floor function on complex arguments.

The definition will be accomplished in the following steps: First, a set of conditions which we wish the floor function to satisfy will be given. Next, a shape will be described which satisfies the conditions geometrically. This shape will be reinterpreted into an algorithmic definition for the complex floor function. With this definition in hand, we shall be able to define the ceiling and residue functions. Following this, several applications will be shown for the complex valued floor function, namely, the classification of systems of least complex residues, a proof of the division theorem for complex arguments, and the use of the residue function in the Euclidean algorithm to find the greatest common divisor of complex arguments.

The requirements which we desire a complex floor function to satisfy are:

A shape which suits these requirements is a rectangle of slides √2 by √(1÷2) , oriented so that the center of one long side is coincident with a lattice point b , and with the ends of the opposite long side coincident with the lattice points above and to the right of b . Figure 1 shows a system of such rectangles. The complex integer b is the midpoint of the bottom line of one of the rectangles. All of the points within the rectangle, and on the two indicated boundaries, have b as floor.

Figure 1. A system of floor areas

The algorithm for the determination of g , the floor of a complex number z , may be explained informally as follows:

An algorithm in APL is as follows:

     ∇ g←floor z
[1]    r←re z
[2]    i←im z
[3]    b←(⌊r)+0i1×⌊i
[4]    x←1|r
[5]    y←1|i
[6]    g←(b if 1>x+y), ((b+1) if (1≤x+y) and x≥y),
          ((b+0i1) if (1≤x+y) and x<y)
     ∇

In the algorithm, r and i are, respectively, the real and imaginary parts of z . b is the complex integer, or lattice point, at the lower left hand corner of the unit square containing z . x and y are, respectively, the fractional parts of r and i . The functions denoted by ⌊ and | are real-valued floor and residue functions. The functions re , im , and , and if have the obvious definitions.

Figure 2
Dissection of the unit square

The propositions used in statement 6 of the algorithm are given a geometric interpretation in Figure 2. The proposition 1>x+y is true in “a” and “d”; the proposition (1≤x+y) and x≥y is true in “c”; and the proposition (1≤x+y) and x<y is true in“b”. The three propositions are mutually exclusive and exhaustive with regard to the area of the unit square. The edges of the different sections of the unit square are darkened to show which lattice points each segment of the edges is associated with. Points “a” and “d” have b are floor, in “b” have b+0i1 as floor, and in “c” have b+1 as floor. See Table I.

Table I. Examples of complex floor computations
 

4. The Complex Ceiling Function

For real numbers, ceiling is the dual of floor with respect to negation. The same duality may be used to define the complex ceiling function: ceiling z ←→ - (floor -z) . Table II gives some examples of the complex ceiling function. Figure 3 shows the complex plane partitioned by ceiling areas. Compare with Figure 1.

Table II: Examples of the complex ceiling function
 

Figure 3. A system of ceiling areas
 

5. The Residue Function

The definition of the residue function for real arguments can be used for complex arguments, given the definition of the complex floor function: that is, w residue z ←→ z-w×floor z÷w+w=0 . The requirement imposed on the floor function, that the magnitude of the result q-floor q be less than one, insures that the magnitude of the result of the residue function is less than the magnitude of the modulus, or left argument. In terms of quotient-remainder arithmetic, this says that the remainder is less than the divisor in magnitude.
 

6. Complete Systems of Residues

Let us agree that a proper representative of a residue class has a magnitude less than the magnitude of the modulus. This does not define a unique proper representative. For example, with respect to the modulus 5 , both 3 and ¯2 are in the same residue class, and both have magnitudes less than 5 . Gauss (1801) used the notion of least residues to describe all those integers, positive, negative, and zero, which are less in magnitude than the modulus. On the real line there are ¯1+2×n least residues, but only n residue classes; in the complex plane, there are approximately π(|n*2) least residues, but only norm n residue classes (Hardy and Wright (1960), p. 220). Gauss classified the residues by the terms least positive residues, least negative residues, and least magnitude residues. The first two correspond to systems of residues found using the floor and ceiling functions, respectively, in the definition of the residue function. In the complex plane, the same classification scheme may be used. To illustrate this, Figure 4 gives the result of using the floor and ceiling functions to determine a complete system of residues with respect to the modulus ¯3i4 . In each case the number of elements is equal to norm ¯3i4 , or 25 .

Figure 4. Complete residue system for the modulus ¯3i4
 

7. The Division Theorem

The division theorem proves that quotients can be found, with remainders having certain properties. The proofs commonly given for the real and the complex cases (see Pollard (1950), for example) differ in two important respects. The statement for the real case is that the remainder found will be less than the divisor, and will be unique. To be able to say this, it is necessary to restrict divisors to be strictly positive. This is, of course, a simplifying restriction, but one which leaves the question hanging as to what the situation is with regard to arbitrary non-zero real numbers.

The second difference is that the floor function is used in the proof for the real number case, and not in the complex number case. Furthermore, the proof for the complex case proves more than necessary, namely that the remainder is less than the divisor divided by √2 (see Hardy and Wright (1960), for example).

The proof given here unifies the real and the complex cases, by removing the restriction to positive divisors and the distinctness of the remainder in the real case, and by using the floor function (as extended in this paper) in both cases. The theorem proves no more than is necessary.

Theorem: If z and w are arbitrary numbers, with w≠0 , then there exists an integer q , and an r such that

Proof: Let

To show that (|r) < |w , observe that

Since 1 > |((z÷w) - floor (z÷w)) , then

8. The Euclidean Algorithm

The version of the Euclidean algorithm usually given for complex numbers differs from that given for real numbers in one important way (see Hardy and Wright (1960), chapter 12, for a representative treatment of the two versions). In handling the real number case, the floor residue is employed. In handling the complex number case, it is not. A minor difference in the two algorithms is that the real case is usually restricted to the positive reals, and so the question of negative remainders does not arise, and the series of remainders found is strictly decreasing. In the complex case, no such restriction on the values is possible, and thus it is shown only that the norm of the series of remainders is strictly decreasing.

With the definition of complex floor provided in this paper, it is clear that a single algorithm can handle both the real and the complex cases. In fact, the situation for the Euclidean algorithm is much like that for the division algorithm, on which the Euclidean algorithm depends. We give below an APL statement of the Euclidean algorithm, suitable for complex (as well as real) arguments.

To find x , the greatest common divisor of w and y :

    ∇ x←w gcd y
[1]   x←w
[2]   w←w|z
[3]   z←x
[4]   →1 if w≠0
    ∇

9. Conclusion

This paper has extended the definitions of the floor, ceiling, and residue functions to the complex domain. The representation function is defined in terms of residue, and so its definition is also extended. These extensions have made a continuity of treatment possible for such subjects as residue classes, the division algorithm, and the Euclidean algorithm, from the real to the complex domain.

The construction provided for the floor of complex numbers may be extended to quaternions and to Cayley numbers, the four- and eight-element hypercomplex numbers analogous to the two-element complex numbers.
 

Acknowledgments

This work was begun as a result of a question posed by L.M. Breed, “How can the APL residue function be extended to complex numbers?”, and has benefitted from discussions with colleagues in the IBM Scientific Centers at Philadelphia and Palo Alto. Special thanks are owned to R.I. Frank, for help with the mathematics, to a referee for comments which led to an extensive revision of the paper, and to P.C. Berry and K.E. Iverson, for their careful reading of early drafts of this paper.
 

References