in reply to about Coolness, Impatience and Complexity
I doubt I've ever seen someone so completely miss the
point of a module. Q::S isn't about speed, it's about
showing the power of quantum operations, the any
and all functions. It's a simulation
of a machine. And yes, the primality tester is
O(1). It's just using different units than you are used to.
Note that all bigOh run time complexities are in numbers
of elementary operations. For instance, in computational
geometry deciding whether a point lies right or left
of a line is an O(1) operation, regardless how many bits we
need to express the coordinates of the points when we would
actually simulate such operations on a current day device.
In the world of Q::S we have different elementary operations.
Finally it should be pointed out that Q::S was mainly intended
as a joke. Most people got it  but some didn't.
 Abigail
Re: Re: about Coolness, Impatience and Complexity
by Blop (Monk) on Jul 12, 2001 at 19:55 UTC

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 :).
Blop!
 [reply] 

my @d = 2 * all( @values ); # Method 1, assume 'use Q::S'
my @d = map { 2*$_ } @values; # Method 2
(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  mneylonpm@masemware.com

"You've left the lens cap of your mind on again, Pinky"  The Brain
 [reply] [d/l] 
Re: Re: about Coolness, Impatience and Complexity
by no_slogan (Deacon) on Jul 12, 2001 at 21:31 UTC

Note that all bigOh run time complexities are in numbers of elementary operations.
If you really want to get down to the brass tacks, a computer scientist is going to define "elementary operations" in terms of a Turing machine (or something equivalent). Since a Turing machine has a finite number of states and symbols available, it can only push a finite number of bits around at once. Multiplying two nbit numbers together is an O(n**2) operation using the algorithm they taught you in grade school. It can be done in O(n*log(n)) with FFT techniques.
 [reply] 

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
 [reply] 

Good point. Turing machines can do any polynomialtime 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.
 [reply] 



Re: Re: about Coolness, Impatience and Complexity
by runrig (Abbot) on Jul 15, 2001 at 21:20 UTC

Cool, I never actually realized that about Q::S, having only
read bits of code using it and not actually reading much about it.
So this means sorting could be an O(N) operation (not necessarily
using Q::S, but maybe Quantum::Sort??).  [reply] 

