Shot noise arises from statistical fluctuations in the flow of charge carriers: if a single bit of data is represented by 10,000 electrons, the magnitude of the fluctuations will typically be about 1%.

Maximal block compression If one has data that consists of a long sequence of blocks, each of length b , and each independently chosen with probability p[i] to be of type i , then as argued by Claude Shannon in the late 1940s, it turns out that the minimum number of base 2 bits needed on average to represent each block in such a sequence is h = -Sum[p[i] Log[2, p[i]], {i, 2 b }] .

With more than two piles it was discovered in 1901 that one player can in general force the other to lose by arranging that after each of their moves Apply[BitXor, h]  0 , where h is the list of heights.

The first one on the bottom (with 63 comparisons) has a nested structure and uses the method invented by Kenneth Batcher in 1964: Flatten[Reverse[Flatten[With[{m = Ceiling[Log[2, n]] - 1}, Table[With[{d = If[i  m, 2 t , 2 i + 1 - 2 t ]}, Map[ {0, d} + # &, Select[Range[n - d], BitAnd[# - 1, 2 t ]  If[i  m, 0, 2 t ] &]]], {t, 0, m}, {i, t, m}]], 1]], 1] The second one on the bottom also uses 63 comparisons, while the last one is the smallest known for n = 16 : it uses 60 comparisons and was invented by Milton Green in 1969.

But any sequence of bits one extracts must be deduced from a corresponding sequence of measurements. … So this means that in effect an infinite computation is actually being done to generate each new bit. But with this amount of computation there are many ways to generate random bits.

[Computation of] mathematical functions The number of bit operations needed to add two n -digit numbers is of order n .

It is related to (a) by Gray code reordering of the rows, and to (b) by reordering according to (see page 905 ) BitReverseOrder[a_] := With[{n = Length[a]}, a 〚 Map[FromDigits[Reverse[#], 2] &, IntegerDigits[Range[0, n - 1], 2, Log[2, n]]] + 1 〛 ] It is also given by Array[Apply[Times, (-1)^(IntegerDigits[#1, 2, s] Reverse[IntegerDigits[#2, 2, s]])] &, 2^{s,s}, 0] where (b) is obtained simply by dropping the Reverse .

Each is roughly of the form BitXor[u[t], s[t]] Sin[ ω t] , where u[t] is a pseudonoise (PN) sequence generated by a linear feedback shift register (LFSR) (see page 1084 ); the idea is that by using a different PN sequence for each signal the corresponding s[t] can be recovered even if thousands are superimposed.

In addition, there has been the practical problem that if n is stored on a computer as a 32-bit number, then n 2 can be 64 bits long, and so cannot be stored in the same way.

In some earlier versions of Mathematica a considerably faster version of the program can be created by using the definition CAStep = Compile[{{rule, _Integer, 1}, {a, _Integer, 1}}, rule 〚 8 - (RotateLeft[a] + 2 (a + 2 RotateRight[a])) 〛 ] In addition, in Mathematica 4 and above, one can use CAStep[rule_, a_]:=rule 〚 8 - ListConvolve[{1, 2, 4}, a, 2]]] 〛 or directly in terms of the rule number num Sign[BitAnd[2^ListConvolve[{1, 2, 4}, a, 2], num]] (In versions of Mathematica subsequent to the release of this book the built-in CellularAutomaton function can be used, as discussed on page 867 .)