Talk:Fast algorithms

Latest comment: 15 years ago by RobinK in topic Notability

So what?

edit

This article is defining a notion of a fast algorithm for evaluating a function on large numbers (i.e. numbers for which we need to care about bit complexity instead of the more usual RAM model) by relating the complexity of the function evaluation algorithm to the complexity of matrix multiplication by a   factor.

But why is this definition important? There's no deep result claimed here like saying for instance that you cannot do better than that for an arbitrary function. Is this a conjecture article? Pcap ping 23:42, 20 August 2009 (UTC)Reply

Wrong info on matrix multiplication?

edit

It appears to contradict Coppersmith–Winograd algorithm, i.e. the complexity cannot be below O(n2), unless I'm missing something... Pcap ping 23:58, 20 August 2009 (UTC)Reply

It's not matrix multiplication. It's just multiplication. The stated time-complexity is of the Schönhage–Strassen algorithm. We do know a faster one now: Fürer's algorithm --Robin (talk) 00:04, 21 August 2009 (UTC)Reply
Oops. Anyway, complexity of M(n) is not essential info in here, so I've replaced it with a link. Pcap ping 00:14, 21 August 2009 (UTC)Reply

Scope in lead vs body

edit

The lead claims that "Fast algorithms" is a field of study, but in the body all we find out is that "Fast algorithms" are class of algorithms, essentially those numeric algorithms that have Õ(n) bit complexity. That's not quite backing up the claim that this is a field of study. Pcap ping 08:26, 21 August 2009 (UTC)Reply

Notability

edit

So has anyone been able to establish notability for this concept? If not, I'm going to nominate this for deletion. If this concept of a "fast algorithm" is slightly notable, it can be mentioned in one line at analysis of algorithms or some such article. We don't need a full article for this one-line concept. --Robin (talk) 14:52, 22 August 2009 (UTC)Reply

You could just redirect it there. It avoids having to deal with the potentially uninformed opinions of those that might be impressed by the long reference list. If the concept is somehow known under another name in the English literature (that neither of us knows about), a non-admin ca (i) notice it, and (ii) resurrect the article much more easily with full history. Pcap ping 15:08, 22 August 2009 (UTC)Reply
Sounds good. Will do just that. --Robin (talk) 17:44, 22 August 2009 (UTC)Reply