ross@spam.ua.oz.au (Ross Williams) (06/22/91)
> I am involved in designing high-performance algorithms but am finding > it difficult to work out what the state of the art is. Some algorithms > are written in C, some in machine code. Algorithms are run on PCs, > Macs, Suns, and other machines. It would be nice to standardize > somehow. > >I hate to pick nits, but the paragraph above confused the hell out of >me. An 'algorithm' is written in pseudecode or a natural language; >never in a programming language. I think we need to differentiate >between an 'algorithm' and an 'implementation of an algorithm'. When >we start thinking of an algorithm as inseparable from its >implementation, then we get such meaningless benchmark results as the >ones you referenced. I'm sorry, I should have said "Some algorithms have been IMPLEMENTED in C...". I am well aware of the difference between an algorithm and its implementation and I am aware of all the theory of complexity stuff that gives an order of complexity measure for an algorithm. However, in the real world, nearly all data compression algorithms are O(n) and so the next question is how to make O(n) data compression algorithms that happen to come up fast when they get coded up. I have invented one or two algorithms that tend to yield fast implementations but am having trouble telling if they are better than other algorithms that tend to yield fast implementations. Better is defined as "tending to lead to faster implementations when implemented in a particular language on a particular system". I disagree that an algorithm is never written in a programming language. A programming language is an ideal vehicle for the formal specification of an algorithm (far better than natural language). I think you're just overreacting to the fact that most algorithms are OVERSPECIFIED when written down in a programming language. Ross Williams ross@spam.ua.oz.au