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 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"