On 3/14/14, Warren D Smith <warren.wds@gmail.com> wrote:
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.
--and furthermore, at least naively, a divisionless algorithm ought to behave optimally in the sense Baker is speaking of, no wasted bits of precision that were not really needed. (Really, still could have them due to additive cancellations, though.) It has always seemed strange to me that good divisionless determinant algorithms were not known. And even in the simpler case of a Toeplitz matrix, again, where is a good divisionless determinant algorithm?