Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!rpi!leah!bingvaxu!kym
From: kym@bingvaxu.cc.binghamton.edu (R. Kym Horsell)
Newsgroups: comp.arch
Subject: Re: benchmark for evaluating extended precision (data, long)
Keywords: extended precision,multiply,benchmark,arithmetic
Message-ID: <3999@bingvaxu.cc.binghamton.edu>
Date: 13 Sep 90 15:50:29 GMT
References: <3989@bingvaxu.cc.binghamton.edu> <119858@linus.mitre.org> <2114@charon.cwi.nl> <119983@linus.mitre.org>
Reply-To: kym@bingvaxu.cc.binghamton.edu.cc.binghamton.edu (R. Kym Horsell)
Organization: SUNY Binghamton, NY
Lines: 16

In article <119983@linus.mitre.org> bs@linus.mitre.org (Robert D. Silverman) writes:
\\\
>This is true when dividing a multi-precise number by a single precision
>number. It is not true when dividing two multi-precise numbers. 
>Dividing 2n bits by n bits is O(n^2) not O(n).
\\\

The complexity of _division_ is still (I understand) an open
question. According to some (old) work by Cook & Aanderaa it
is _unlikely_ to be less than O(n log n/(log log n)^2) on
``conventional'' machines.

The best division _algorithm_ that I know of performs 
O(n log n log log n).

-Kym Horsell