(EL-5120) N-Queens Benchmark

[Dave Britten]

The Sharp EL-5120 is a pleasant, though in some ways underwhelming calculator. About the size of an HP Pioneer, and similar in functions to a 32S/32SII, it's equipped with a three-line display of dot-matrix characters, and roughly 1 KB of RAM. It has solve and integrate functions, and can store a list of equations for later use. Interestingly, it allows for two-character letter+number local variables in equations and programs. However, this machine is quite wasteful with its memory, so that 1 KB doesn't get you too much further than the 384 bytes of a 32SII (which was already pretty wasteful with its 1.5-byte program steps). At least you get a lot more labels to use, and you can GOTO or GOSUB to local labels within a program, but you can't have one program call another.

The EL-5120 is programmable in a simple BASIC-like language that's very similar to that of Sharp's graphing calculators, but entirely lacking in any sort of indirect addressing capability. This rules out the possibility of running the N-Queens solver algorithm, right? Wrong! The "chopping block" algorithm from "Mathematical Recreations for the Programmable Calculator" (which I previously crammed into the HP 65) requires no indirect addressing, and needs only 5 or 6 memories to find solutions on a board up to 9x9.

Below is the listing for NQUEENS, which probably doesn't need too much explanation. Functions like IPART, FPART, ABS, IF, GOTO, and PRINT all function exactly like you would expect them to, and variable assignments take the form A=0, E=E+1, etc. Run the program, type in the board size (e.g. 8 for 8x8), and press ENTER to start solving. The program produces a solution for an 8x8 board in about 4m27s. You can press ENTER to start looking for another solution, or press QUIT or ON to stop the program.

Code:

INPUT N
A=0
C=0
LABEL 1
IF A=NGOTO 6
B=1
LABEL 3
D=C
E=0
LABEL 7
E=E+1
IF D=0GOTO 8
D=.1D
X=10FPART D
D=IPART D
IF X=BGOTO 4
IF ABS (X-B)=EGOTO 4
GOTO 7
LABEL 8
C=10C+B
A=A+1
GOTO 1
LABEL 6
PRINT C
WAIT
LABEL 4
IF B=NGOTO 5
B=B+1
GOTO 3
LABEL 5
A=A-1
IF A<0GOTO 9
C=.1C
B=10FPART C
C=IPART C
GOTO 4
LABEL 9
PRINT"DONE
END

[toml_12953]

(02-22-2022 08:11 PM)Dave Britten Wrote:  The Sharp EL-5120 is a pleasant, though in some ways underwhelming calculator. About the size of an HP Pioneer, and similar in functions to a 32S/32SII, it's equipped with a three-line display of dot-matrix characters, and roughly 1 KB of RAM. It has solve and integrate functions, and can store a list of equations for later use. Interestingly, it allows for two-character letter+number local variables in equations and programs. However, this machine is quite wasteful with its memory, so that 1 KB doesn't get you too much further than the 384 bytes of a 32SII (which was already pretty wasteful with its 1.5-byte program steps). At least you get a lot more labels to use, and you can GOTO or GOSUB to local labels within a program, but you can't have one program call another.

The EL-5120 is programmable in a simple BASIC-like language that's very similar to that of Sharp's graphing calculators, but entirely lacking in any sort of indirect addressing capability. This rules out the possibility of running the N-Queens solver algorithm, right? Wrong! The "chopping block" algorithm from "Mathematical Recreations for the Programmable Calculator" (which I previously crammed into the HP 65) requires no indirect addressing, and needs only 5 or 6 memories to find solutions on a board up to 9x9.

Below is the listing for NQUEENS, which probably doesn't need too much explanation. Functions like IPART, FPART, ABS, IF, GOTO, and PRINT all function exactly like you would expect them to, and variable assignments take the form A=0, E=E+1, etc. Run the program, type in the board size (e.g. 8 for 8x8), and press ENTER to start solving. The program produces a solution for an 8x8 board in about 4m27s. You can press ENTER to start looking for another solution, or press QUIT or ON to stop the program.

Code:

INPUT N
A=0
C=0
LABEL 1
IF A=NGOTO 6
B=1
LABEL 3
D=C
E=0
LABEL 7
E=E+1
IF D=0GOTO 8
D=.1D
X=10FPART D
D=IPART D
IF X=BGOTO 4
IF ABS (X-B)=EGOTO 4
GOTO 7
LABEL 8
C=10C+B
A=A+1
GOTO 1
LABEL 6
PRINT C
WAIT
LABEL 4
IF B=NGOTO 5
B=B+1
GOTO 3
LABEL 5
A=A-1
IF A<0GOTO 9
C=.1C
B=10FPART C
C=IPART C
GOTO 4
LABEL 9
PRINT"DONE
END

For those that may not be aware of it, here's the site that compares the nqueens program running on many different calculators/pocket computers:

https://www.hpmuseum.org/cgi-sys/cgiwrap...i?read=700

[Dave Britten]

(02-23-2022 02:49 PM)toml_12953 Wrote:  For those that may not be aware of it, here's the site that compares the nqueens program running on many different calculators/pocket computers:

https://www.hpmuseum.org/cgi-sys/cgiwrap...i?read=700

Good old "Article 700" as I've taken to calling it.

I've been looking through the "Simple test used in case of incapability of executing n-queens" section to see which calculators in there could probably handle this version of the routine. I think these would probably be up to the challenge:

EL-5250
fx-3900P
fc-200
fx-50FH (I think this model lacks Int/Frac functions, so it would be a bit more laborious.)
fx-3650P (Less memory than the fx-50FH, so I'm not certain it would fit. Maybe.)

[xerxes]

Very nice demonstration. Thank you Dave. I didn't noticed the HP-65 version before.

I've tested the speed difference compared to the original algorithm on a FX-7000GA Turbo (1.6->4.0 MHz):
The "chopping block" version needs 60.5 seconds vs 43.8 seconds of the original version.

[Dave Britten]

Interestingly, the difference is much slimmer on the EL-9300C. I'm using all global variables in the program since those are faster than local/lowercase variables in my tests. The chopping-block program found a solution in 4m40s, vs. the 4m38s for the matrix-based version in Article 700 (both tested on the same unit).

I'm not surprised that it's so much slower on the Casio, since Casio's indirect addressing is a lot like in RPN calculators, where you're just giving it an offset from the fixed start of variable memory. This is very efficient, since there's not really any lookup involved - A[0] points to A, A[1] points to B, and so on, and the variables always start at the same address.

However, in calculators like the EL-9300C where you can allocate matrices or lists that potentially end up sitting anywhere in memory, I assume the calculator first has to consult some variable catalog to find the starting address each time the object is referenced, and then use the subscripts to calculate an offset from that address. This extra lookup perhaps diminishes the advantage of using an array to store the individual digits. I'll have to test this on a TI and see how it behaves there. On their graphing calculators, the numeric variables are not fixed in memory like I assume they are on the Sharp (which provides no way to delete them, and doesn't report them in the memory check screen). The list/matrix version may again have a considerable advantage if both algorithms require variable address lookups anyway. It could be the same for later Casios that dropped the array memories and switched to lists and matrices.

[xerxes]

I fully agree, because I made exactly this observation during the tests. A good example ist the TI-81 compared to the other TIs, considering the speed of the CPU.