# f(f(n)) = -n

In a comment to Steve Yegge's blog http://steve-yegge.blogspot.com/2008/02/portrait-of-n00b.html,

Tactically, you are very right. Strategically... I don't know. You mix two things together, strict typing in general, abuse of UML and class hierarchy, and overuse of strict typing where it is not necessary (I mean JavaScript).

Regarding class structures - it's probably hard to force people that love bureaucracy not to fill their code with Managers, Handlers, Helpers, and the like (none of these does any work, but they pass it around, like in real life). But I'm afraid this anti-bureaucratic rant has nothing to do with the issue of modeling in general.

I'll give you one example, an interview problem. Write a function f on 32-bit integers that, applied twice, it negates the integer. f(f(n)) = -n.

Try to solve it without any kind of model, by just applying randomly ad-hoc xors and shifts.

9:00 PM, February 11, 2008

Assuming Vlad means integers represented in two-complement, which is the case with 99% of the processors nowadays, such a function just doesn't exist. Here's the mathematical proof.

First, in ℤ, such functions indeed exist. For example:

``````
(defun integer/f (n)
"
Assuming n is an INTEGER, (= (- n) (f (f n)))
0 -->  0
+1 --> -2 --> -1 --> +2 --> +1
+3 --> -4 --> -3 --> +4 --> +3
...
+(2k+1) --> -(2k+2) --> -(2k+1) --> +(2k+2) --> +(2k+1)
"
(declare (type integer n))
(if (zerop n)
0
(if (plusp n)
(if (oddp n)
(1- (- n))
(1- n))
(if(oddp n)
(1+ (- n))
(1+ n)))))
``````

The same function works in one-complement representation, too (assuming `zerop` indicates both +0 and -0).

But things are different in ℤ/m, because of the special properties of the negation in these sets.

When m=2p with p>2:

Let i be the identity function: ∀ a ∈ ℤ/m, i(a)=a

Let n be the negation function in two-complement on ℤ/2p. n is defined as: n(x) = 1+(¬x), with ¬x being the bitwise not operation.

Here are some properties of n:

1. n(0)=0
2. let M = -2p-1. In two-complement arithmetic, n(M)=M.
3. ∀ a ∈ ℤ/2p∖{0, M}, n(a)≠a
4. ∀ a ∈ ℤ/2p, n(n(a))=a ; n2 = i
5. ∀ (a,b) ∈ ℤ/2p2, n(a)=n(b) ⇒ a=b (trivially deduced from 4.)

Properties 3 and 4 allow partitionning ℤ/2p∖{0, M} in two symetrical subsets, one representing the positive integers, and the other their opposite negative integers.

Now, assume there is a function f such as ∃ x ∈ ℤ/2p, f(f(x))=n(x).

Let's denote the composition of functions by mere juxtaposition: fg = f○g.

• f0 = i
• f2 = n
• f3 = nf1 = f1n
• f1 = nf3 = f3n = f
• f4 = n2 = i
and so on, ∀ k ∈ ℕ, f4k=i, f4k+1=f, f4k+2=n, f4k+3=nf.

Let C be the function from ℤ/2p to 2ℤ/2p such as: C(x) = { f0(x), f1(x), f2(x), f3(x) }

Now, let (a,b) ∈ ℤ/2p2, such as a ∉ {0, M}, f2(a)=n(a) and b ∉ C(a) [H]

Since a ∉ {0, M} and f2(a)=n(a), | C(a) | = 4.

And:

• b = f0(b) ≠ a, by hypothesis [H].
• f1(b) ≠ a, since by hypothesis [H], b ≠ f3(a).
• f2(b) ≠ a, since by hypothesis [H], b ≠ f2(a).
• f3(b) ≠ a, since by hypothesis [H], b ≠ f1(a).

in consequence, all the subsets C(x) are disjoint and form a partition of ℤ/2p.

However, since C(0) = { 0, f1(0) }, and C(M) = { M, f1(M) }, and ℤ/2p is divisible by 4 when p>2, there is at least two other elements of ℤ/2p, let's call them N and O, such as C(O) = { O, f1(O) } and C(N) = { N, f1(N) }.

We have f2(O) = O and f2(N) = N, which shows that ∃ x ∈ ℤ/2p, f(f(x)) ≠ -x.

Conclusion: When p>2, there is no function on ℤ/2p such as f2 = n.

At most, we can find functions such as f(f(x)) = -x for all elements x of ℤ/2p but for two of our choosing. Note that we can choose to break the formula for 0 and M, since -0 is not very interesting and -M in two-complement is pathologic anyways.

(For other sets, ℤ/q if q ≡ 1  or q ≡ 2 , then there are functions such as f2=n).

Finally, we can implement a function that does almost what was asked, only with a bug: we get to choose which two values for which f(f(x)) ≠ -x.

But of course, not using only XOR and SHIFT operations! Using only NAND and SHIFT, it would be possible (since NAND is all is needed to build all the boolean operators, but XOR is not powerful enough to do so, see Wikipedia articles on Logical connective or on Functional completeness).

Technically, we don't need full functional completeness for XOR (⊻), we'd only need to be able to implement logical not and increment. For logical not, there's no problem, a ⊻ 1 = ¬a, but for increment, we need to implement a semi-adder, where s = a ⊻ b and c = a ∧ b. But there is no way to get AND from XOR, because XOR is closed over {0, 1, a, b, ¬a, ¬b, a⊻b, ¬(a⊻b)} (any application of XOR on two elements of this set gives an element of this set).

Since two-complement negation on binary words of length w is defined as `(mod (1+ (lognot n)) (expt 2 w))`, we need more than just XOR and SHIFT... Two impossibilities for one interview question. Vicious! And asking to do that "without any kind of model", tskss, tskss, I wouldn't like to work at such a company, unless the question was designed exactly for that, to weed out people doing what they're told without thinking...

``````
(declaim (ftype (function (integer) (unsigned-byte 32))
32-bit
32-bit/2-complement-neg))

(defun 32-bit (x)
(logand #xffffffff x))

(defun 32-bit/plusp (n)
"Whether N represents a positive integer."
(declare (type (unsigned-byte 32) n))
(zerop (ldb (byte 1 31) n)))

(defun 32-bit/2-complement-neg (n)
"Return the negation of N in 2-complement."
(declare (type (unsigned-byte 32) n))
(32-bit (1+ (lognot n))))

(defun 32-bit/f (n)
"
Assuming n is a 32-bit 2-complement signed integer different
from 0 and -2³¹,  (= (- n) (f (f n)))
"
(declare (type (unsigned-byte 32) n))
(32-bit
(case n                              ; (f (f n))
((#x00000000) #x80000001)          ; --> 0x80000000
((#x80000000) #x7FFFFFFF)          ; --> 0x00000000
((#x7FFFFFFF) #x00000000)          ; --> 0x80000001
((#x80000001) #x80000000)          ; --> 0x7fffffff
;;  For the above exceptions, any permutation is valid;
;;  we choose here to break it for 0 and M, with
;;  f(f(0))=M and f(f(M))=0,
;;  to keep f(f(2³¹-1))= -(2³¹-1) and f(f(-(2³¹-1)))= 2³¹-1
(otherwise
(if (32-bit/plusp n)
(if (oddp n)
(lognot n)
(1- n))
(if (oddp n)
(+ (lognot n) 2)
(1+ n)))))))

``````

``````

T
C/USER> (test-f)

i           -i    (f (f i))        (f i) (- (f (f i)))
00000000     00000000 /=  80000000    80000001     80000000
00000001     FFFFFFFF     FFFFFFFF    FFFFFFFE     00000001
00000002     FFFFFFFE     FFFFFFFE    00000001     00000002
00000003     FFFFFFFD     FFFFFFFD    FFFFFFFC     00000003
00000004     FFFFFFFC     FFFFFFFC    00000003     00000004
00000005     FFFFFFFB     FFFFFFFB    FFFFFFFA     00000005
00000006     FFFFFFFA     FFFFFFFA    00000005     00000006
00000007     FFFFFFF9     FFFFFFF9    FFFFFFF8     00000007
00000008     FFFFFFF8     FFFFFFF8    00000007     00000008
00000009     FFFFFFF7     FFFFFFF7    FFFFFFF6     00000009
0000000A     FFFFFFF6     FFFFFFF6    00000009     0000000A
0000000B     FFFFFFF5     FFFFFFF5    FFFFFFF4     0000000B
0000000C     FFFFFFF4     FFFFFFF4    0000000B     0000000C
0000000D     FFFFFFF3     FFFFFFF3    FFFFFFF2     0000000D
0000000E     FFFFFFF2     FFFFFFF2    0000000D     0000000E
0000000F     FFFFFFF1     FFFFFFF1    FFFFFFF0     0000000F
00000010     FFFFFFF0     FFFFFFF0    0000000F     00000010
00000011     FFFFFFEF     FFFFFFEF    FFFFFFEE     00000011
00000012     FFFFFFEE     FFFFFFEE    00000011     00000012
00000013     FFFFFFED     FFFFFFED    FFFFFFEC     00000013
FFFFFFFF     00000001     00000001    00000002     FFFFFFFF
FFFFFFFE     00000002     00000002    FFFFFFFF     FFFFFFFE
FFFFFFFD     00000003     00000003    00000004     FFFFFFFD
FFFFFFFC     00000004     00000004    FFFFFFFD     FFFFFFFC
FFFFFFFB     00000005     00000005    00000006     FFFFFFFB
FFFFFFFA     00000006     00000006    FFFFFFFB     FFFFFFFA
FFFFFFF9     00000007     00000007    00000008     FFFFFFF9
FFFFFFF8     00000008     00000008    FFFFFFF9     FFFFFFF8
FFFFFFF7     00000009     00000009    0000000A     FFFFFFF7
FFFFFFF6     0000000A     0000000A    FFFFFFF7     FFFFFFF6
FFFFFFF5     0000000B     0000000B    0000000C     FFFFFFF5
FFFFFFF4     0000000C     0000000C    FFFFFFF5     FFFFFFF4
FFFFFFF3     0000000D     0000000D    0000000E     FFFFFFF3
FFFFFFF2     0000000E     0000000E    FFFFFFF3     FFFFFFF2
FFFFFFF1     0000000F     0000000F    00000010     FFFFFFF1
FFFFFFF0     00000010     00000010    FFFFFFF1     FFFFFFF0
FFFFFFEF     00000011     00000011    00000012     FFFFFFEF
FFFFFFEE     00000012     00000012    FFFFFFEF     FFFFFFEE
FFFFFFED     00000013     00000013    00000014     FFFFFFED
FFFFFFEC     00000014     00000014    FFFFFFED     FFFFFFEC
7FFFFFEC     80000014     80000014    7FFFFFEB     7FFFFFEC
7FFFFFED     80000013     80000013    80000012     7FFFFFED
7FFFFFEE     80000012     80000012    7FFFFFED     7FFFFFEE
7FFFFFEF     80000011     80000011    80000010     7FFFFFEF
7FFFFFF0     80000010     80000010    7FFFFFEF     7FFFFFF0
7FFFFFF1     8000000F     8000000F    8000000E     7FFFFFF1
7FFFFFF2     8000000E     8000000E    7FFFFFF1     7FFFFFF2
7FFFFFF3     8000000D     8000000D    8000000C     7FFFFFF3
7FFFFFF4     8000000C     8000000C    7FFFFFF3     7FFFFFF4
7FFFFFF5     8000000B     8000000B    8000000A     7FFFFFF5
7FFFFFF6     8000000A     8000000A    7FFFFFF5     7FFFFFF6
7FFFFFF7     80000009     80000009    80000008     7FFFFFF7
7FFFFFF8     80000008     80000008    7FFFFFF7     7FFFFFF8
7FFFFFF9     80000007     80000007    80000006     7FFFFFF9
7FFFFFFA     80000006     80000006    7FFFFFF9     7FFFFFFA
7FFFFFFB     80000005     80000005    80000004     7FFFFFFB
7FFFFFFC     80000004     80000004    7FFFFFFB     7FFFFFFC
7FFFFFFD     80000003     80000003    80000002     7FFFFFFD
7FFFFFFE     80000002     80000002    7FFFFFFD     7FFFFFFE
7FFFFFFF     80000001     80000001    00000000     7FFFFFFF
80000013     7FFFFFED     7FFFFFED    7FFFFFEE     80000013
80000012     7FFFFFEE     7FFFFFEE    80000013     80000012
80000011     7FFFFFEF     7FFFFFEF    7FFFFFF0     80000011
80000010     7FFFFFF0     7FFFFFF0    80000011     80000010
8000000F     7FFFFFF1     7FFFFFF1    7FFFFFF2     8000000F
8000000E     7FFFFFF2     7FFFFFF2    8000000F     8000000E
8000000D     7FFFFFF3     7FFFFFF3    7FFFFFF4     8000000D
8000000C     7FFFFFF4     7FFFFFF4    8000000D     8000000C
8000000B     7FFFFFF5     7FFFFFF5    7FFFFFF6     8000000B
8000000A     7FFFFFF6     7FFFFFF6    8000000B     8000000A
80000009     7FFFFFF7     7FFFFFF7    7FFFFFF8     80000009
80000008     7FFFFFF8     7FFFFFF8    80000009     80000008
80000007     7FFFFFF9     7FFFFFF9    7FFFFFFA     80000007
80000006     7FFFFFFA     7FFFFFFA    80000007     80000006
80000005     7FFFFFFB     7FFFFFFB    7FFFFFFC     80000005
80000004     7FFFFFFC     7FFFFFFC    80000005     80000004
80000003     7FFFFFFD     7FFFFFFD    7FFFFFFE     80000003
80000002     7FFFFFFE     7FFFFFFE    80000003     80000002
80000001     7FFFFFFF     7FFFFFFF    80000000     80000001
80000000     80000000 /=  00000000    7FFFFFFF     00000000
NIL
C/USER>

``````

``` | Mirror on informatimago.com | Mirror on free.fr | ``` 