Re: N-queens benchmark and the HP-17BII
Message #62 Posted by x34 on 2 Feb 2011, 11:53 a.m.,
in response to message #61 by Thomas Klemm
Quote:
Quote:
What happens if the EXPRESSION LIST has side effects? Let's assume it just increments a counter. In the upper FOR-loop it counts the passes until the break-condition is met for the 1st time while in the lower it counts how many passes don't meet the break condition which is not the same.
This could be rewritten to avoid side effects, as you illustrate:
Quote:
However this can be fixed with an additional variable DONE. What we really want to have are expressions before and after the break:
FOR I IN [1..N] DO
EXPRESSION LIST A;
IF (X>0) THEN BREAK; END IF;
EXPRESSION LIST B;
END FOR;
This is equivalent to:
DONE=0
FOR I IN [1..N] DO
IF (DONE==0) THEN
EXPRESSION LIST A;
IF (X>0) THEN
DONE=1
ELSE
EXPRESSION LIST B;
END IF;
END IF;
END FOR;
Absolutely!
[quote[
I'm still not 100% convinced that an endless-loop and a for-loop are equivalent. But you might say that there isn't something as an endless-loop in a finite machine. Or how would you argue?
No. i will not argue. You are right, they are not equivalent in general. But I think it simply does not matter here, because Endloss loop is not a request for Turing-Completeness,so i don't count it as an objection.
BTW, finite machine CAN have an endloss-loop if it is one of the states. Many of them actually have, like a telephone answering machine.
In our case (calculator) if you can make a 1E12 iterations cycle, it would be practically infinite. But actually TWO types of loops should be used - the one with simulated BREAKs would be impractical if near infinite. "Cray is so fast, it can do infinite loop in two seconds!" - it was popular saying in the 80's :)
And your solution of Queens is much faster than could be done with
"emulated" constructions.
Quote:
Best regards and thanks for your interesting contribition
Thomas
Thanks to you!
[pre]
Actually, i have a problem with HP-35S Solver.
What we have on HP-35S is:
a) One external loop, designed by Katie
b) Unlimited IFs
IFs are emulated with 0*((BOOLEAN RESULT) EXPRESSION).
X=0? is equivalent to 1-SGN(ABS(X)) or NOT(SGN(X))
X<Y?==NOT(SGN(Y-X)-1)
X>=Y?==NOT(SGN(X-Y)-1)+NOT(SGN(ABS(X-Y))
and so on.
I could not yet understand, if a lot of "IFs" within eternal loop
could be considered equivalent to GOTO and/or recursion.
I personaly think they are NOT equivalent, however could be used for
small tasks.
In any case, there would be EXTREMELY difficult to write 8 queens in the HP-35S Solver, however possible, even if it is not turing-complete. I will try to write simple compiler or macros to do it, but not soon.
May be someone will find a way to make any kind of iteration (loop) besides the outer one in HP-35S Solver? I hope so.
[pre/]
| 
Go back to the main exhibit hall