On Apr 28, 4:44 am, Bill Hart <goodwillh...@googlemail.com> wrote: > On Apr 27, 8:55 pm, rjf <fate...@gmail.com> wrote: > > > Oh, just another note. > > > There are people who have made their whole careers on devising > > asymptotically fast algorithms > > which have never been implemented, or (if they have been implemented) > > are not fast because > > their overly-simplified analysis does not fit the currently available > > computer efficiency profile. > > Indeed, their analysis may not fit any past profile of computers, and > > their algorithms were never > > practical. > > Interesting observation. Furer's algorithm is not practical, as are > some matrix multiplication algorithms. Do you have any other examples > in mind? >
Fastest algorithms in semi-algebraic geometry (see e.g. the book by S.Basu, R.Pollack, M.-F.Roy), such as quantifier elimination over the reals, fall under this, too. Nobody has found how to implement the symbolic infinitesimal deformations needed there efficiently, it seems. Dima > > > > Note, for example, that memory access is far more expensive than > > arithmetic, and that > > many computers now can multiply or add in comparable time; and they > > have several multipliers. Etc. > > I would say that memory access if far more expensive than addition, > but not arithmetic in general. FFT multiplication is n log n > (sometimes with a log log n, depending on what you are multiplying) > and I would say the memory access perhaps adds a hidden log n factor. > > Can you perhaps be more specific as to what you are hinting at? > > > > > RJF > > > -- > > To post to this group, send an email to sage-devel@googlegroups.com > > To unsubscribe from this group, send an email to > > sage-devel+unsubscr...@googlegroups.com > > For more options, visit this group > > athttp://groups.google.com/group/sage-devel > > URL:http://www.sagemath.org > > -- > To post to this group, send an email to sage-devel@googlegroups.com > To unsubscribe from this group, send an email to > sage-devel+unsubscr...@googlegroups.com > For more options, visit this group athttp://groups.google.com/group/sage-devel > URL:http://www.sagemath.org -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
