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? > > 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 at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org