I recognize this module as an interesting insight into a possible evolution of computers. I do understand that it describes methods that, if implemented in hardware with the appropriate technics, would:
1. be a great step forward (precisely for the parallel computing Damian underlines it would allow);
2. imply that we consider the writing of algorithms differently from what we do now with our 'sequential' machines.

I live in a real world, work with a real PC, and have seen real people using this module. Its documentation does not say "this is a joke", and it is really available on CPAN.

If it was intended only as a joke, I had no way to know it, as its documentation doesn't say so. Moreover, for the reasons stated above, and for the fact that it provides a concise, expressive, elegant way of doing certain things (including computing minimums if you are not in a hurry) I do not think it should be considered <it>mainly</it> as a joke.

But I probably put too much focus on Q::S. I mainly intended it as an example to illustrate one of the possible shortcomings of <it>"concise, expressive, elegant"</it> ways of doing things: people misunderstanding how much calculus there is behind a simple, innocent, pretty expression.

Concerning the particular complexity of this prime number tester, I have to agree with you, Abigail. <it>It's just using different units than I am used to.</it> The problem is that the units are not specified. I did understand that Damian was expressing his complexity in terms of elementary quantic operations. But please admit that in everyday programming, what interests most of us is complexity in terms of time (or space, sometimes). This O(1) is pure prospective and does not mean much for the pragmatic programmer of today.

For your specific example of the point and the line, I agree too: I need, basically, 2 multiplications, one substraction, and one comparison. So it runs in constant time on everyday PCs (no matter how long the line is :).
Still, I can say it is an operation in O(n) (time) if I consider my little brain as the target platform (the larger the number, the longer it takes me to compute multiplications). But if I say so, I will definitely not forget to specify the unit (time) and the platform (you servant), for they are not what people are accustomed to.

(Maybe I should try and be more concise myself.) BTW, you seem to like polemics, Abigail, and I like that too :).

Sometimes, and this is on a case by case basis, simplication, abstraction, or any other way to reduce code may be simplier to maintain, document, and explain to others than code that might run faster but is overall a bit harder to read.

For example, given hypothetical:

my @d = 2 * all( @values );  # Method 1, assume 'use Q::S'
my @d = map { 2*$_ } @values; # Method 2
[download]

(and include method 3, which would be the functional/Haskill approach to this problem, which I know you can write, but I have no idea how to write it myself :-).

Method 2 is the fastest of all these, but to those not versed in perl, it may be harder to describe than method 1, which 'reads' like what it's supposed to do. Depending on the situation I was in when coding this, I might purposely using the Q::S method if only to convey meaning moreso than method 2; that situation would most likely be limited to scientific groups with understanding of computing but no strong computer language skills. On the other hand, if I was with a web site design shop, I'd automatcially advocate the use of method 2, which is straight forward from (what we hope to expect) the viewpoint of experienced computer programmers.

---

Dr. Michael K. Neylon - mneylon-pm@masemware.com || "You've left the lens cap of your mind on again, Pinky" - The Brain

Note that all big-Oh run time complexities are in numbers of elementary operations.

Having been a computer scientists, I strongly disagree with the statement that a Turing machine should be involved. Not at all! We use elementary operations in a certain computational model. That could be a Turing machine, but it could also mean a pointer machine, a Von Neumann architecture or something more abstract as arithmetic or geometry. Complexity analysis for calculations on a modern computer certainly don't assume a Turing machine as the underlaying model. You wouldn't be able to do binary search in O (log N) time on a Turing machine. You cannot achieve O (log N) on a Turing machine because indexing in an array cannot be done in constant time on a Turing machine - it's going to be at least linear in the amount of tape used.

-- Abigail

Good point. Turing machines can do any polynomial-time computation in polynomial time, but they might take a higher order polynomial length of time than some other type of machine. I was trying to compose a snappy reply, and got sloppy.

Still, when we talk about "polynomial time", what we really mean is "polynomial in the length of the problem using a reasonable encoding scheme." Not "polynomial in the number of entities in the input set," though we sometimes ignore the distinction. If the point and the line in your geometrical computation are specified with 512 bit numbers, that's a larger problem than if they were only 16 bits. You can't reduce that - it's information theory.

Any physical machine you build is going to have a finite number of bits of processing power available to it. We can't make computers out of infinitesimally thin Euclidian line segments. A quantum computer might be able to consider a virtually unlimited number of possibilities at the same time, but it has a limited number of qubits and they have to collapse down into one answer before it can be printed out on the screen.

If we start talking about machines that are impossible to build, are we still doing computer science? I don't say this to be facetious, but just to ask what computer science really is.

So this means sorting could be an O(N) operation (not necessarily using Q::S, but maybe Quantum::Sort??).