Number of computations for multiplication

Question

I just read Marvin Minskys' "Form and Content in Computer Science" and found myself confused with the following paragraph:

A startling discovery was made about multiplication itself in the thesis of S.A. Cook [3], which uses a result of A.L. Toom, as discussed in Knuth [4]. Consider the ordinary algorithm for multiplying decimal numbers: for two n-digit numbers this employs n-squared one-digit products. It is usually supposed that this is minimal. But suppose we write the numbers in two halves, so that the product is N = (#A+B)(#C+D), where # stands for multiplying by 10 subscript{n/2}. (The left-shift operation is considered to have negligible cost.) Then one can verify that

N = ##AC + BD + #(A+B)(C+D) - #(AC+BD).

This involves only three half-length multiplications, instead of the four that one might suppose were needed. For large n, the reduction can obviously be reapplied over and over to the smaller numbers. The price is a growing number of additions. By compounding this and other ideas, Cook showed that for any e and large enough n, multiplication requires less than n*(1-e) products, instead of the expected n-squared.

I got stuck when I read stands for multiplying by 10 ... because I didn't understand what the subscript in this example means. I tried to find it out by googling about the complexity of multiplication and stuff like that, but couldn't find the answer.

Can you point me in the right direction here? I guess that this exact part is essential for understanding the formula in the middle. I would like to find out how this computation would resolve a multiplication.

Answer 1

It should be "10 superscript{n/2}" meaning $10^{n/2}$. For example, if $n=4$, then "6#2" would represent $6\cdot10^2=600$. All he's doing is shifting a decimal number to the left.

Answer 2

From context it's just exponentiation. I don't know why it's written with a subscript instead of a superscript, but with older papers you sometimes had a professional typesetter who might not have understood the material. (Of course nowadays typically do their own typesetting.)