Oh, I'm sorry, I was under the impression that there existed O(N log N) multiplication algorithms, but apparently that's just conjectured. Right now the best s

Oh, I'm sorry, I was under the impression that there existed O(N log N) multiplication algorithms, but apparently that's just conjectured. Right now the best seems to be O(N log(N) 2^(log*(N))) ( http://en.wikipedia.org/wiki/Fürers_algorithm http://en.wikipedia.org/wiki/Fürers_algorithm ), which is slightly better than O(N log N log log N). Okay then. Also, the closed form solution would still be O(log N), since I don't think anybody yet considers exponentiation to be free :-)