Complex floor

Complex Floor is a domain extension for the built-in function Floor to accept complex numbers. It was originally designed by Eugene McDonnell in order to provide domain extensions to ceiling, residue, GCD, and LCM, which all depend on the definition of Floor. This extension is currently implemented in Dyalog APL, J, and NARS2000.

Terminology

In this article, an integer refers to a Gaussian integer, a complex number whose real and imaginary parts are integers.

In code fragments, re and im refer to functions that return the real and imaginary part of the given complex number respectively. They are available as a part of Circular, namely 9○ and 11○.

Concept

McDonnell focused on a few specific uses of Floor: calculating the quotient and remainder between two numbers, and calculating the GCD via the Euclidean algorithm. In order to achieve this, he proposed seven requirements:

1. Existence. Every number has a floor.
2. Uniqueness. Every number has only one floor.
3. Fractionality. The magnitude of the difference of a number and its floor shall be less than one. This property must be satisfied to guarantee that remainders are less in magnitude than divisors. It may be called the fundamental property of the floor function.
4. Integrity. The floor of a number is an integer.
5. Convexity. If g is the floor of the numbers z and w, then it is also the floor of all numbers on the line segment between z and w.
6. Integer Translation. For c a complex integer, (c+⌊z) = ⌊(c+z).
7. Compatability. The complex floor function is compatible with the real floor function. Furthermore, its action on purely imaginary numbers is similar to the action of the real floor function on real numbers. In particular, (re⌊z)≤re⌈z and (im⌊z)≤im⌈z.

Then he proposed a shape on the complex plane that satisfies all seven requirements: a rectangle of width √2 and height √÷2, rotated 45 degrees clockwise so that the midpoint of the bottom side is placed on an integer b, and the top two corners are placed on b+0j1 and b+1 respectively. The following is the APL model by McDonnell, rewritten using dfns:

Floor←{
  r←re ⍵
  i←im ⍵
  b←(⌊r)+0j1×⌊i
  x←1|r
  y←1|i
  1>x+y: b
  x≥y: b+1
  b+0j1
}

Application to other primitives

Ceiling ⌈x was extended via the property (⌈x) = -⌊-x.

Residue x|y was extended by the definition (w|z) = z-w×⌊z÷w+w=0. The property of Fractionality ensures that the residue is always smaller in magnitude than the divisor.

GCD x∨y was extended by using the Euclidean algorithm, which is guaranteed to terminate for any pair of complex numbers, again due to Fractionality. The following is the APL model for complex GCD, again using dfns:

GCD←{
  0=⍺|⍵:⍺
  (⍺|⍵)∇⍺
}

LCM x∧y was extended by using the property (x∧y) = x×y÷x∨y.