Deep Dive into MQA-CD Encoding

A few weeks ago, I saw this video by Techmoan introducing the MQA-CD. MQA-CD is an audio CD that can be played back in a regular CD player, which is limited to 16-bit samples at 44.1 kHz. However, when played back through an MQA decoder, it promises better sound quality at 24-bit at 192 kHz.

Before we dig into the MQA marketing material, we need to understand that MQA is an encoding scheme that can exist outside of a CD, e.g. audio delivered over the radio or the Internet. Some of the non-CD transports are assumed to carry 24-bit at 48 kHz or higher. However, MQA-CD transport is limited to 16-bit at 44.1 kHz by the CD as its physical medium.

At first glance, MQA violates the Nyquist–Shannon sampling theorem which places a hard upper-bound that a signal at frequency B must be uniquely represented by at least 2B samples per second. However, we can give it some leeway by allowing for lossy encoding, even though some MQA marketing material claims that the encoding is lossless.

In a lossy scheme, we can steal some lowest significant bits from the sample to passthrough a data stream like MP3 that employs psychoacoustic coding. The lowest significant bits sound like the noise floor when listened to without the decoder, and the psychoacoustic coding allows us to put more detail into the noise more economically—basically, the data stream contains instructions about how to synthesize only sounds humans can hear, so we use less data than if we have to encode the full Nyquist-Shannon spectrum. Furthermore, the data stream only needs to contain the delta, which is the sound not already present in the non-stolen bits.

The question about MQA-CD is how many bits it is stealing?

Music Origami, according to MQA

The MQA website links to a blog by the MQA inventor, Bob Talks, which discusses the CD encoding with some technical detail, but it is a little confusing:

If the original source is 44.1kHz/24b or if the sample rate is 88.2, 176.4, 352,8 kHz, or DSD, then a standard MQA file will be 44.1 kHz/24b. The file contains the information for decoding, ‘unfolding’, and rendering.

This 24b MQA file is structured so that, if in distribution it encounters a ’16-bit bottle-neck’ (e.g. in a wireless or automotive application), then the information in the top 16 bits is arranged to maximise the downstream sound quality and still permits unfolding and rendering. See [2]

[2] MQA-CD: Origami and the Last Mile 

So reference [2] should contain some information about how the 24-bit is truncated to 16-bit. Here are some mentions:

The Green signal is completely removed by MQA decoders; but it is there so that we can hear more of the music when playback is limited to a 16-bit stream.

Sometimes we might want to listen to MQA music on equipment that doesn’t support 24 bits – maybe only 16? Rather than throw away all the buried information, MQA carries a small data channel (shown in Green) which can contain the ‘B’ estimates, enabling significantly improved playback quality on, e.g. a CD, over ‘Airplay’, in-car, to certain WiFi speakers and similar scenarios.

But it is also confusing because it shows the “Green signal” at -120 dB. We know that CD dynamic range is 96 dB, so it could not have been able to represent -120 dB noise floor. Samples at 24-bit has a dynamic range of 144 dB. However, the signal charts in the page shows a floor of -168 dB, and it was putting some information below -144 dB, which requires 28-bits.

As a side note, CD dynamic range of 96 dB is determined by the formula in terms of the 16-bit sample depth: \( 20 \times \log_{10}{2^{16}} \approx 96 \). As a rule of thumb, each bit in the sample represents about 6 dB in dynamic range.

Another page Deeper Look: MQA 16b and Provenance in the Last Mile also states that:

If we look at the block diagram above, we can see there are three components to the MQA data, broadly described as: i) top 16 bits, ii) MQA signalling and iii) bottom 8 bits

The block diagram clearly shows that the encoding result in 24-bit master file, but it still does not explain how that is reduced to MQA-CD which is bottlenecked to 16-bit samples.

Is Bit Stealing Plausible?

Since MQA still does not explain how the 24-bit master is reduced to 16-bit transport depth on a CD, we are left to speculate about the bit stealing idea earlier.

If we allow stealing 4 bits per sample, then we get a data rate of \( 2 \textit{ channels} \times 4 \textit{ bits per sample} \times 44100 \textit{ Hz} \approx 344 \textit{ kbps} \). This is pretty generous for high quality AAC, which is typically 256 kbps. The dynamic range before decoding is reduced from 96 dB to 72 dB, which is still comparable to a very high quality magnetic tape.

So I would say it is plausible, but it is inconclusive from the MQA marketing material if this is how they did it.

Furthermore, I don’t see the point of MQA’s “Music Origami” that folds 24-bit 192 kHz into 24-bit 48 kHz. If the transport is already capable of lossless 24-bit data, it must be a digital transport that is not a CD, which means there is no requirement to maintain backwards compatibility with a Red Book CD player. We can just use the whole stream to transport encoded audio, e.g. AAC or Flac. Even some later CD players in the 2000’s can play MP3 from a data CD or from a USB drive. That was all possible before MQA launched in 2014.

Which is why Techmoan says that even if you believe MQA delivers higher quality audio, it is a format that came a little too late.

Infinite Monkey Theorem, Debunked

If you let a monkey hit random keys on a typewriter for an infinite amount of time, will it happen to write the complete works of Shakespeare? Common wisdom says that not only will it write Shakespeare, but it will “almost surely” type every possible text an infinite number of times.

The proof idea goes like this: the probability to produce a permutation matching the complete works of Shakespeare is very small, but still greater than zero, so it will “almost surely” happen.

This is assuming that the monkey will eventually produce such permutation with a non-zero probability.

What if some permutations are simply not possible? There could be several reasons why this particular monkey and this particular typewriter could not have written Shakespeare. In order of increasing complexity:

• Some letters on the keyboard are broken, so some letters in the works of Shakespeare could not be typed.
• Due to the clumsiness of the monkey, it is only able to hit the space bar before or after hitting the letters above it. This means that every word has to always begin and end with ‘z’, ‘x’, ‘c’, ‘v’, ‘b’ ‘n’, or ‘m’. Shakespeare often used words that do not satisfy this criteria, so the works of Shakespeare could not have been written.
• The monkey is not able to repeat what it types within a certain number of words, so phrases like “to be or not to be” can never be written.

Infinity does not mean that it will allow every permutation. An example is the infinite sequence that concatenates the set of numbers consisting of only even digits: 0 2 4 6 8 20 22 24 26 28 40 42 44 46 48 etc. This sequence is infinite, but it would never contain the number ‘1’.

(On the other hand, the sequence of all even numbers concatenated will contain all finite numbers, including the odd numbers; since starting from 10—which is still an even number—we simply ignore the last digit and look at the tens and above, e.g. 123 is contained in 1230 1232 1234...)

This is not an argument about “almost surely” being practically zero. Instead, we are simply saying that infinite monkey is not almost surely, as the output is handicapped in some way albeit still infinite.

If we want to apply the infinite monkey theorem elsewhere, infinity alone is not sufficient. We have to also show that the desired permutation has a non-zero probability to happen, as this is not a given. On the contrary, an application that only establishes infinity can be disproven by showing that the desired output actually has a zero probability of happening.

∞ ⨉ 𝜀 = ∞ but ∞ ⨉ 0 = 0

In reality, we often confuse the mechanism of the permutation with the existence of output. We cannot say that the complete works of Shakespeare exists in the output implies that it must have been produced by the monkey. What if we have a programmed typewriter such that, if the monkey hits ‘s’ a million times in a row, would insert the complete works of Shakespeare? The complete works “exists” in the output, but it is not produced through the monkey's mechanism of permutation.

(This is analogous to the panspermia hypothesis saying that life could have been introduced from an external source rather than permuted naturally within the system. The hypothesis allows that a system capable of sustaining finite life may not have been able to produce life infinitely.)

Showing that some improbable event has zero probability of being produced could be quite difficult but “almost surely” doable. However, if we try to categorically argue that “almost surely” is practically zero, then the argument is only “almost surely” believable.

Deep Learning and Solving NP-Complete Problems

This recent article about AlphaGeometry being able to solve Olympiad geometry proof problems brings to my attention that there have been active research in recent years to combine deep learning with theorem proving. The novelty of AlphaGeometry is that it specializes in constructing geometry proofs, using synthetic training data guided by the theorem prover, which previous approaches have had difficulty with.

As a formal method like type checking of programming languages, theorem proving tries to overcome the ambiguity of mathematical proofs written in a natural language by formalizing proof terms using an algebraic language with rigorous semantics (e.g. Lean), so that proofs written in the language can be verified algorithmically for correctness. In the past, proofs had to be tediously written by humans, as computers had great difficulty constructing the proofs. Computers can do exhaustive proof search, but the search space blows up exponentially on the number of terms, which renders the exhaustive search intractable. However, once the proof is constructed, verification is quick. Problems that are exponentially intractable to solve but easy to verify are called NP-complete.

Traditional proof searching limits the search space to simple deductions, which can offload some tedium from manually writing the proofs. In recent years, machine learning is used to prune or prioritize the search space, making it possible to write longer proofs and solve larger problems. It is now possible for computers to construct complete mathematical proofs for a selected number of high school level math. The idea is a natural extension to what AlphaGo does to prune the game's search space, which I have written about before.

This is quite promising for a programming language that embeds theorem proving in its type system to express more elaborate safety properties, such as Applied Type System (ATS) designed by my advisor, which I have written about before. Programs written in ATS enjoy a high degree of safety: think of it as a super-charged Rust, even though ATS predates it. Now that generative AI can help people write Rust, a logical next step would be to create a generative AI for ATS.

I would be interested to see how machine learning can be applied to solve other NP-complete problems in general, such as bin-packing, job shop scheduling, or the traveling salesman problem. However, machine learning will face fierce competition here, as these problems are traditionally solved using approximation algorithms, which comes up with a close-enough solution using fast heuristics. Also, only a few of them have real-world applications. Admittedly, none are as eye catching as "AI is able to solve math problems" giving the impression of achieving general intelligence; in reality, the general intelligence is built into the theorem proving engine when it is used in conjunction with machine learning.

However, I think proof construction is a very prolific direction that machine learning is heading. Traditionally, machine learning models are a black box: even though it can "do stuff," it could not rationalize how to do it, let alone teaching a human or sharing the same insight with a different machine learning model. With proof construction, at least the proofs are human readable and have a universal meaning, which means we can actually learn something from the new insights gained by machine learning. It is still not general intelligence, and the symbolic insight to be gained might very well be a mere probabilistic coincidence, but it does allow machine learning to begin contributing to human knowledge.

Electronic Voting

As Americans patiently wait for the result of the 2020 POTUS election, I decided to take a crack at solving the electronic voting problem, with a timing that is perhaps a bit irrelevant now but may be useful again in 4 years. Now, this is by no means a survey of the state of the art on electronic voting, since the research has been done in so many years by so many people. This exercise is just for me to kill time.

A naive electronic voting may have accountability issues, namely we don't know if a vote is legitimate, or that all votes have been counted correctly. In order to know if a vote is counted, we need to know how everyone voted, which seems to sacrifice anonymity, unless we come up with an electronic analogy of a paper ballot. Traditionally, a ballot is issued in person at the voting station, or mailed to the voter in advance for mail-in ballots. There is little protection against ballot forgery, but it would be difficult to forge ballots physically at a large scale.

For electronic voting, a ballot certificate would be issued by the county government to the voter upon voter registration. The issuer is responsible for checking voter identification before issuance. This ballot certificate gives the voter the right to vote, and should be kept secret before a vote is cast (anyone in possession of a ballot certificate could vote with it). The certificate has a unique serial number and a cryptographic signature signed by the issuer. The serial number ensures that the ballot could only be used to cast at most one vote, and the signature verifies that the ballot is issued legally by the county. Otherwise the ballot is not tied to the voter identity. The county should maintain a separate list of voters who already registered, so a voter could only ever receive one ballot certificate. Large scale fraud can be detected if a county somehow issued more ballot certificates than its voting population.

Votes are entered into the voting databases along with the ballot certificate. Since the voting database contains no personal identifiable information, its entirety can be downloaded by the public when the election is concluded, and anyone could verify the presence of their vote in the database as well as independently count all of the votes. US population is only ~328 million, so the database is probably ever going to be only a few gigabytes which can comfortably fit onto a smart phone. Ballot verification could still take an hour or two (e.g. ed25519 signature verification rate is 71K/s), but counting should take only a few minutes if not seconds.

The challenge is distributing the database while ensuring integrity, since anyone receiving a copy with parts of the database missing or tempered with would not know it, and would arrive at a different count.

To ensure that all the votes are recorded without being tempered, they need to appear as part of a Merkle Tree (like how git works). Each transaction begins with a base commit hash and stores the content of the voting record (ballot, vote), both of which would derive a new commit hash. The complete voting record (base commit hash, ballot, vote, new commit hash) is returned to the voter as a receipt, and the new hash is also used as the base commit hash for the next transaction. Once a vote is cast, the ballot certificate is no longer a secret.

This simplest form of the Merkle Tree is just a singly linked list, but this type of transaction is very inefficient, since it requires all the votes in the universe to be sequentialized (i.e. only one person can vote at any given time). A tree construction allows transactions to take place in parallel (i.e. many people can cast vote at the same time). First, vote commits are built sequentially as before, but when a good number of votes are collected, they are finalized into a block by recording the final commit hash of the block. Multiple blocks can be built concurrently and then merged into a superblock by creating a commit hash out of all the block hashes. Superblocks can be similarly merged, until the election is closed, at which point the whole election is given a final commit hash.

This way, a voter can verify that their vote is counted in the election if they could trace their vote's commit hash all the way to the final election hash. If a vote is tempered with, the commit hash would change. If a block is tempered with, its block hash would change. If any merges are tempered with, the final election hash would change. Anyone could download the whole voting database and know that they have the complete, untempered copy. They can write software to independently verify the Merkle Tree without trusting the software that generated it.

The electronic ballot certificate could be printed on paper as a 2D barcode, which allows the bearer to cast the vote as a paper ballot. When voting in person, the voting machine would scan the barcode, ask for voter input, conduct the transaction, then print out the receipt with the commit hash. If this 2D barcode is a QR code, it could be scanned by a mobile app for possibly voting by phone, but the risk is that a malware app could steal the ballot and cast the vote without the voter's knowledge.

I believe this system is secure and practical, but I haven't spent too much time agonizing over it to tell for sure. I purposefully avoided mentioning the word "blockchain" because many people use that buzzword without knowing what it really means. Even though a blockchain is built using a Merkle Tree as well, it limits the rate of transactions globally to 5 per second (really low) through proof of work. The proof of work was invented for Bitcoin to impose artificial scarcity to the cryptocurrency. In the context of election, scarcity may be able to mitigate large scale fraud, but this is not a good way for ensuring election integrity.

Proof of Sum of Exponential Powers

My renewed interest in proof of exponent laws came from reading the Harvard Entrance Exam, 1869, which David Robert Palmer painstakingly typed up. In the exam there were sections of Latin and Greek, History and Geography, are various mathematics. It's fascinating that the words in Latin and Greek are already provided, so knowing how to conjugate is all that is required. The maths section are heavily calculation based. It seems that these sections serve to test only how nimble the minds are in solving known problems, but not so much whether the students exhibit the thought process of solving unknown problems. But one question intrigued me.

Question (3) in the algebra section reads, "What is the reason that when different powers of the same quantity are multiplied together their exponents are added?" It is asking about the exponent law for product of powers, \( a^x a^y = a^{x+y} \). Knowing the prestige of Harvard, giving an informal answer is likely not satisfactory. But most of the so called "proofs" that are prevalent in textbooks essentially boil down to the following reasoning.
\[ \underbrace{a a \dots a }_{x \text{ times}} \cdot \underbrace{a a \dots a}_{y \text{ times}} = \underbrace{a a a a \dots a a }_{x + y \text{ times}} \]
This appeals to the intuitive understanding that \( a^x \) is \(a\) multiplied \(x\) times, so when you multiply the result also by \(a\) for another \(y\) times, you get \( a^{x+y} \). This is hardly satisfying as a proof.

Another "proof" is to reduce this to the additive law of logarithms \( \log{xy} = \log{x} + \log{y} \), but this is like throwing the hot potato to someone else.
\[ \log{a^x a^y} = \log{a^x} + \log{a^y} = x + y \\
a^{\log{a^x a^y}} = a^{x+y} \]
And since \( a^{\log{c}} = c \) i.e. log is the inverse of exponent, so \( a^{\log{a^x a^y}} = a^x a^y = a^{x+y} \).

There are other exponent laws without formal proofs, but for this article I'm going to focus on the sum of powers.

Formal proof

We appeal to proof by induction for the formal proof. First we establish the base case for exponentiation:
\[ a^0 = 1 \]
Also recall that \(1\) is the multiplicative identity, so \( x\cdot 1 = 1\cdot x = x \), and \(0\) is the additive identity, so \( x+0 = 0+x = x \). From this, we can prove the base case where \( y = 0 \), i.e. \( a^x a^0 = a^x \cdot 1 = a^x = a^{x+0} \).

Now for the inductive case, we need both the axiom of exponentiation \( a^x \cdot a = a^{x+1} \) and the induction hypothesis \( a^x a^y = a^{x+y} \). We proceed to show that \( a^x a^{y+1} = a^{x+y+1} \).
\[ a^x (a^{y+1}) \underbrace{=}_{\text{axi.}} a^x (a^y a^1) \underbrace{=}_{\text{assoc.}} (a^x a^y) a^1 \underbrace{=}_{\text{I.H.}} a^{x+y} a^1 \underbrace{=}_{\text{axi.}} a^{(x+y)+1} \]
In the equations above, "axi." means the axiom of exponentiation, "I.H." means application of induction hypothesis, and "assoc." means associativity (which is true of all multiplicative groups, e.g. matrix multiplication).

Having painstakingly established a formal proof of the product of powers, there is a notable limitation, namely that we only allow natural number exponents, \( \{x, y\} \subseteq \mathbb{N} \). In particular, we don't allow negative (e.g. -3) or fractions (e.g. 3.14159...). Indeed, the real number domain has declarative properties that evade the mere application of modus ponens in discrete logic, which gives rise to the famous satire Alice in Wonderland.

Proof sketch in real number domain

Fortunately, all is not lost in the real number domain. We can invoke Taylor's theorem to expand the infinite series for calculating \( e^x \) and \( e^y \), multiply the two series, and see if \( e^{x+y} \) expands to the result of the multiplication.

The Taylor series for \( e^x \) is:
\begin{array}{rcl}
e^x & = & \sum^{\infty}_{n=0} {x^n \over n!} \\
 & = & 1 + {x^1 \over 1!} + {x^2 \over 2!} + {x^3 \over 3!} + {x^4 \over 4!} + \dots \\
 & = & 1 + x + {x^2 \over 2} + {x^3 \over 6} + {x^4 \over 24} + \dots
\end{array}
The following table multiplies the Taylor series for \( e^x \) and \( e^y \).
\begin{array}{c|cc}
\times & 1 & x & x^2 \over 2 & x^3 \over 6 & x^4 \over 24 & \dots \\ \hline
1 & 1 & x & x^2 \over 2 & x^3 \over 6 & x^4 \over 24 & \dots \\
y & y & xy & x^2 y \over 2 & x^3 y \over 6 & x^4 y \over 24 & \dots \\
y^2 \over 2 & y^2 \over 2 & xy^2 \over 2 & x^2 y^2 \over 4 & x^3 y^2 \over 12 & x^4 y^2 \over 48 & \dots \\
y^3 \over 6 & y^3 \over 6 & xy^3 \over 6 & x^2 y^3 \over 12 & x^3 y^3 \over 36 & x^4 y^3 \over 144 & \dots \\
y^4 \over 24 & y^4 \over 24 & xy^4 \over 24 & x^2 y^4 \over 48 & x^3 y^4 \over 144 & x^4 y^4 \over 576 & \dots \\
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots
\end{array}
The Taylor series for \( e^{x + y} \), expanded individually, is:
\begin{array}{c}
1 &+& (x+y) &+& {(x+y)^2 \over 2} &+& {(x+y)^3 \over 6} &+& {(x+y)^4 \over 24} &+& \dots \\
 & & || & & || & & || & & || \\
 & & x & & x^2 \over 2 & & x^3 \over 6 & & x^4 \over 24 \\
 & & y & & xy & & x^2 y \over 2 & & x^3 y \over 6 \\
 & & & & y^2 \over 2 & & xy^2 \over 2 & & x^2 y^2 \over 4 \\
 & & & & & & y^3 \over 6 & & xy^3 \over 6 \\
 & & & & & & & & y^4 \over 24
\end{array}
As you can see, the expansion of each term corresponds diagonally to the multiplication table above, so we can indeed show by Taylor expansion that \( e^x e^y = e^{x+y} \). This is only a proof sketch, but the enterprising mind could organize the table into a formal proof, using Binomial Theorem and Cauchy Product.

You might have noticed that we have only established the product law at base \(e\) but not other bases. For the other bases, recall that \( a^x = e^{x \ln a} \), so we have:
\[ a^x a^y = e^{x \ln a} e^{y \ln a} = e^{(x \ln a) + (y \ln a)} = e^{(x+y)\ln a} = a^{x+y} \]

Conclusion

There are two reasons why I suspect the Harvard entrance exam only expected the informal reasoning of counting the number of multiplicands. Cauchy (1789-1857) product is a fairly recent development to the time of the exam in 1869, which makes it unlikely to become part of the curriculum. There were no other questions that require the use of proof by induction so that it is also unlikely to be part of the curriculum either.

On the other hand, it is only after I became older (and overeducated) that I realize a lot of maths I was taught in grade school were really just informal proof sketches, and even so I didn't learn to question the profoundness of their limitations. The informal proof sketch of counting the multiplicands is limited to exponent in the natural number domain and would not work for real number exponents. I spent the better parts of my youth learning faux math!

Laws in the real number domain cannot be proven by counting alone because real numbers are uncountable. For this case I appealed to Taylor's Theorem, first expanding the polynomial series and showing the combined series are equal. I suspect many of the real number laws could use the same treatment.

How to Play Go Like a Computer Scientist

The board game of Go, or 圍棋 (weiqi), started receiving a lot of attention when AlphaGo beat the European champion Fan Hui in all of the five games. Now people are worried when AlphaGo is on its way to beat the world champion Lee Sedol, winning 3 out of 5 games so far. AlphaGo plays the game like no human as seen the game played before, inciting the awe of sadness and beauty. It is touted as an accomplishment of machine intelligence because traditionally the game of Go is very difficult for a machine to play well, whereas games like Chess is well-understood.

Board games are fascinating because a few number of rules allow an exponential number of possible game moves, some with winning outcomes, and some with losing. Traditionally, a naive game solver for any game tries all the possible positions of each alternate side's game play some number of steps ahead and chooses the first move that leads to the best gameplay after that number of steps, known as the min-max algorithm. Pruning heuristics is applied to reduce the search space so the computer does not waste time searching down "lost cause" paths, known as alpha-beta pruning. Even with pruning, the search space is still exponential to the number of positions on the board.

The keyword here is exponential. The machine can spend more time to compute, but for the amount of time spent \( t \), it can only search by \( \log{t} \) more steps. We can attempt to parallelize exponential search by enlisting the help of some number of machines, but it will still only allow us to advance the search depth by \( \log{n} \), i.e. the added intelligence is logarithmic to the number of machines.

Chess is well-understood. The number of game play combinations are vast, but we have found ways to prune the search space so that it is tractable with computer clusters that are practical to build. Computers can beat human playing Go on a smaller \( 9 \times 9 \) board with an upper bound of \( (9 \times 9)! \) or \( 10^{121} \) possible game plays, but on a professional championship level, the board size \( 19 \times 19 \) sports an exponential explosion of an upper bound of \( (19 \times 19)! \) or approximately \( 10^{768} \) possible game plays.

Even though Google might undertake the most ambitious of data center builds, they couldn't possibly shut down all the kitten videos on YouTube so AlphaGo could play against Lee Sedol with super-intelligence. Even so, they would achieve only logarithmic increase in intelligence. Building machines to brute force an exponential algorithm is a sure way to go bankrupt (NSA is an exception because the government prints the money).

I feel that a disclaimer is in order before I write any further. I don't have insider knowledge about how AlphaGo works. Everything I'm about to speculate comes from common sense and public sources.

AlphaGo algorithm reduces the search space using Monte-Carlo tree search, which means it randomly prunes some moves to reduce the branching factor, which allows the search to go deeper. The pruning is guided by deep neural network so it decreases the probability of pruning winning moves. Deep neural network works by building a hierarchy of signal processing nodes that amplifies certain signals after training.

When using DNN to recognize pictures, we can visualize how it works by looking at the images synthesized iteratively in order to boost certain signals.

In computer science, a pervasive strategy to design a super-efficient algorithm is by divide and conquer: basically, a big problem is solved by breaking down the problem into smaller sub-problems, until the problem becomes trivially solvable. Here are some examples:

• Sorting is taught to every first year computer science undergraduate. Given \( n \) items to sort, a naive sorting algorithm like bubble sort will take \( O(n^2) \) steps, whereas better ones using divide and conquer like quick sort or merge sort will take \( O(n \lg{n}) \) steps. If we are to sort 1000 items, this makes the difference between 1 million steps verses just 10000 steps.
• First year graduate student would likely learn about discrete Fourier transform. A naive DFT takes \( O(n^2) \) steps, whereas fast Fourier transform using divide and conquer takes \( O(n \lg{n}) \) steps.
• A naive matrix multiplication takes \( O(n^3) \) steps for an \( n \times n \) matrix, but Strassen's algorithm using divide and conquer takes \( O(n^{\lg{7}}) \) or approximately \( O(n^{2.8}) \) steps.
• The n-th Fibonacci number can be computed in \( O(\lg{n}) \) time using a divide and conquer method. The straightforward iterative method would take \( O(n) \) time, and a naive recursive method would take \( O(2^n) \) time. See Fibonacci Number Program for some examples in code.

For other algorithms, divide and conquer may not reduce the number of steps, but it still improves computation performance due to better cache locality. Divide and conquer is the basic idea of cache oblivious algorithms.

In other words, the real innovation of AlphaGo is not because machines achieved singularity, but because deep neural network approximated the divide and conquer method which happens to allow Go to be played efficiently.

The outcome of Go is scored by determining whether the pieces can survive locally, and the territorial occupation by the surviving pieces. This makes the winning strategy two-fold: on one hand, a player needs to ensure local survival of the pieces, but he has to take the territory into account. If a local battle is losing, it could be better for a player to strengthen his position on a different part of the board. This division of local and global thinking lends itself very well to using the divide and conquer method.

Here are some ideas how to divide. On the first level, we divide the board into subregions of \( 10 \times 10 \) each (figure left). We can also add overlapping subregions of \( 9 \times 9 \) or \( 9 \times 10 \) (figure right). This results in the first level division into \( 3 \times 3 \) subregions.

Left: Level 1

Right: Level 1 overlaps

Each subregion can be divided further into \( 5 \times 5 \) or \( 5 \times 4 \) grids with overlaps. In the following figure, only the division of the first subregion is shown, but it should be understood that the same division will take place for all first level subregions.

Left: Level 2

Right: Level 2 overlaps

A sketch of the divide and conquer algorithm would play Go by first choosing the region to play by valuation of the amount of territory it can likely occupy. Then within each region, it could brute force the positions that maximizes the survival of its own pieces.

Here is a very rough guesstimate of the number of steps needed to solve the game. These moves can be grouped into streaks of local battles taking place in \( 3 \times 3 \) subregions, and each streak is further divided to settle the \( 3 \times 3 \) sub-subregions which are about \( 5 \times 5 \) by grid. This reduces the amount of search space to be just:
\[ (5 \times 5)! \cdot (3 \times 3)! \cdot (3 \times 3)! \approx 10^{36} \]
This is a lot more computationally tractable. Of course, the caveat of my calculations is that I have never implemented a divide and conquer player for Go, and I don't know how well it works in practice. But even if we have to add a few levels of \( 3 \times 3 \) division, multiplying the search space by \( 9! \) still grows a lot slower than the exponential explosion of \( (9 \times 9)! \).
\[ (5 \times 5)! \cdot (9!)^9 \approx 10^{75} \]
Using this divide and conquer method, we can envision a game of Go played on a much bigger board, maybe like the 3-dimensional chess depicted in Star Trek.

The difference between the world champion Go player such as Lee Sedol and a modest Go player who happens to be a computer scientist, is that a computer scientist understands the power of divide and conquer. There is an immense beauty of divide and conquer that reaches far beyond game play. Nobody is worried when a computer doing quick sort can sort numbers faster than a human can with no sorting strategy, so why should we worry that a computer using divide and conquer can play a board game better than humans with only an ad-hoc strategy?

No, the computer is not about to achieve singularity. It is just a tool that helped us understand the game better.

Recursively Extensible Open Addressing Hash Table

There are two common ways to implement a hash table: open addressing and separate chaining. Both use a hash function to map keys to indices within an array for fast lookup. They differ in the conflict resolution strategy when multiple keys map to the same index. Upon conflict, open addressing searches for the next available index in the array through a probing policy such as linear probing (increment index by the number of probing attempts), quadratic probing (add index by the number of probing attempts squared), or by enumerating through different hash functions. Separate chaining avoids conflict by maintaining keys of the same index as a linked list.

Open Addressing

Separate Chaining

Both tables can be subject to O(n) lookup for a naive implementation when there are many collisions. A better one would dynamically resize the array depending on the load factor, but resizing is an expensive operation. For separate chaining, performance degradation can also be mitigated by using a balanced binary search tree instead of a linked list. Since the worst case access time is bound to O(lg n), it can retain some efficiency without resizing.

So far, this is text book material prior art.

In terms of cache efficiency, separate chaining has the disadvantage that list nodes may be scattered, so accessing the list can cause many cache misses. Open addressing is more cache friendly because the key and values are stored in a contiguous array. The question is: can we do away without resizing like separate chaining, but enjoy the cache efficiency of open addressing?

Yes we can. Here I introduce the recursively extensible open addressing hash table.

A recursively extensible open addressing hash table keeps the key/value in the table, but also reserves a pointer to an extension subtable per entry. To resolve conflict, it would first probe within the same table for an available slot but limited to k tries with a small k. If the search fails, then it would descend to the extension subtable at the original hashed index, creating the subtable only if necessary. It would use an orthogonal hash function to compute the index within this subtable, repeat the probing, and descend if necessary.

An orthogonal hash function is linearly independent (in the linear algebra sense) to the hash functions used in parent tables. An easy way to compute the orthogonal hash is to consider a universal hash function producing a 32-bit unsigned integer output. The first level hash table has 256 entries, and the index is based on the value in the 8 least significant bits. The second level tables also have 256 entries, with index drawn from the next 8 bits, and so on for the third and fourth levels.

As for the probing policy, we could use any policy like any open addressing hash table would, but linear probing has the best cache locality, and it is sufficient to achieve high load factor without compromising lookup performance. That is because the subtables all enjoy O(1) access as well.

Practicality of the Vector Packing Problem

Vector Packing problem is a generalization of the Bin Packing problem. In the simplest form, the Bin Packing problem seeks to find a placement of objects in a bin (both one-dimensional) such that the smallest number of bins are used. With vector packing, both the bin and the objects can have several dimensions, and different sizes along these dimensions.

Even in the simplest form, bin packing is an NP-hard problem. An approximation algorithm that runs in polynomial time may not produce the optimal solution, as you can see in the following illustration.

The first fit algorithm sorts objects by size, and then place each object in the leftmost bin that has space that fits. Heuristic algorithm can try harder to find a better solution at greater computation cost. You can imagine that vector packing problem is even more complex, now that the algorithm has to consider several dimensions of constraints.

Researchers understand that vector packing problem has a very useful application in cloud computing, and this has inspired a wealth of research literature. In this application, bins represent machines in a computation cluster, and each bin has a dimension for CPU, RAM, disk space, and network bandwidth. The objects represent jobs to be scheduled in the computing cluster. A job has specifications for the amount of CPU, RAM, disk, and network it uses. We can pack several jobs into a machine as long as the sum of the resources used is under what the machine could provide.

Better packing means that unused machines can be powered off to save energy, while the online machines have higher utilization which helps them achieve better energy efficiency. But as the number of jobs and the number of machines grow, even a heuristic algorithm can take a long time trying to find a better packing solution. This can grind cluster scheduling to a halt.

But I want to call this a fallacious understanding of the real problem we want to solve. In practice, cluster scheduling differs from the vector packing problem in the following regards:

• Bin or vector packing is a static problem where, once the objects are placed, they are not meant to be moved or displaced with other objects. Scheduling is inherently a dynamic allocation problem where objects come and go (i.e. they have a lifetime). An optimal packing does not imply optimal scheduling.
• The scheduling as a dynamic allocation problem is usually tackled as an offline problem where all the objects and their lifetimes are known in advance. In practice, we do not know the lifetime of jobs, which may stay running for a long time, but a human operator can always restart jobs or start new ones.
• A cluster typically have machines of a variety of specifications that differ in CPU speed, number of cores, amount of RAM, etc. Bin or vector packing assumes that all bins are of the same size.

Furthermore, in real life, job specification may not accurately reflect its actual usage. A job that says it uses a certain amount of CPU or RAM might end up using more, or using less. Or the usage may be sporadic. If it leaves garbage files around, then its disk space usage would grow indefinitely.

To define the cluster scheduling problem better, we need to understand that some of the dimensions are soft constraints, while others are hard. In general, temporal constraints are soft, while spatial constraints are hard, but there are exceptions.

• CPU is a soft constraint. If it is over-subscribed, jobs will just take longer to compute.
• Network bandwidth is also a soft constraint. If over-subscribed, then jobs will just take longer to send or receive data.
• RAM is a spatial constraint, except that can actually be over-subscribed because of virtual memory. When memory pressure is high, rarely used memory pages are swapped to disk to meet new memory demand. This swapping can cause performance issues, but it now allows a temporal trade-off, which makes RAM a soft constraint.
• In some deployment scenario, disk seek time is a scarce resource, but it is still a soft constraint. If over-subscribed, then jobs will simply spend more time waiting for disk I/O.
• The only remaining hard constraint is really the disk space.

These observations simplify cluster scheduling to become more like a one-dimensional bin packing problem, where jobs are scheduled only based on the amount of disk space it expects to use. To meet the soft constraints, we simply monitor each machine to see if the CPU, RAM, network, or I/O is oversubscribed. If so, the machine monitor will try to move contending jobs to different machines. But over-subscription will not prevent us from tentatively scheduling new jobs to run on this machine since we don't know about their performance characteristics yet; they may not cause any more contention.

It's not always a good idea trying to solve a practical problem with a theoretical one, since a theoretical solution is likely a lot harder, and will still miss the mark. Vector packing problem is not a practical representation of the cluster scheduling problem.

MISC: binary Galois Field multiplication

After reading NIST may not have you in mind, I decided that a new ISA should support binary Galois Field multiplication. Binary Galois Field is a special case of binary polynomial \( \mathbb{Z}_2[x] \) where addition and subtraction are already supported as XOR, written as \( \oplus \). What is missing for GF is multiplication and division in \( \mathbb{Z}_2[x] \). The binary polynomials are expressed as bit vectors where the \(n\)-th bit is the coefficient of the \(x^n\) term. Let \( \otimes \) be polynomial multiplication.

• pmul: \( (a, b) \to (r, s) \) where \( r s = a \otimes b \), i.e. \( r \) is the upper word of the result, and \( s \) is the lower word.
• pdiv.mod: \( (a, b) \to (q, r) \) where \( q \otimes b = a \oplus r \), i.e. \( q \) is the quotient and \( r \) is the remainder.

It's been a while since I last studied abstract algebra, so I might not have gotten all my terminology correct, but you get the idea.

MISC: Computation Modules

This is a continuation of Microcosmic Instruction Set Computer, defining the computation modules before I decide on the port assignments. The notation is \( (I_1, I_2, ..., I_m) \to (O_1, O_2, ..., O_n) \) for input ports \( I_1 ... I_m \) and output ports \( O_1 ... O_n \). The total number of input and output ports for each operator are kept as power of 2 to allow less fragmentation in port assignment later.

Arithmetic operators

• add: \( (a, b) \to (r, c) \) where \( r = a + b \) and \( c \) is the carry bit.
• sub: \( (a, b) \to (r, c) \) where \( r = a - b \) and \( c \) is the carry bit.
• neg: \( a \to b \) where \( b = -a \).
• mul: \( (a, b) \to (r, s) \) where \( r s = a \times b \), i.e. \( r \) is the upper word of the result, and \( s \) is the lower word.
• div.mod: \( (a, b) \to (q, r) \) where \( q \times b = (a - r) \), i.e. \( q \) is the quotient and \( r \) is the remainder.
• smul, sdiv.mod: same as mul and div.mod but for signed integers.
• and: \( (a, b) \to (c, c') \) where \( c = a \wedge b \) and \( c' = a \wedge \neg b \), both bitwise.
• or.xor: \( (a, b) \to (c, c') \) where \( c = a \vee b \) and \( c' = a \oplus b \), both bitwise.
• rot.left: \( (a, c) \to (r, s) \) where \( r \) is the result of shifting \( a \) to the left by \( c \) bits, and \( s \) is the overflow part of \( a \) adjacent to the least significant bit.
• rot.right: \( (a, c) \to (r, s) \) where \( r \) is the result of shifting \( a \) to the right by \( c \) bits, and \( s \) is the underflow part of \( a \) adjacent to the most significant bit.
• not: \( a \to b \) where \( b = \neg a \), bitwise.

Signed integers use two's complement representation, so they don't need to distinguish addition and subtraction. Note that the conditional branch instruction should be able to use the condition from the least significant bit which is the carry bit, as well as the most significant bit which is the signed bit. This allows comparing both signed and unsigned integers.

Convenience operators

• lea: \( (b, a, x) \to r \) computes \( r = 2^a \cdot x + b \).
• add3: \( (a, b, c) \to r \) computes \( r = a + b + c \).
• or3: \( (a, b, c) \to r \) computes \( r = a \vee b \vee c \).
• xor3: \( (a, b, c) \to r \) computes \( r = a \oplus b \oplus c \).

Any of these operators—especially “or” or “xor”—could be used for the purpose of joining the completion of all computations. These are not to be confused with non-deterministic join. A non-deterministic join is not necessary; just have two pipes connecting from some two different output ports to the same input port.

Conditional operators

• cond: \( (c, a, b) \to r \) where \( r = c \mathop{?}  a : b \), i.e. returns \( a \) if \( c \) is nonzero, otherwise \( b \).
• cx: \( x \to c \) where \( c \) extends the carry bit of \( x \) to fill the whole word.
• sx: \( x \to s \) where \( s \) extends the signed bit of \( x \) to fill the whole word.

Memory controller

• read: \( a \to r \) where \( r \) is the value of memory word at address \( a \) which must be word-aligned.
• write: \( (a, x, z) \to z' \) to write \( x \) to the memory word at address \( a \) which must be word-aligned, whenever \( z \) is also ready. The value of \( z \) is not used. When the write finishes, \( z' \) becomes ready with a zero value.
• cswap: \( (a, new, old) \to old' \) writes \( new \) to the memory word at address \( a \) only when \( a \) still contains the expected \( old \) value. The actual value of \( a \) before the swap is returned as \( old' \).

Byte packing

• pack: \( (a, b, p) \to r \) where \( r \) is the result of permuting the concatenation of \( a b \) according to mapping \( p \).
• unpack: \( (a, p) \to (r, s) \) where \( r \) and \( s \) are the two words selected from \( a \) by mapping \( p \) and they can be optionally sign extended.

Coprocessor I/O

• exec: \( (k, a_1, a_2) \to r \) sends a two-argument command to co-processor \( k \) and returns its result in \( r \).
• exec2: \( (k, a_1, a_2, a_3, a_4, a_5) \to (r_1, r_2) \) sends a five-argument command to co-processor \( k \) and returns a pair of results in \( r_1 \) and \( r_2 \).

This can be used to drive the floating point coprocessor as well. The floating point coprocessor, for example, would occupy a range of k in the coprocessor namespace, one for each operation.

Some concluding remark

The fact that all computation modules above have non-empty inputs and outputs means that this forms a monadic set of operators, where synchronization is accomplished by port pipelining. I guess you can call this Monadic Instruction Set Computer also.

Because of the fine granularity of some of the computation modules, it makes sense to base the cycle on the finest granule which is the gate distance, e.g. the bitwise operators are all single gate distance, hence single cycle. This means that while some modules are single cycle, others can be hundreds or thousands of cycles.

Minimal unsatisfiable 3-SAT example

The 3-SAT problem defined here is a stricter version than elsewhere, in the sense that each clause must contain exactly three literals. Some versions permit 1 or 2 literals.

To obtain a minimal unsatisfiable 3-SAT example, we start with a two-clause contradiction representing \( u_1 \wedge \neg u_1 \) as the base case. This base case is not 3-SAT. We then grow the clause as follows: suppose \( C_{i-1} \) containing \( i-1 \) variables is unsatisfiable, then let \( C_i = \left\{ c \vee u_i, c \vee \neg u_i \mid c \in C_{i-1} \right\} \), and \( C_i \) is also unsatisfiable.

To carry out the algorithm, we start with the base case.

• \( u_1 \)
• \( \neg u_1 \)

Then we add another variable to each clause:

• For \( u_1 \):
• \( u_1 \vee u_2 \)
• \( u_1 \vee \neg u_2 \)
• For \( \neg u_1 \):
• \( \neg u_1 \vee u_2 \)
• \( \neg u_1 \vee \neg u_2 \)

Then we add another variable to each clause:

• For \( u_1 \vee u_2 \)
• \( u_1 \vee u_2 \vee u_3 \)
• \( u_1 \vee u_2 \vee \neg u_3 \)
• For \( u_1 \vee \neg u_2 \)
• \( u_1 \vee \neg u_2 \vee u_3 \)
• \( u_1 \vee \neg u_2 \vee \neg u_3 \)
• For  \( \neg u_1 \vee u_2 \)
• \( \neg u_1 \vee u_2 \vee u_3 \)
• \( \neg u_1 \vee u_2 \vee \neg u_3 \)
• For \( \neg u_1 \vee \neg u_2 \)
• \( \neg u_1 \vee \neg u_2 \vee u_3 \)
• \( \neg u_1 \vee \neg u_2 \vee \neg u_3 \)

And here we have an unsatisfiable 3SAT example with 3 variables and 8 clauses.

Better upper bound for factorial?

Tonight I was puzzled by the question, if an algorithm \( \Pi \) has running time \( O(n!) \), does \( \Pi \) belong to EXPTIME? To rehash, EXPTIME contains all algorithms that has running time \( O(2^{n^k}) \). For brevity, I use the notation \( f(x) \prec g(x) \) to denote that \( f(x) \) grows slower than \( g(x) \). We know that \( 2^n \prec n! \prec n^n \) but I don't think I can show that \( n^n \) belongs to EXPTIME. I need a tighter bound.

It turns out that \( n! \prec 2^{n^2} \).

Proof.

• The growth of \( n! \) is \( \frac{(n+1)!}{n!} = n+1 \).
• The growth of \( 2^{n^2} = (2^n)^n \) is \[
  \begin{eqnarray}
  \frac{(2^{n+1})^{n+1}}{(2^n)^n}
    & = & \frac{(2 \cdot 2^n)^{n+1}}{(2^n)^n} \\
    & = & \frac{(2 \cdot 2^n)^n \cdot (2 \cdot 2^n)}{(2^n)^n} \\
    & = & \frac{2^n \cdot \cancel{(2^n)^n} \cdot (2 \cdot 2^n)}{\cancel{(2^n)^n}} \\
    & = & 2 \cdot 2^{2n} = 2^{2n+1} \\
  \end{eqnarray}
  \]

Since \( n+1 < 2^{2n+1} \) for all \( n \), therefore \( n! \prec 2^{n^2} \).

\( \Box \)

So it turns out that an \( O(n!) \) algorithm belongs to the class \( O(2^{n^k}) \) where \( k = 2 \), so such algorithm indeed belongs to EXPTIME.

---

Update (June 7, 2012): it turns out that showing \( n^n \) belongs to EXPTIME isn't that hard.

The growth of \( n^n \) is \[
\begin{eqnarray}
\frac{(n+1)^{n+1}}{n^n}
  & = & \frac{(n+1)^n (n+1)}{n^n} \\
  & = & \left( \frac{n+1}{n} \right)^n (n+1) \\
  & = & \left( 1 + \frac{1}{n} \right)^n (n + 1) \\
  & \approx & (n+1)e \\
\end{eqnarray}
\]

And that's because \( \lim_{n \to \infty} \left( 1 + \frac{1}{n} \right)^n = e \).  So \( n^n \) even grows slower than \( 2^{n^2} \).

The Tower Hotel Problem

Dynamic storage allocation problem, both as an online problem and an offline problem, is widely studied in literature, such as this article by Jordan Gergov. Here I present a similar problem which I call "The Tower Hotel Problem."

The Tower Hotel is peculiar. It has an infinite number of floors, but each floor has the same fixed number of rooms. The proprietor wanted to keep the number of floors open to the public minimal in order to save costs on maintenance; a closed floor incurs no cost. A floor is closed if none of the rooms are occupied. But as long as there is at least one occupied room, the floor must be open to public. Once a guest arrives and settles in a room, the proprietor must not ask the guest to move to another room.

In a zealous attempt to minimize cost, the proprietor requires all guests to make reservations before the year begins. The guest would indicate upon reservation the arrival and departure dates. Once the year begins, no more reservation can be made. The proprietor then optimizes the placement of guests on floors. This eccentric policy may be one reason the hotel is not very well known.

A number of years passed, and the proprietor passed away. His son knows nothing about hotel management, so the son interviewed three potential managers. In order to make the hotel more popular, the son required that the managers must not assume the reservations are made in advance. In fact, he went a step further and said that a guest could arrive at any time and leave at any time.

Each manager had a different strategy. The first manager would place the guest at random on any of the opened floors with vacancy (and open up a new floor if none of the existing floors are available). The second manager would place the guest on the floor with the most number of occupied rooms (but still has vacancy). The third manager would place the guest on the lowest numbered floor with vacancy. The third manager has an assistant who, due to her desire to be promoted, secretly proposes to the proprietor's son a slightly different strategy than her manager: she would locate the lowest numbered floors with vacancy, fill it entirely first, then find again the lowest numbered floors with vacancy, which may be lower than the previously chosen floor because some guests below may have checked out.

How does the proprietor's son determine which manager has the most cost-effective strategy? How do these managers and the third manager's assistant compare with what the proprietor could do, when the proprietor had full knowledge of all the reservations in the whole year?

---

This problem describes segregate fits dynamic storage allocation with virtual memory where all objects are of the same size, and a memory page could fit a fixed number of these objects. A virtual memory page has to be backed by a physical memory page if there is at least one object in the page. Once all objects in the page are freed, the physical memory page backing can be removed. This presents a different sort of fragmentation problem where certain long-lived objects can pin a memory page even though the page is mostly unused.

Evaluating RC4 as pseudo-random number generator

Update (September 3, 2012): I made some mistakes in my own implementation of RC4. An analysis of the mistake is documented in Mistake in my RC4 implementation. After fixing the mistake, I do not see the skewed distribution shown here. Please be advised that none of the blog posts in this blog are peer reviewed, and mistakes happen.

On the quest to look for a pseudo-random number generator that is easy to implement, I gave up on Mersenne Twister but took Wikipedia's advice that a stream cipher can be used for generating pseudo-random sequences. But it also mentions that RC4 is not a particularly uniform stream cipher which makes statistical attacks possible. Because of the simplicity of RC4, I decided to implement it and see really how bad it is. Since RC4 outputs a stream of bytes, I took the histogram of the byte value. The initialization key is the integer value of a stack-allocated object pointer, repeated for 64 bytes, and it's run on a 64-bit machine. I'm not sure if the fact that the key is highly regular has anything to do with the following non-uniform result that I observed.

byte	count	byte	count	byte	count	byte	count	byte	count	byte	count	byte	count	byte	count
0	5499938	32	50376	64	81740	96	253697	128	50004	160	144433	192	147856	224	147031
1	134854	33	50103	65	50386	97	115718	129	50024	161	49930	193	149593	225	50260
2	50352	34	50179	66	954060	98	50362	130	50185	162	50553	194	134910	226	78249
3	115332	35	50006	67	50091	99	50170	131	50543	163	50289	195	50516	227	49853
4	50214	36	50065	68	50256	100	50052	132	50288	164	49950	196	50532	228	50303
5	50089	37	50589	69	50173	101	50118	133	143783	165	49753	197	50182	229	50135
6	207241	38	49946	70	50416	102	50395	134	50447	166	50270	198	50145	230	134634
7	68820	39	50147	71	49985	103	49774	135	50252	167	50502	199	49368	231	49987
8	50212	40	103906	72	49950	104	50501	136	49803	168	50038	200	50032	232	50486
9	695154	41	49905	73	50137	105	50389	137	50085	169	50619	201	66006	233	49849
10	50439	42	49865	74	50472	106	50284	138	49508	170	50045	202	50336	234	50083
11	49682	43	948555	75	50141	107	50230	139	50294	171	50719	203	50300	235	50267
12	50378	44	49965	76	140698	108	50119	140	49772	172	50399	204	49963	236	50117
13	50466	45	50171	77	49814	109	50012	141	50385	173	50031	205	50072	237	49945
14	49591	46	50290	78	50219	110	90366	142	50177	174	50126	206	50585	238	50157
15	49776	47	50340	79	49916	111	49974	143	50224	175	50513	207	50350	239	50234
16	287052	48	205931	80	151232	112	131863	144	50079	176	50026	208	50226	240	131317
17	50022	49	50076	81	50134	113	49801	145	50487	177	50688	209	81920	241	50161
18	118991	50	50125	82	50108	114	50370	146	66545	178	78182	210	49998	242	50092
19	50209	51	50706	83	50292	115	50297	147	50236	179	50411	211	50458	243	50180
20	50170	52	50025	84	221044	116	116139	148	247793	180	215784	212	50185	244	50124
21	50371	53	49717	85	50259	117	50274	149	50327	181	758974	213	49808	245	90855
22	50365	54	49979	86	50302	118	50523	150	50228	182	50272	214	50685	246	50228
23	50467	55	50145	87	49797	119	105677	151	50108	183	50390	215	113514	247	50316
24	100861	56	78827	88	113581	120	138358	152	57005	184	53395	216	147492	248	50546
25	50158	57	49803	89	50264	121	50209	153	50095	185	50334	217	50396	249	50078
26	50483	58	50279	90	50176	122	49674	154	50292	186	50529	218	49915	250	50111
27	50211	59	49997	91	50337	123	50396	155	50453	187	49836	219	50170	251	50524
28	49859	60	50507	92	50313	124	50280	156	50059	188	50229	220	248053	252	49981
29	50580	61	50869	93	50417	125	49877	157	50355	189	50313	221	49937	253	50533
30	50142	62	50358	94	50292	126	50240	158	49821	190	50204	222	50139	254	49975
31	50265	63	50165	95	50352	127	244313	159	50410	191	50529	223	202938	255	246009

The result is pretty staggering non-uniform and heavily biased to 0. I quickly eyeballed the figures and labeled the counter with colors. Red means a strong bias. Yellow is a slight bias. Green is the ballpark figure for unbiased result, but they are still above a typical count in this table. The coloring is quite subjective, but I'm only using it to highlight the non-uniform bias.

Now, this observation also indicates that RC4 is a very poor stream cipher. The way stream cipher works is essentially that a stream of pseudo-random bytes are generated and XOR-ed byte-wise with the plaintext in order to obtain ciphertext. The prevalence of 0 values means that most of the plaintext will be identical to the ciphertext because 0 is an XOR identity. The fact that this bad encryption is possible with some key choices should worry a lot of people who are still using RC4.

By a stroke of luck, I tried a slightly modified RC4 that actually gives me a pretty uniform distribution. The difference (from the pseudo-code listing of the RC4 wikipedia article) is highlighted in grey below.

i := 0
j := 0
while GeneratingOutput:
    i := (i + 1) mod 256
    j := (j + S[i]) mod 256
    swap values of S[i] and S[j]
    K := S[(S[i] + S[j]) mod 256]
    output K ^ j  // was just K before
endwhile

This modification gives me the following histogram.

byte	count	byte	count	byte	count	byte	count	byte	count	byte	count	byte	count	byte	count
0	99723	32	100388	64	99739	96	99866	128	100026	160	100026	192	99831	224	99581
1	99941	33	99908	65	100363	97	100328	129	99741	161	100338	193	99792	225	99776
2	99968	34	100010	66	99589	98	100231	130	100649	162	100084	194	100218	226	99839
3	99896	35	99924	67	100465	99	100002	131	100093	163	99815	195	100478	227	100137
4	100439	36	99677	68	100004	100	99960	132	100165	164	99756	196	100064	228	100114
5	100081	37	99362	69	99664	101	99872	133	99887	165	100059	197	99523	229	100590
6	100570	38	99924	70	99648	102	99945	134	99459	166	99854	198	100170	230	100069
7	99812	39	99706	71	100066	103	99598	135	99532	167	99499	199	99956	231	99892
8	99969	40	100484	72	100074	104	99506	136	99831	168	100291	200	100164	232	99562
9	99840	41	99756	73	99128	105	100178	137	99646	169	100348	201	100121	233	99412
10	99793	42	100133	74	100019	106	100488	138	99882	170	99661	202	99864	234	99878
11	100208	43	100059	75	99717	107	100141	139	100374	171	100116	203	99643	235	100394
12	100157	44	99772	76	99846	108	100085	140	100180	172	99632	204	99928	236	100123
13	100098	45	100232	77	100017	109	100654	141	99955	173	99993	205	99858	237	100188
14	100017	46	100135	78	99566	110	99104	142	99640	174	99256	206	100243	238	99918
15	100259	47	100403	79	99459	111	99887	143	100255	175	99818	207	99612	239	99840
16	100139	48	99888	80	100828	112	99999	144	99820	176	100378	208	99663	240	99622
17	100093	49	100173	81	99633	113	100480	145	99804	177	99826	209	100564	241	99916
18	100257	50	99987	82	100502	114	100253	146	100554	178	99998	210	100183	242	100319
19	99835	51	100206	83	99776	115	99674	147	100726	179	99909	211	100548	243	99803
20	100010	52	99879	84	100188	116	99657	148	100255	180	99687	212	99937	244	100122
21	100424	53	100257	85	100197	117	100375	149	99866	181	99741	213	100669	245	99972
22	100062	54	99376	86	100123	118	100396	150	99623	182	100523	214	100195	246	100034
23	99729	55	100404	87	100620	119	100275	151	99594	183	99879	215	99921	247	100092
24	100076	56	99792	88	100383	120	99712	152	100641	184	99514	216	100226	248	100600
25	100107	57	100214	89	100079	121	99682	153	99723	185	99764	217	100120	249	99574
26	99785	58	100284	90	99835	122	100090	154	99805	186	99752	218	99850	250	100211
27	99839	59	99459	91	100332	123	100185	155	99557	187	100176	219	100167	251	100213
28	99700	60	99795	92	99966	124	100599	156	99709	188	100422	220	100028	252	100368
29	99776	61	99663	93	99596	125	99479	157	100266	189	100427	221	100172	253	99842
30	100319	62	99734	94	99962	126	99874	158	100068	190	100238	222	100058	254	99921
31	99537	63	100025	95	100043	127	100382	159	99910	191	99824	223	100697	255	99923

This is quite amazingly uniform, at least appears good enough for my purpose. It remains to be seen whether two or more consecutive bytes of output will still retain the same uniformity.

I think it is quite possible that this slight modification could be immune to the existing statistical attacks on RC4.

Interface checking

One of my regrets for C++ is that it doesn't have interface checking when you instantiate templates. Coupled with the delayed instantiation (the code of a method is not fully type checked until you use it), static type checking of template code has been a hit or miss. Also, when you do get a type error, it is incomprehensible, riddled with the instantiation details that shouldn't be there in the first place. Interface checking means that the compiler can do better type checking before template instantiation. Interface checking has been in development for some time (e.g. Boost Concept Check, ConceptCpp, N2773), but it didn't make into the C++11 standard.

Interface checking in most programming languages follow a fulfillment model where an interface specifies a collection of function method signatures, and if a class implements all the functions (fulfills all signatures), then it is said to implement the interface. This is the case for Java and Go language as well as C++ concept checking in development so far.

However, if I were to develop interface for a new language, I would choose a declarative model where a class has to explicitly declare the interface it intends to implement. The interface is uniquely identifiable in the program's namespace. The motivation is to prevent a class from unintentionally implementing an interface by coincidence.

This is especially important for C++ since many operators are overloaded. For example, a random access iterator looks a lot like an integral type at the interface level (in fact it is a super concept because you can dereference an iterator), but manipulating the iterator like an integral without observing begin() and end() will cause the iterator to go out of bounds.

This semantic gap can be bridged by a more precise type specification using dependent type (not to be confused with C++ dependent type, a class that is complete if and only if a template argument refers to a complete type; complete type here simply means the compiler knows its memory layout so you can do a sizeof(type), for example, to get its size), but we don't yet have an object oriented dependent type system with interface checking. Even if we can bridge the semantic gap, I argue that a declarative interface checking is not less powerful than fulfillment interface checking.

Suppose you have a class Foo that implements all the methods required for interface Xyzzy, but Foo doesn't declare it so. In the fulfillment model, Foo can be used to instantiate any template (generic) that requires interface Xyzzy, but not in the declarative model, which requires Foo to explicitly state that it implements interface Xyzzy. Even if you cannot modify the definition of Foo, all you need to do is to subclass Foo and declare that it implements Xyzzy, and pass it to the template.

Another idea I have (in the context of C++ concept checking at least) is to get rid of the distinction between a class and an interface. Any class can be used as an interface. That's because C++ allows declaration and implementation to be separate. Furthermore, when a class is said to implement another class, it does not mean the class is a subclass of the other class. The compiler will only check that the method signatures are congruent.

Redundancy of audio packets over lossy network

I wanted to know what people currently do to stream audio packets over a network with packet loss. There are several options for streaming audio, and they vary in their effectiveness against packet loss.

• AirTunes (aka. RAOP) is the protocol used between iTunes and Airport Express, based on RTSP (for establishing session) and RTP (for transmitting data). My impression is that you could stream MPEG4 AAC and Apple Lossless Audio Codec to Airport Express, though it may be possible to stream uncompressed audio too. Note that audio codec itself introduces algorithmetic delay, since compression is performed by grouping audio data over a time window. It is not clear how the protocol deals with packet loss, since RTP does not define how to deal with it.
• Netjack connects a jack server to a slave. It can stream CELT or raw audio over UDP. CELT is a low-delay audio codec with packet loss concealment. However, a tradeoff of the low-delay is that it could not resolve low-frequency pitch (~100Hz fundamental), and has to rely on a long term predictor. I'm not sure how this affects audio quality in practice. The packet transport does not seem to attempt recovering from packet loss, but instead relies on CELT codec for packet loss concealment. The slaves audio time clock is synchronized to the jack server.
• Netjack2 is really a distributed version of jack, using remote computing nodes to apply computationally intensive audio filtering, instead of playing back sound. They implemented a discovery protocol based on multicast, and audio is transmitted over UDP, with no packet loss handling. When using an audio adapter for streaming audio to a slave sound card device, audio resampling is applied to compensate for clock drift.
• Jacktrip, developed at Stanford CCRMA, connects two jack servers over a network. There doesn't seem to be any time synchronization. Data is transmitted over UDP, and it is possible to transmit redundant data in a rolling window in order to recover from data loss.
• There is a proposal (quick view) in using Reed-Solomon code to transmit data over UDP at Kyushu University.

I'm particularly interested in technique that could deal with wireless network packet loss, which has the following characteristics:

• Wireless packet radio implements low-level retransmission of lost or corrupt packets. On the higher level, this is perceived as high packet delay.
• When packet loss on the higher level does occur, it usually happens in bursts of packets. I estimate that up to 3ms radio gap is possible in normal condition.

Regarding these characteristics, the rolling window redundancy used by Jacktrip would not be effective, since a whole streak of packet loss would not be recoverable under this scheme.

When using Reed-Solomon, if we use byte-sized symbols, then a code block can only be 255 bytes (including parity). If we naively transmit the 255 bytes over UDP as a single packet, it is possible that the whole block would be dropped altogether. But we could transpose the block so that, when transmitting n blocks over m UDP packets, each UDP packet would contain 1/m slice of n blocks. This seems to be the approach taken by the Kyushu University proposal. This scheme, known as Cross-Interleaved Reed-Solomon, is also used on audio CD.

The Equal Sign

I've long wanted to write about the equal sign but I've been putting it off. Now I have an excuse to write about it. It is reported that students don't understand what the equal sign means. I don't blame them because the symbol '=' is overloaded. It is given four meanings in grade-school curriculum.

The first meaning is reduction of computation, as in arithmetics. An example is 2 × 5 + 4 × 3 = 10 + 12 = 22. In this case, the reduction from a formula 2 × 5 + 4 × 3 to a value requires us to compute 2 × 5 = 10 and 4 × 3 = 12 first because of operator precedence, and then compute 10 + 12 = 22. When arithmetics is taught, the equal sign is taken to mean reduction. We kind of gloss over the fact that there is a specific order of reduction, but the order of reduction was never formally taught.

The second meaning of the equal sign, by the time you learn algebra, is constraint solving. You are asked to solve for the value of the variables given a system of constraints, for example, 2x - y = 7 and x + y = 5. The answer is x = 4 and y = 1. Here the equal sign represents a goal, and you are asked to give solution for the goal.

The third meaning of the equal sign, if you haven't flunk out of math class yet, is definition. You would learn in pre-calculus about how to define a function, e.g. f(x) = x² - 3x + 7. The formula x² - 3x + 7 has been assigned a name f(x), and there is some implicit notion of variable scoping and substitution. For example, if you were to compute f(4) - 5, you would first reduce the function f(4) to its definition x² - 3x + 7, and then substitute x for 4, which gives you 4² - 3 × 4 + 7 = 11. Then you compute 11 - 5, which gives you 6. The equal sign here allows you to give a long formula a short name.

Finally, we encounter the fourth meaning in a very subtle way when we talked about constraint solving and function definition. That is, we also use the equal sign to denote a substitution. For example, you can verify that the system of constraints 2x - y = 7 and x + y = 5 yields the solution x = 4 and y = 1 if you substitute x for 4 and y for 1, so that 2 × 4 - 1 = 8 - 1 = 7, and 4 + 1 = 5. And to compute f(4), you will compute x² - 3x + 7 in the context of x = 4 because of the function definition.

All four notions of the equal sign are different, but they all use the same symbol. That's why students get confused. And it takes a computer scientist to tell a mathematician about that!