10
\$\begingroup\$

We already have a challenge for computing the GCD of two Gaussian integers, but that challenge explicitly allows to choose any of the four possible values.

Your task now is to bring the Gaussian integer computed by the GCD in the following normal form:

  1. The result differs from the original number by a factor of 1,i,-1 or -i
  2. The result is zero, or the real part is positive
  3. The imaginary part is non-negative

Input: A Gaussian integer (complex number with integer real and imaginary parts)
Output: The normal form (see above) of that Gaussian integer

Examples:

0 -> 0
5 -> 5
2i -> 2
1+i -> 1+i
1-i -> 1+i
3-5i -> 5+3i
-3+5i -> 5+3i
3+5i -> 3+5i
-3-5i -> 3+5i

Rules

  • You can use pairs instead of complex numbers for input/output
  • If your language has a built-in for this operation consider adding a non built-in solution as well
  • This is the shortest solution wins
\$\endgroup\$
1
  • 5
    \$\begingroup\$ I suggest renaming this challenge to "Normalize a Gaussian integer". As stated it no longer has anything to do with GCDs. \$\endgroup\$ Commented Aug 30, 2023 at 0:20

13 Answers 13

10
\$\begingroup\$

J, 14 bytes

Takes input as a complex number.

(0,o.%2)&|&.*.

Attempt This Online!

Convert to polar coordinates, take the angle modulo \$\frac\pi2\$, convert back.

The first rule allows for 90˚ or \$\frac\pi2\$ rotations on the complex plane, the other two rules specify the result should be in the upper-right quadrant or on the non-negative part of the real axis.
This means the resulting complex number should have an angle in \$\left[0,\frac\pi2\right)\$ and the same magnitude as the input.


J, 12 bytes

Takes input as a pair of integers.

||.~1=2|@#.*

Attempt This Online!

Take the absolute value of both values and swap them if:

  • one is negative, the other positive, or
  • the first (real) part is zero.
\$\endgroup\$
5
\$\begingroup\$

Python, 46 bytes

f=lambda x,y:f(-y,x)if(x|y)*(y|x-1<0)else(x,y)

Attempt This Online!

  • -25 bytes thanks to Arnould and Bsoelch
  • -3 bytes thanks to Arnould
  • -1 byte thanks to The Thonnu
\$\endgroup\$
4
  • \$\begingroup\$ 68 bytes \$\endgroup\$
    – bsoelch
    Commented Aug 29, 2023 at 11:58
  • \$\begingroup\$ 55 bytes by doing it recursively \$\endgroup\$
    – Arnauld
    Commented Aug 29, 2023 at 12:22
  • \$\begingroup\$ 49 bytes \$\endgroup\$
    – Arnauld
    Commented Aug 29, 2023 at 12:57
  • \$\begingroup\$ 46 bytes \$\endgroup\$
    – The Thonnu
    Commented Aug 29, 2023 at 13:19
4
\$\begingroup\$

Jelly, 9 bytes

×ƬıÆiṠ$ÞṪ

A monadic Link that accepts the Gaussian integer as a complex number and yields a complex number.

Try it online!

How?

×ƬıÆiṠ$ÞṪ - Link: Gaussian integer, G
  ı       - imaginary unit
 Ƭ        - starting with G, collect up while distinct applying:
×         -   multiply by {imaginary unit}
       Þ  - sort by:
      $   -   last two links as a monad:
   Æi     -     convert to [real, imaginary] parts
     Ṡ    -     signs (-x:-1, 0:0, x:1)
        Ṫ - tail
\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 32 bytes

-3 bytes thanks to alephalpha

Expects (real, imaginary). Returns [real, imaginary].

f=(r,i)=>r<!!i|i<0?f(-i,r):[r,i]

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ r|i&&r<1 -> r<!!i \$\endgroup\$
    – alephalpha
    Commented Aug 30, 2023 at 14:23
3
\$\begingroup\$

Vyxal, 6 bytes

±BṅßǓȧ

Try it Online!

Port of jelly with conditional execute rather than repeating 0 or 1 times

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

Retina 0.8.2, 76 bytes

\bi
1i
^-?(\d+)i?$
$1
^-(\d+)([+-].*)
$1-$2
--
+
(.+)-\+?(.+)i
$2+$1i
\b1i
i

Try it online! Link includes test cases. Explanation:

\bi
1i

Change i, +i and -i to 1i, +1i and -1i.

^-?(\d+)i?$
$1

Change multiples of powers of i to their absolute value.

^-(\d+)([+-].*)
$1-$2

If the real part is negative then negate the whole value.

--
+

Fix up a double negation of the imaginary part.

(.+)-\+?(.+)i
$2+$1i

If the imaginary part is negative then multiply by i.

\b1i
i

Change +1i to +i. (It can't be i or -i at this point.)

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

Jelly, 6 bytes

Input and output as a pair of integers. Port of my second J answer.

ṠḄỊṙ@A

Try it online!

Ṡ        -- sign of each integer
 Ḅ       -- convert from binary
  Ị      -- insignificant / absolute value <= 1
   ṙ@    -- this number of times (0 or 1), rotate ...
     A   -- the absolute value of each integer
\$\endgroup\$
2
\$\begingroup\$

R, 37 bytes

\(x)complex(,,,Mod(x),Arg(x)%%(pi/2))

Attempt This Online!

Port of the first approach in J answer by ovs.

Inputs and outputs complex numbers.

\$\endgroup\$
1
\$\begingroup\$

PARI/GP, 35 bytes

f(x,y)=if(x<!!y||y<0,f(y,-x),[x,y])

Attempt This Online!

Takes input as real,imag and outputs [real,imag].

\$\endgroup\$
1
\$\begingroup\$

Nekomata, 7 bytes

±đZ≠nŘA

Attempt This Online!

A port of @ovs's Jelly answer.

Takes a pair of integers as input, and outputs a pair of integers.

±đZ≠nŘA
±           Sign
 đ          Split the pair into two integers
  Z         Check if the second integer is non-zero
   ≠        Check if the two integers are not equal
    n       Return 0 if the check fails, 1 if it passes
     Ř      Rotate the input that many times
      A     Absolute value
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 32 bytes

≔E²NθF⁴«⊞υθ≔E⮌θ⎇λκ±κθ»I⌈Φυ¬›⁰§ι¹

Try it online! Link is to verbose version of code. I/O is a pair of integers. Explanation:

≔E²Nθ

Input the Gaussian integer.

F⁴«⊞υθ≔E⮌θ⎇λκ±κθ»

Multiply it by the powers of i.

I⌈Φυ¬›⁰§ι¹

Filter out those values with negative imaginary parts and take the remaining value with the largest real part.

There are three cases:

  • If the Gaussian integer is zero, then all of the values will be zero, and so the output will be zero.
  • If the Gaussian integer is a non-zero multiple of a power of i, then only one of the values will have a positive real part, and this is the value we want.
  • If the Gaussian integer has neither real nor complex part zero, then there will be two values with positive real parts, but one will have a negative imaginary part which will have been filtered out, so we obtain the value with both parts positive.
\$\endgroup\$
1
\$\begingroup\$

ARM64 machine code, 28 bytes

 b40000a1
 aa0003e2
 cb0103e0
 aa0203e1
 b7ffffa1
 b7ffff80
 d65f03c0

Assembly source:

    .text
    .global make_positive
    .balign 4
make_positive:
    // If z is already real, jump directly to check if the real part is nonnegative
    cbz x1, check_real_part
    
multiply_again: 
    // multiply by i
    mov x2, x0
    neg x0, x1
    mov x1, x2

    // see if both parts nonnegative
    
    tbnz x1, #63, multiply_again
check_real_part:    
    tbnz x0, #63, multiply_again
    ret

This function takes the real and imaginary parts as 64-bit signed integers in x0 and x1 respectively, and returns the result in the same two registers. This is in keeping with usual ARM64 calling conventions for something like struct complex { int64_t re, im; }; passed by value.

The basic algorithm is:

do {
    z *= i;
} while (z.im < 0 || z.re < 0);

The only case for which this doesn't work is if the starting value of z is positive real. So if z is pure real (z.im == 0), we jump directly to the z.re < 0 test; if that branch is not taken then z is already nonnegative real and we are done.

Spending three instructions to multiply by i seems like a lot, but the issue is that we have to do it in place, and there's no "swap registers" instruction so we need a temporary third register.

Note that if either part of the input is -2^63 (LONG_MIN) then the function will enter an infinite loop. However this should be disallowed anyway since the normal form of such a number cannot be represented in signed 64-bit.

Branchless version, 36 bytes

As a bonus, I also tried writing a branchless version, but so far have only been able to get down to 36 bytes. The idea is to conditionally multiply by -1 and i in turn

        .text
        .global make_positive_branchless
        .balign 4
make_positive_branchless:
        // if real part is negative, multiply by -1                                                                                                                                           
        cmp x0, #0
        cneg x2, x0, lt
        cneg x3, x1, lt
        // if real part was zero and imaginary part now positive, we must negate again                                                                                                        
        // so that multiplication by i gives a positive real result                                                                                                                                    
        ccmp x3, #0, #4, eq // nZcv, for which GT is false                                                                                                                                    
        cneg x3, x3, gt
        // now if imaginary part is negative, multiply by i                                                                                                                                   
        cmp x3, #0
        csneg x0, x2, x3, ge
        csel x1, x3, x2, ge
        ret
\$\endgroup\$
0
\$\begingroup\$

Scala, 67 bytes

Fixed underlying error thanks to the comment of @bsoelch


Port of @mousetail's Python answer in Scala.


def f(x:Int,y:Int):(Int,Int)=if((x|y)!=0&(y|x-1)<0)f(-y,x)else(x,y)

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ You seem to have made a mistake while porting the answer, the solution gives the wrong result for some of the test-cases. This seems to fix it \$\endgroup\$
    – bsoelch
    Commented Sep 2, 2023 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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