Decomposing an integer as sum of two squares

Decomposing an integer as sum of two squares

(I had not planned to write this EWD, but, after I had given this problem as homework, it turned out that the majority of my students had problems with it. My personal difficulty is, of course, that I now have to forget all the old-fashioned ways in which I have solved this problem in distant pasts.)

It is requested to print for $N \geq 0$ all natural solutions of

$u,v : \left( {{u}^{2} + {v}^{2} = N \land u \leq v}\right)$

The solutions have to be printed in some order. Since we are looking for zeros of $u^2 + v^2 - N$ , an increasing function of both $u$ and $v$ , the order of increasing $u$ is at the same time the order of decreasing $v$ . Let us take that order in one of its directions. Arbitrarily this is a choice we may regret - I propose as one of the conjuncts of the invariant

Po all solutions with $u < x$ have been printed

(Note that I have chosen $\kappa$ to characterize the upper bound: there may be a solution with $u = 0$ and I wish to characterize the empty set of printed solutions at initialization with natural $x$ .

Initialization of $x$ is no problem: $x := 0$ . The analysis of the question of for which value of $x$ we can guarantee that all solutions of (0) have been printed is postponed because it depends intimately on the precise shape of (0). We should first investigate what we can do with the fact that we are looking for zeros of an $P_{\bullet}(u, v)$ which is increasing in both arguments. We conclude

• each u is combined with at most one v and vice versa
• if values for $u$ are tried in increasing order, those for $v$ should be tried in decreasing order.

(The first conclusion is based on $f$ being increasing; for the second conclusion, $f$ being ascending suffices. If we have the knowledge, this is the moment to be inspired by the Welfare Crook with 2 sequences instead of with 3 , or by the Saddleback Search.)

How can we conclude that $x$ is a u-value to be combined with no v-value? From the existence of a y such that -remember that f is ascending in its second argument -

$$ f. (x, y) < 0 \land f. (x, y + 1) > 0 $$

How can we conclude that $x$ is a u-value for which there is a v-value? From

$$ f. (x, y) = 0 $$

in that case $y$ is the corresponding v-value we were looking for and , because $f$ is increasing in its second argument, we then conclude that

Combining the two observations, we propose to add

as conjunct to the invariant.

Now we return to the postponed question of an appropriate final value of $x$ . All solutions have been printed if $((u, v) \text{ solves } (0)) \Rightarrow u < x$ . We observe for any $(u, v)$ that solves (0):

$$ \begin{array}{l} P _ {i}: \quad x ^ {2} + (y + 1) ^ {2} > N \ u < x \ = {u a n d x n a t u r a l } \ 2 \cdot u ^ {2} < 2 \cdot x ^ {2} \ \Lleftarrow {\mathrm {a r i t h m e h i c} } \ 2 \cdot u ^ {2} \leq u ^ {2} + v ^ {2} \wedge u ^ {2} + v ^ {2} < 2 \cdot x ^ {2} \ = {(u, v) s o l v e s (0) } \ N < 2 \cdot x ^ {2} \ \Leftarrow \quad {\mathrm {a r i t h m e h i c} } \ N < x ^ {2} + (y + 1) ^ {2} \wedge x ^ {2} + (y + 1) ^ {2} \leq 2 \cdot x ^ {2} \ = {P _ {1} } \ (y + 1) ^ {2} \leq x ^ {2} \ = {x a n d y n a t u r a l } \ y + 1 \leq x \ = {\mathrm {a r i t h m e h i c} } \ \end{array} $$

$x > y$ ,

which suggest the guard $x \leq y$ and the further

P2: $0 \leq x \land x \leq y + 1$

In the above seven-step derivation - probably the price for the chosen direction of solution generation - we have been fortunate. In the path from $u < x$ to $x > y$ we have strengthened the predicate twice; is $x > y$ perhaps stronger than necessary? Or; is the corresponding guard $x > y$ perhaps weaker than necessary? The answer is no, because (0) might have a solution with $u = v$ .

With invariant

${P}{1} \cdot {P}{1} \cdot {P}_{2}$

a correct solution is now

$$ \begin{array}{l} \llbracket \operatorname {v a r} x, y: \mathrm {i n t}; x, y := 0, 0 \left{\rho_ {0} \wedge \rho_ {2} \right} \ ; \underline {{d o}} x ^ {2} + y ^ {2} \leq N \rightarrow y := y + 1 \underline {{o d}} \ {x ^ {2} + y ^ {2} > N, h e n c e P _ {1}, h e n c e P } \ ; \underline {{d o}} x \leq y \rightarrow \ i f x ^ {2} + y ^ {2} > N \rightarrow y := y - 1 \ [ x ^ {2} + y ^ {2} < N \rightarrow x := x + 1 \ \therefore x ^ {2} + y ^ {2} = N \rightarrow \operatorname {p r i n t} (x, y); x := x + 1 \ F i \ \end{array} $$

$$ \pi^ {\underline {{o d}}} $$

Our last step -under the assumption that squaring is an expensive operation - is a coordinate transformation. We shall do it in two steps, introducing new variables in the first one and deleting old variables in the last one.

Let us add the conjunct

${P}_{3} : c = {x}^{2} + {y}^{2} - N \land p = 2 \cdot x + 1 \land q = 2 \cdot y + 1$

1. $\forall r \in x,y,c,p,q : \operatorname{int};x,y,c,p,q \mathrel{\text{:=}} 0,0, - N,1,1} {P}_{3}$

$\therefore \underline{do} \in 0 \rightarrow c \mathrel{\text{:=}} c + q;\;y,q \mathrel{\text{:=}} y + 1,q + 2\;\left{ {P}{3}\right} \oplus \left{ {P}{3}\right}$

[\therefore \underline{\text{do}} \times {sy} \rightarrow ]

$$ \begin{array}{l} i f c > 0 \rightarrow y, q := y - 1, q - 2; c := c - q {P _ {3} } \ \left[\begin{array}{l}{c < 0 \rightarrow c := c + p; x, p := x + 1, p + 2}\end{array}\right. \left{P _ {3} \right} \ [ c = 0 \rightarrow p r i n t (x, y) \ ; c := c + p; x, p := x + 1, p + 2 {P _ {3} } \ \end{array} $$

E

$$ \prod_ {i} ^ {o d} $$

Thanks to ${P}_{3},x < y \equiv p \leq q$ and $\left( {x,y}\right) = \left( {p - 1/2,q - 1/2}\right) .$ Making these substiutions,we can eliminate $x$ and $y$ :

$$ \begin{array}{l} \left[ \begin{array}{l} \operatorname {v a r} c, p, q: \operatorname {i n t}; c, p, q := - N, 1, 1 \end{array} \right] \ ; \underline {{d o}} c \leqslant 0 \rightarrow c := c + q; q := q + 2 \underline {{o d}} \ ; \underline {{\underline {{d o}}}} p \leq q \rightarrow i f c > 0 \rightarrow q := q - 2; c := c - q \ [ ] c < 0 \rightarrow c := c + p; p := p + 2 \ [ 1 c = 0 \rightarrow p r i n t ((p - 1) / 2, (q - 1) / 2) \ \end{array} $$

F

$$ \pi^ {\frac {o d}{.}} $$

Note Once we have established that $y \coloneqq y + 1$ translates under invariance of $P3$ into

$$ {P _ {3} } c := c + q; y, q := y + 1, q + 2 {P _ {3} }, $$

the translation of the inverse statement $y \coloneqq y - 1$ is mechanical: the inverse statements of the trans-. lation in inverse order. (End of Note.)

The transition from the x.y-program to the c.p,q-program has only been added to show in one of my handouts an example of a coordinate transformation, complete with its justification by means of an invariant describing the relation between old and new coordinates.

Comparing my derivation of the x,y-program with the corresponding chapter in "A discipline of programming", I can only conclude that my memory is too good - or, equivalently, that I am not too good at getting rid of my past-. The current derivation displays a more successful disentanglement by isolating the consequences of the fact that we are dealing with a function that is increasing in both of its arguments. Also, today's solution is a bit more elegant, and in its derivation the stepping stone of a program with two nested repetitions has been avoided.

One of Algol 60's major mistakes - faithfully copied from FORTRAN - was the introduction of the "controlled variable" that was an intrinsic part of each repetitive construct. The notion of the controlled variable was killed in Euclid's algorithm

$$ \begin{array}{l} {0 \leq X \land 0 \leq Y } x, y := X, Y \ ; \underline {{d o}} x > y \rightarrow x := x - y \ \therefore y > x \rightarrow y = y - x \ \operatorname {o d} {x = X g c d Y } \ \end{array} $$

and I very well remember my excitement when I saw this code for the first time: it identified the notion of the controlled variable as a confusing artefact. (The above program was the first program I wrote with a repetition with more than 1 guarded command; it strongly suggested that repetitions with guarded command sets might be not a bad idea.) Nevertheless, old habits die hard, and several years later I still approached this problem by nested repetitions: the outer one for $x$ , the inner one for $y$ . A sobering thought.

Austin, 13 October 1988

proF. dr. Edsger W. Dgksha

Department of Computer Sciences

The University of Texas at Austin

Aushin, TX 75712 - 1188

United States of America