Path: utzoo!attcan!uunet!snorkelwacker!apple!agate!linus!linus!bs
From: bs@linus.mitre.org (Robert D. Silverman)
Newsgroups: comp.arch
Subject: Re: benchmark for evaluating extended precision (data, long)
Keywords: extended precision,multiply,benchmark,arithmetic
Message-ID: <120002@linus.mitre.org>
Date: 13 Sep 90 16:47:42 GMT
References: <2114@charon.cwi.nl> <119983@linus.mitre.org> <3999@bingvaxu.cc.binghamton.edu>
Organization: The MITRE Corporation, Bedford MA
Lines: 31
Xref: dummy dummy:1
X-OldUsenet-Modified: added Xref
In article <3999@bingvaxu.cc.binghamton.edu> kym@bingvaxu.cc.binghamton.edu.cc.binghamton.edu (R. Kym Horsell) writes:
: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
I'm talking about PRACTICAL algorithms here, not theoretical ones.
There doesn't seem to be a recursive bisection algorithm similar to
Karatsuba's that works for division. Methods based on FFT's are
ineffective until one reaches thousands of bits. For numbers in the
(say) 200 decimal digit range, ordinary long division is best, and
that algorithm is O(n^2).
--
Bob Silverman
#include
Mitre Corporation, Bedford, MA 01730
"You can lead a horse's ass to knowledge, but you can't make him think"