TICS

Yesterday, I gave at work a swift introduction to the JMM. Here.

Proposed in Mathematics: A Very Short Introduction. Given the following rules:

A1 Commutative law for addition:

A2 Associative law for addition:

A3 Additive identity:

A4 Additive inverse:

A5 Cancellation law for addition:

M1 Commutative law for multiplication:

M2 Associative law for multiplication:

M3 Multiplicative identity:

M4 Multiplicative inverse:

M5 Cancellation law for multiplication:

D Distributive law:

Let’s prove that (-1)(-1) = 1:

Say we need to swap the values of two variables, a and b. This is a classic problem in programming and it can be accomplished in a few ways.

Using a temporary variable

This is the straightforward method; just use a temporary variable to avoid losing one of the variable values:

Accumulating one of the values

Use one of the variables to temporarily keep track of both variable values:

Using Exclusive-OR (XOR)

The exclusive-or binary operator takes two bits and returns 1 only if both values differ, 0 if equal:

The bitwise exclusive-or operator (^) will apply the exclusive-or operation on every pair of bits of the inputs.

   01100110
^  01011110
   --------
   00111000

Three interesting properties, given A, B = {0, 1}:

1. A XOR 0 = A (i.e. A XOR 0 returns A whatever A)
2. A XOR 1 = ~A (i.e. A XOR 1 returns A flipped)
3. (A XOR B) XOR B = A

The third property requires further explanation. On the one hand, if B is 0 then, by 1), applying XOR B twice to A returns A itself. On the other, if B is 1 then we are flipping A twice by 2), which winds up returning A itself.

We base our last method of swapping two (integer) variables on those three properties:

More formally, the computation:

is equivalent to:

At this point, B has the original value of A, therefore:

This last method is the most performant among them all.

Question

Now that we have sifted through these three methods of swapping two variables, question: which is the main advantage of the first over the others?

Given the following implementation of the Ackermann’s Function:

What are the evaluations of these expressions:

Value: 1024

Value: 65536

Value: 65536

What are the mathematical counterparts of these procedures:

corresponds to:

corresponds to:

At some step i, the most inner combination in the form (A 2 (- n i)) will evaluate to 2 cause n-i=1. (A 1 x) is 2^x by the definition of g(n), and there will be n evaluations of such combination, resulting in:

This can be also expressed as a recurrence:

Evaluate (+ 4 5) using the following procedure definition:

This is a linear recursive process.

Now, use the following definition instead to evaluate the same combination:

This is an linear iterative process.