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, <syntaxhighlight lang=apl inline>re</source> and <syntaxhighlight lang=apl inline>im</source> 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 <syntaxhighlight lang=apl inline>9○</source> and <syntaxhighlight lang=apl inline>11○</source>.

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 <syntaxhighlight lang=apl inline>g</source> is the floor of the numbers <syntaxhighlight lang=apl inline>z</source> and <syntaxhighlight lang=apl inline>w</source>, then it is also the floor of all numbers on the line segment between <syntaxhighlight lang=apl inline>z</source> and <syntaxhighlight lang=apl inline>w</source>.
6. Integer Translation. For <syntaxhighlight lang=apl inline>c</source> a complex integer, <syntaxhighlight lang=apl inline>(c+⌊z) = ⌊(c+z)</source>.
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, <syntaxhighlight lang=apl inline>(re⌊z)≤re⌈z</source> and <syntaxhighlight lang=apl inline>(im⌊z)≤im⌈z</source>.

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

<syntaxhighlight lang=apl> 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

} </source>

Application to other primitives

Ceiling <syntaxhighlight lang=apl inline>⌈x</source> was extended via the property <syntaxhighlight lang=apl inline>(⌈x) = -⌊-x</source>.

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

GCD <syntaxhighlight lang=apl inline>x∨y</source> 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:

<syntaxhighlight lang=apl> GCD←{

 0=⍺|⍵:⍺
 (⍺|⍵)∇⍺

} </source>

LCM <syntaxhighlight lang=apl inline>x∧y</source> was extended by using the property <syntaxhighlight lang=apl inline>(x∧y) = x×y÷x∨y</source>.