25
\$\begingroup\$

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.

enter image description here

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 rules apply. Shortest code in bytes wins.

\$\endgroup\$
7
  • 5
    \$\begingroup\$ Do you happen to know if this innovation had made any appearances in pure math, or is it just a useful programming construct? \$\endgroup\$
    – Jonah
    May 17 at 3:02
  • \$\begingroup\$ Wolfram alpha has a very simple definition wolframalpha.com/input/?i=floor%283.3%2B2.3i%29 . Does that fit the criteria? \$\endgroup\$
    – Anush
    May 17 at 3:14
  • 1
    \$\begingroup\$ @Jonah AFAIK it didn't make into mainstream mathematics. The only actual usefulness I'm aware of is that the Euclidean algorithm always terminates. \$\endgroup\$
    – Bubbler
    May 17 at 3:15
  • 1
    \$\begingroup\$ @Anush Assuming it just floors the two components, it is the prime example that does NOT solve the challenge, since it violates Fractionality (floor of 3.9+2.9i is 3+2i; the difference is 0.9+0.9i; magnitude of 0.9+0.9i is greater than one which is not allowed). \$\endgroup\$
    – Bubbler
    May 17 at 3:28
  • \$\begingroup\$ @Bubbler Thanks \$\endgroup\$
    – Anush
    May 17 at 4:36

10 Answers 10

10
\$\begingroup\$

BQN, 14 bytesSBCS

⌊+·(⍋×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.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Welcome to Code Golf, and nice first answer! \$\endgroup\$
    – Bubbler
    May 17 at 5:43
8
\$\begingroup\$

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.
\$\endgroup\$
2
  • \$\begingroup\$ would taking a two element array as input be shorter here? \$\endgroup\$
    – Razetime
    May 17 at 4:38
  • \$\begingroup\$ yes! thanks, somehow i was thinking i had to take a complex number.... \$\endgroup\$
    – Jonah
    May 17 at 4:42
6
\$\begingroup\$

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
\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Is 1>Math.abs(x)+Math.abs(y) Math.abs(x)>=Math.abs(y) required to make this function work? \$\endgroup\$
    – tsh
    May 17 at 9:34
  • \$\begingroup\$ @tsh doesn't seem like it, because f(.6,.3) seems to work. So does f(.6, .8). \$\endgroup\$
    – user100690
    May 17 at 9:35
  • \$\begingroup\$ Also, your floor of -0.5 is 0 instead of -1, while floor of 0.5 is 0; but Rule 6 Integer Translation says floor(-0.5) = floor(0.5)-1. \$\endgroup\$
    – tsh
    May 17 at 9:41
6
\$\begingroup\$

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:

enter image description here

* I think.

\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ If I understand correctly, your Floor(-0.9-0.1i)=-i but |(-0.9-0.1i)-(-i)|=0.9*sqrt(2)>1 \$\endgroup\$
    – tsh
    May 17 at 9:48
  • \$\begingroup\$ @tsh Thanks for finding that. Fixed for -1 bytes lol \$\endgroup\$
    – hyper-neutrino
    May 17 at 13:59
  • \$\begingroup\$ Explanation should read "grade up; [1, 2] if frac(x) <**=** frac(y) and [2, 1] otherwise" (and does the code need a fix?). \$\endgroup\$ May 17 at 18:15
  • \$\begingroup\$ @JonathanAllan thanks for spotting that. I don't think that requires a fix, though I did end up finding something else that needed to be fixed \$\endgroup\$
    – hyper-neutrino
    May 17 at 18:26
  • 1
    \$\begingroup\$ 12 bytes \$\endgroup\$ Jul 4 at 2:04
3
\$\begingroup\$

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

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 58 bytes using a-a%1 == a//1 and simplifying the conditional. \$\endgroup\$
    – ovs
    May 17 at 10:03
3
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Excellent! It was clear that my proposal could be golfed further. Well done. \$\endgroup\$ May 18 at 12:48
2
\$\begingroup\$

Charcoal, 26 23 bytes

NθNηIE²⌊⊘⁺⊕⁺θη×⌊⁻θη∨±ι¹

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 \$.

\$\endgroup\$
0
2
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.