I contemplated the article and it occurred to me that integer matrix multiplication is probably O(n^2), without even any galactic constants. But it will need unit-cost integer math.
First, find a sufficiently large base b so that no intermediate calculation exceeds b-1 (one pass over the matrices should do the trick). Then encode each row of the left matrix as a big value A_i = sum_k a_ik * b^k. Encode each column of the the right matrix as B_j = sum_k b_kj * b^(n-k). Compute A and B explicitly (takes O(n^2) integer operations).
Now you extract the answer one element at a time. A_i * B_j has a bunch of terms including sum_k a_ik * b_kj * b^n. All other terms have different powers of b. So do an integer division by b^(n-1), discard the remainder, then take the result mod b, and that gives (a*b)_ij, costing one integer multiplication and two divmod operations per output element. Problem solved. Can I publish in FOCS?
This is, of course, a wild cheat: even with OpenAI’s latest and greatest galactic integer multiplication algorithm, this would be asymptotically slower than the plain high school matrix multiplication algorithm in any remotely realistic model of a computer.
I wonder whether the OpenAI papers contain cheats quite as outrageous as mine :)
(The moral here is that exact math is quite powerful, and exact math in time sublinear in the number of bits of precision is a great way to steal some performance.)
First, find a sufficiently large base b so that no intermediate calculation exceeds b-1 (one pass over the matrices should do the trick). Then encode each row of the left matrix as a big value A_i = sum_k a_ik * b^k. Encode each column of the the right matrix as B_j = sum_k b_kj * b^(n-k). Compute A and B explicitly (takes O(n^2) integer operations).
Now you extract the answer one element at a time. A_i * B_j has a bunch of terms including sum_k a_ik * b_kj * b^n. All other terms have different powers of b. So do an integer division by b^(n-1), discard the remainder, then take the result mod b, and that gives (a*b)_ij, costing one integer multiplication and two divmod operations per output element. Problem solved. Can I publish in FOCS?
This is, of course, a wild cheat: even with OpenAI’s latest and greatest galactic integer multiplication algorithm, this would be asymptotically slower than the plain high school matrix multiplication algorithm in any remotely realistic model of a computer.
I wonder whether the OpenAI papers contain cheats quite as outrageous as mine :)
(The moral here is that exact math is quite powerful, and exact math in time sublinear in the number of bits of precision is a great way to steal some performance.)