brnstnd@stealth.acf.nyu.edu (Dan Bernstein) (12/02/89)
In article <16296@duke.cs.duke.edu> srt@grad19.cs.duke.edu (Stephen R. Tate) writes: [ This triple-quoted stuff is me (Dan) ] > > >Oh, give me a break. I recently proved that if n-digit multiplication > > >and addition take time O(M(n)) where n^a = O(M(n)) for some a > 1, then > > >n digits of e can be computed in time O(M(n)). (The best previous result > > >is O(M(n) log n), which also applies for a = 1, if you care.) > Side issue: how can you assume n^a = O(M(n))??? If, say, M(n) = n^1.003, then take a between 1 and 1.003. (grin) > looking at Shonhage-Strassen multiplication shows that n^a is NOT O(M(n)) Technical distinction: I didn't say M(n) was the time to perform multiplication; I said it was a bound on that time. You should have said ``Schonhage-Strassen multiplication shows that two n-digit numbers in the usual format may be multiplied by a one-tape Turing machine in time O(n log n log log n); hence your result does not apply to computations in that format on such a machine.'' There are many theoretical models for multidigit computation where M(n) is Theta(n^a) for some a > 1; not all representations of numbers admit fast multiplication. More importantly for practical applications, most multiplication routines ``out there'' use Theta(n^a) routines, since fast convolution methods do not win out until a huge number of digits. > Furthermore, if you are considering a less-than-optimal > multiplication algorithm, Be careful in saying ``less-than-optimal.'' My result applies whether M(n) is optimal or not. And we don't even know if n log n is optimal for usual n-digit multiplication on a random-access machine. (I think there's a bound of n log n / log log n for online multiplication, but none of the best known algorithms are online.) > then is shaving off a log(n) all that important? There are many, many, many papers on shaving off log log n's in far more obscure computations. I've shown that a wide class of problems run against the conventional wisdom about so-called transcendental computations, on a large class of machines; I don't think it's earth-shattering, but it's interesting. Also, this particular shaving closes an open gap. > Now -- can we please be finished with this silly categorizing and move > on to something interesting? A laudable sentiment. ---Dan