Floor of complex number

Question

Background

Complex floor is a domain extension of the mathematical floor function for complex numbers. This is used in some APL languages to implement floor ⌊, ceiling ⌈, residue |, GCD ∨, and LCM ∧ on complex numbers.

For the rest of this challenge, an integer refers to a Gaussian integer, i.e. a complex number whose real and imaginary parts are integers.

Eugene McDonnell defined seven requirements of a complex floor function (copied from the wiki page, with APL code fragments translated into plain math notation):

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+ \lfloor z \rfloor = \lfloor c+z \rfloor\$.
7. Compatibility. 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, \$\operatorname{re}(\lfloor z \rfloor) ≤ \operatorname{re}(\lceil z \rceil)\$ and \$\operatorname{im}(\lfloor z \rfloor) ≤ \operatorname{im}(\lceil z \rceil)\$. (Ceiling for complex numbers is defined as \$\lceil z \rceil = -\lfloor -z \rfloor \$.)

One shape that satisfies these conditions is a rectangle \$\sqrt{1\over2}\$ units high and \$\sqrt2\$ units wide, rotated 45 degrees, as in the following image.

One interesting consequence of fractionality is that the magnitude of the residue is always smaller than that of the divisor, and the Euclidean algorithm always terminates on arbitrary complex number inputs.

Task

Define your own complex floor that satisfies the requirements listed above, and implement it. It is OK if you simply use McDonnell's function. If you use a different function, please include an explanation of how it satisfies the requirements.

Please note that simply flooring the two components is NOT a valid answer since it violates Fractionality: when \$z = 3.9 + 2.9i\$,

$$ \lfloor z \rfloor = 3 + 2i \\ z-\lfloor z \rfloor = 0.9 + 0.9i \\ |z-\lfloor z \rfloor| = |0.9 + 0.9i| = 0.9 \sqrt2 > 1 $$

You may represent a complex number as a built-in complex number or a pair of real numbers. You don't need to care too much about boundary conditions, since floating-point imprecision will impact its correctness anyway.

It is known to be implemented in Dyalog APL, J, and NARS2000. You are not allowed to use floor/ceiling/residue/GCD/LCM functions with non-real complex arguments for these languages.

Standard code-golf rules apply. Shortest code in bytes wins.

Answer 1

BQN, 14 bytes^SBCS

⌊+·(⍋×1<+´)1⊸|

Try it here.

⌊+·(⍋×1<+´)1⊸| # Tacit function which takes input as an array of 2 numbers
⌊              # floor
 +             # plus
   (      )    # the parenthesized train: 
    ⍋          #   grade
     ×         #   times
      1<+´     #   comparison 1 less than the sum
  ·            #   applied monadically to
           1⊸| # the fractional part

Replicating the image in the challenge description.

Answer 2

J, ^{32 31} 26 bytes

j.&<.+((1<:+)*0j1^<)&(1|])

Try it online!

^{-5 thanks to Razetime for pointing out I could take real and imag parts as left and right args.}

Obligatory J answer.

For reference, per the link in the OP, Eugene McDonnell's algorithm is:

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

1. Let b be the point at the lower left corner of the unit square containing z . Let x and y be the fractional parts of the real and imaginary parts of z .
2. Then:

• Let g = b if 1 > (x + y) ,
• Let g = (b + 1) if (1 ≤ x + y) and x ≥ y ,
• Let g = (b + 0i1) if (1 ≤ x + y) and x < y .

We take the real and imaginary parts as left and right args.

We note that the answer is:

b + (0 or 1 or i)

depending on the case.

• j.&<.+ Floors both parts and converts back to complex j.&<./, then adds everything to the right +. This gives us the b + part.
• (...)&(1|]) Get fractional parts of real/imag pieces, and feed those as left and right args to everything in parens. This gives us x and y.
• (1<:+) Is x + y greater than or equal to 1? Returns 0 or 1. Multiply that by...
• 0j1^< \$i\$ raised to "is x < y?" -- gives us \$i\$ if true, 1 otherwise.

Answer 3

MMIX, 56 bytes (14 instrs)

00000000: e0043ff0 17020300 17030301 06000002  ṭ¥?ṅ磤¡ç¤¤¢©¡¡£
00000010: 06010103 04ff0001 01ffff04 6104ff00  ©¢¢¤¥”¡¢¢””¥a¥”¡
00000020: 01ff0001 7005ff04 26040405 04000305  ¢”¡¢p¦”¥&¥¥¦¥¡¤¦
00000030: 04010204 f8020000                    ¥¢£¥ẏ£¡¡

cfloor  SETH $4,#3FF0           // readj = 1.
        FINT $2,ROUND_DOWN,$0   // xf = floor(x)
        FINT $3,ROUND_DOWN,$1   // yf = floor(y)
        FSUB $0,$0,$2           // x -.= xf
        FSUB $1,$1,$3           // y -.= yf
        FADD $255,$0,$1
        FCMP $255,$255,$4
        CSN  $4,$255,0          // if(x +. y <. 1) readj = 0
        FCMP $255,$0,$1
        ZSN  $5,$255,$4         // imadj = x <. y? readj : 0
        SUBU $4,$4,$5           // readj -= imadj
        FADD $0,$3,$5
        FADD $1,$2,$4           // add in adjustments and swap (MMIX shuffle)
        POP  2,0

Answer 4

R, 55 bytes

function(x,y=x%%1)(x+(sum(y)>1)*c(z<-diff(y)<0,!z))%/%1

Try it online!

Straightforward implementation of McDonnell's function.

---

R, 71 bytes

function(x,y=x%%1,w=c(z<-diff(y)<0,!z))(x+(sum(y/(1+2^.5*!w))>1)*w)%/%1

Try it online!

16 bytes longer, but minimizes the amount of rounding-up required*, while still satsifying the convexity requirement, for all complex numbers.

McDonnell's function unsatisfyingly rounds-up either the real or imaginary part of a complex number whenever their fractional parts sum to greater than 1, even though the fractionality requirement (condition #3) would still be satisfied by rounding down until r^2+i^2>1.
The convexity requirement (condition #5) prevents us from rounding down for all r^2+i^2<=1, but we can minimize the amount of rounding-up needed by using a 'quarter-octagon' shape, instead of a triangle, for fractional r and i between 0 and 1.
The rounding 'domains' are shown in different colours here:

* I think.

Answer 5

JavaScript (Node.js), 57 74 bytes

(a,b,x=a%1,y=b%1,s=Math.abs)=>1>x+y?[a-s(x),b-s(y)]:[a-x+(x>=y),b-y+(x<y)]

Try it online!

Explanation

Uses a similar algorithm as @Jonah's answer.

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

Let b be the point at the lower left corner of the unit square containing z . Let x and y be the fractional parts of the real and imaginary parts of z . Then: Let g = b if 1 > (x + y) , Let g = (b + 1) if (1 ≤ x + y) and x ≥ y , Let g = (b + 0i1) if (1 ≤ x + y) and x < y .

Needed to add 17 bytes in order to sort out a bug.

Answer 6

Jelly, 12 bytes

Ḟɓ_Ụ’×S>1ƊƲ+

Try it online!

-3 bytes by using the grade up idea from frasiyav's BQN answer. Go upvote that too.
-1 byte by fixing a bug pointed out by tsh
-1 byte thanks to caird coinheringaahing

This is just a golf of Eugene McDonnell's algorithm. Using the same concept for golfing the 3-way conditional as Jonah's J answer.

Answer 7

Python 3.8 (pre-release), 58 bytes

lambda a,b:[a//1+(w:=a%1>=b%1)*(q:=1<=a%1+b%1),b//1+(q>w)]

Try it online!

thanks to @ovs for -12

Answer 8

Ruby, 55 47 bytes

->a,b{(a-a%=1)+1i*(b-b%=1)+(a+b<1?0:a>b ?1:1i)}

Try it online!

Thanks Eric Duminil for the idea of using 2 arguments.

Answer 9

Charcoal, 26 23 bytes

ＮθＮηＩＥ²⌊⊘⁺⊕⁺θη×⌊⁻θη∨±ι¹

Try it online! Explanation: Calculates \$ \lfloor a + bi \rfloor \$ using the following formula which is the complex conjugate of the rectangular tiling suggested in the question, and therefore trivially still satisfies all the requirements:

$$ \lfloor a + bi \rfloor = \left \lfloor \frac { 1 + a + b + \lfloor a - b \rfloor } 2 \right \rfloor + \left \lfloor \frac { 1 + a + b - \lfloor a - b \rfloor } 2 \right \rfloor i $$

In particular when \$ b = 0 \$, \$ \lfloor a + bi \rfloor = \left \lfloor \frac { 1 + a - \lfloor a \rfloor + 2 \lfloor a \rfloor } 2 \right \rfloor + \left \lfloor \frac { 1 + a - \lfloor a \rfloor } 2 \right \rfloor i = \lfloor a \rfloor \$ and when \$ a = 0 \$, \$ \lfloor a + bi \rfloor = \lceil b \rceil i \$.

Answer 10

Excel, 61 bytes

=LET(a,INT(A1:B1),a+(SUM(A1:B1-a)>=1)*({1,0}+(A1<B1)*{-1,1}))

Uses McDonnell's definition. Real coefficient in A1; imaginary in B1. Output is an array of real and imaginary coefficients.

Without LET, also 61 bytes

=INT(A1:B1)+(SUM(A1:B1-INT(A1:B1))>=1)*({1,0}+(A1<B1)*{-1,1})

Alternate, 35 bytes

=INT((1+A3+B3+INT(A3-B3)*{1,-1})/2)

This is a port of Neil's answer