Euclid's algorithm with complex numbers
Statement
Goal
This puzzle assumes that you have solved:None of the math is explained nor needed. For those interested the references are at the bottom.
You will have to implement an analog of the euclidian division for Gaussian integers (complex numbers of the form x + iy with x and y integers). The pseudocode:
You are given two Gaussian integers a and b:
1: Compute a/b = x + iy.
2: Find the closest integer cx to x and cy to y. *
3: The quotient q is then cx + icy.
4: The rest r is just a - q * b.
You can now compute the GCD of a and b. Print the steps in the suitable format. **
* If there are two possible choices pick the highest one. That is, if x =
** This puzzle follows the Python conventions for printing complex numbers. The tests are more telling than a detailed explanation.
Reference: https://www.cut-the-knot.org/arithmetic/int_domain4.shtml
Input
Line 1: A space separated string containing two integers, the first representing the real part xa and the second the imaginary part ya of a Gaussian integer a.
Line 2: A space separated string containing two integers, the first representing the real part xb and the second the imaginary part yb of a Gaussian integer b.
Line 2: A space separated string containing two integers, the first representing the real part xb and the second the imaginary part yb of a Gaussian integer b.
Output
The steps of the GCD computation of a and b in the suitable format. This puzzle follows the Python conventions for printing complex numbers.
Constraints
xa, ya, xb and yb are all between -10000 and 10000 included.
Example
Input
2 0 1 -1
Output
(2+0j) = (1-1j) * (1+1j) + 0j GCD((2+0j), (1-1j)) = (1-1j)
Tags
Recursion, Mathematics, Complex Numbers
Difficulty
Easy
Test cases
1. 2 is not prime Test
Input
2 0
1 -1
Output
(2+0j) = (1-1j) * (1+1j) + 0j
GCD((2+0j), (1-1j)) = (1-1j)
1. Nor 5 Validator
Input
5 0
1 -2
Output
(5+0j) = (1-2j) * (1+2j) + 0j
GCD((5+0j), (1-2j)) = (1-2j)
2. Random Test
Input
-38 -26
-43 -7
Output
(-38-26j) = (-43-7j) * (1+0j) + (5-19j)
(-43-7j) = (5-19j) * -2j + (-5+3j)
(5-19j) = (-5+3j) * (-2+2j) + (1-3j)
(-5+3j) = (1-3j) * (-1-1j) + (-1+1j)
(1-3j) = (-1+1j) * (-2+1j) + 0j
GCD((-38-26j), (-43-7j)) = (-1+1j)
2. Random val Validator
Input
43 11
-32 26
Output
(43+11j) = (-32+26j) * (-1-1j) + (-15+5j)
(-32+26j) = (-15+5j) * (2-1j) + (-7+1j)
(-15+5j) = (-7+1j) * (2+0j) + (-1+3j)
(-7+1j) = (-1+3j) * (1+2j) + 0j
GCD((43+11j), (-32+26j)) = (-1+3j)
3. Don't sort Test
Input
-6 27
-37 25
Output
(-6+27j) = (-37+25j) * 0j + (-6+27j)
(-37+25j) = (-6+27j) * (1+1j) + (-4+4j)
(-6+27j) = (-4+4j) * (4-3j) + (-2-1j)
(-4+4j) = (-2-1j) * (1-2j) + 1j
(-2-1j) = 1j * (-1+2j) + 0j
GCD((-6+27j), (-37+25j)) = 1j
3. Don't sort val Validator
Input
8 3
36 -23
Output
(8+3j) = (36-23j) * 0j + (8+3j)
(36-23j) = (8+3j) * (3-4j) + 0j
GCD((8+3j), (36-23j)) = (8+3j)
4. Rounding Test
Input
28 40
-18 -24
Output
(28+40j) = (-18-24j) * (-2+0j) + (-8-8j)
(-18-24j) = (-8-8j) * (3+0j) + (6+0j)
(-8-8j) = (6+0j) * (-1-1j) + (-2-2j)
(6+0j) = (-2-2j) * (-1+2j) + 2j
(-2-2j) = 2j * (-1+1j) + 0j
GCD((28+40j), (-18-24j)) = 2j
4. Rounding + Don't sort val Validator
Input
-10 10
-46 25
Output
(-10+10j) = (-46+25j) * 0j + (-10+10j)
(-46+25j) = (-10+10j) * (4+1j) + (4-5j)
(-10+10j) = (4-5j) * (-2+0j) + (-2+0j)
(4-5j) = (-2+0j) * (-2+3j) + 1j
(-2+0j) = 1j * 2j + 0j
GCD((-10+10j), (-46+25j)) = 1j
5. Big Test
Input
-13 -39
-5 35
Output
(-13-39j) = (-5+35j) * (-1+1j) + (17+1j)
(-5+35j) = (17+1j) * 2j + (-3+1j)
(17+1j) = (-3+1j) * (-5-2j) + 0j
GCD((-13-39j), (-5+35j)) = (-3+1j)
5. Big val Validator
Input
32 733
-351 -455
Output
(32+733j) = (-351-455j) * (-1-1j) + (136-73j)
(-351-455j) = (136-73j) * (-1-4j) + (77+16j)
(136-73j) = (77+16j) * (2-1j) + (-34-28j)
(77+16j) = (-34-28j) * (-2+1j) + (-19-6j)
(-34-28j) = (-19-6j) * (2+1j) + (-2+3j)
(-19-6j) = (-2+3j) * (2+5j) + -2j
(-2+3j) = -2j * (-1-1j) + 1j
-2j = 1j * (-2+0j) + 0j
GCD((32+733j), (-351-455j)) = 1j
6. Bigger Test
Input
-5612 -2269
-250 940
Output
(-5612-2269j) = (-250+940j) * (-1+6j) + (-222+171j)
(-250+940j) = (-222+171j) * (3-2j) + (74-17j)
(-222+171j) = (74-17j) * (-3+2j) + (-34-28j)
(74-17j) = (-34-28j) * (-1+1j) + (12-11j)
(-34-28j) = (12-11j) * -3j + (-1+8j)
(12-11j) = (-1+8j) * (-2-1j) + (2+4j)
(-1+8j) = (2+4j) * (2+1j) + (-1-2j)
(2+4j) = (-1-2j) * (-2+0j) + 0j
GCD((-5612-2269j), (-250+940j)) = (-1-2j)
6. Bigger val Validator
Input
-250 940
-222 171
Output
(-250+940j) = (-222+171j) * (3-2j) + (74-17j)
(-222+171j) = (74-17j) * (-3+2j) + (-34-28j)
(74-17j) = (-34-28j) * (-1+1j) + (12-11j)
(-34-28j) = (12-11j) * -3j + (-1+8j)
(12-11j) = (-1+8j) * (-2-1j) + (2+4j)
(-1+8j) = (2+4j) * (2+1j) + (-1-2j)
(2+4j) = (-1-2j) * (-2+0j) + 0j
GCD((-250+940j), (-222+171j)) = (-1-2j)
7. Care even rounding Test
Input
19 8
-1 -7
Output
(19+8j) = (-1-7j) * (-1+3j) + (-3+4j)
(-1-7j) = (-3+4j) * (-1+1j) + 0j
GCD((19+8j), (-1-7j)) = (-3+4j)
7. Care even rounding val Validator
Input
9436 1127
-1395 935
Output
(9436+1127j) = (-1395+935j) * (-4-4j) + (116-713j)
(-1395+935j) = (116-713j) * (-2-2j) + (263-259j)
(116-713j) = (263-259j) * (2-1j) + (-151+68j)
(263-259j) = (-151+68j) * (-2+1j) + (29+28j)
(-151+68j) = (29+28j) * (-2+4j) + (19+8j)
(29+28j) = (19+8j) * (2+1j) + (-1-7j)
(19+8j) = (-1-7j) * (-1+3j) + (-3+4j)
(-1-7j) = (-3+4j) * (-1+1j) + 0j
GCD((9436+1127j), (-1395+935j)) = (-3+4j)
Solution language
Solution
Stub generator input