From: Henry Baker <hbaker1@pipeline.com> To: math-fun@mailman.xmission.com Subject: Re: [math-fun] avoidance of division (in English) Message-ID: <E1WOSHp-0007oE-Bd@elasmtp-scoter.atl.sa.earthlink.net> Content-Type: text/plain; charset="us-ascii"
The practical problem is that putting off division typically blows up the sizes of the eventual numerators & denominators, so that the total number of bit operations actually increases.
--no... Any algorithm involving +,-,*,/ can be done with rationals in such a way that only one division per output is needed, thus postponing the divisions until one at end. But that is not what Strassen & I were speaking of. Strassen was ENTIRELY eliminating divisions, not postponing or reducing to one. Example problem: given a matrix compute its determinant (or the coefficients of its characteristic polynomial.) These are normally done by algorithms involving divisions. But algorithms involving NO divisions are possible. By combining Strassen's trick with some other tricks by Kaltofen & Villard, and some updating, I can show that these things may be computed for NxN matrix with O(N^2.6945) ring-arithmetic operations. Meanwhile the best determinant and charpoly algorithms I know which do use divisions, take O(N^2.3727) field-arithmetic operations. It would be very interesting if you could decrease either of these magic exponents... or if you could prove a gap between the division-using and not complexities... -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)