Xref: utzoo comp.software-eng:2581 comp.theory:97
Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!samsung!zaphod.mps.ohio-state.edu!gem.mps.ohio-state.edu!sunybcs!sbcs!stealth!brnstnd
From: brnstnd@stealth.acf.nyu.edu (Dan Bernstein)
Newsgroups: comp.software-eng,comp.theory
Subject: There are many different models for multidigit computation
Message-ID: <4116@sbcs.sunysb.edu>
Date: 2 Dec 89 07:21:29 GMT
References: <2608@fai.UUCP> <34818@regenmeister.uucp> <10014@june.cs.washington.edu> <16296@duke.cs.duke.edu>
Sender: news@sbcs.sunysb.edu
Reply-To: brnstnd@stealth.acf.nyu.edu (Dan Bernstein)
Distribution: usa
Organization: IR
Lines: 49

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


Brought to you by Super Global Mega Corp .com