f(f(n)) = -n

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

Vlad Patryshev said...

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=2^p with p>2:

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

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

Here are some properties of n:

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

Properties 3 and 4 allow partitionning ℤ/_2^p∖{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 ∈ ℤ/_2^p, f(f(x))=n(x).

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

f⁰ = i
f² = n
f³ = nf¹ = f¹n
f¹ = nf³ = f³n = f
f⁴ = n² = i

and so on, ∀ k ∈ ℕ, f^4k=i, f^4k+1=f, f^4k+2=n, f^4k+3=nf.

Let C be the function from ℤ/_2^p to 2^{ℤ/_2^p} such as: C(x) = { f⁰(x), f¹(x), f²(x), f³(x) }

Now, let (a,b) ∈ ℤ/_2^p², such as a ∉ {0, M}, f²(a)=n(a) and b ∉ C(a) [H]

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

And:

b = f⁰(b) ≠ a, by hypothesis [H].
f¹(b) ≠ a, since by hypothesis [H], b ≠ f³(a).
f²(b) ≠ a, since by hypothesis [H], b ≠ f²(a).
f³(b) ≠ a, since by hypothesis [H], b ≠ f¹(a).

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

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

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

Conclusion: When p>2, there is no function on ℤ/_2^p such as f² = n.

At most, we can find functions such as f(f(x)) = -x for all elements x of ℤ/_2^p 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 [4] or q ≡ 2 [4], then there are functions such as f²=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)
  "Mask off 32-bits of 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)))))))



C/USER[83]> (load"ffn=-n.lisp")
;; Loading file ffn=-n.lisp ...
;; Loaded file ffn=-n.lisp
T
C/USER[84]> (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[85]>