Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses
 
PerlMonks  

Re: about Coolness, Impatience and Complexity

by Abigail (Deacon)
on Jul 12, 2001 at 18:34 UTC ( #96047=note: print w/ replies, xml ) Need Help??


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 big-Oh 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


Comment on Re: about Coolness, Impatience and Complexity
Select or Download Code
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!
      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
      (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
Re: Re: about Coolness, Impatience and Complexity
by no_slogan (Deacon) on Jul 12, 2001 at 21:31 UTC
    Note that all big-Oh 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 n-bit 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.
      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.

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??).

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://96047]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (6)
As of 2014-07-30 23:51 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (241 votes), past polls