The Museum of HP Calculators

HP Forum Archive 16

[ Return to Index | Top of Index ]

Speed Comparison
Message #1 Posted by Xerxes on 29 Jan 2007, 1:32 p.m.

I am working on a calculator benchmark to test the speed of the programming language and not the mathematical functions. The program searches a position for 8 queens on a chessboard without attackting each other by brute force. I have many results for Casio and Sharp calculators but only one HP. Can somebody please test it on a HP-71B or a HP-75C/D? Of course results of other calculators are welcome.

5 CLEAR
10 R=8
20 REM DIM A(R)
30 S=0
40 X=1
50 A(X)=R
60 IF X=R THEN 200
70 X=X+1
80 A(X)=R
90 S=S+1
100 Y=X
110 Y=Y-1
120 IF Y=0 THEN 60
130 T=A(X)-A(Y)
140 IF T=0 THEN 160
150 IF X-Y<>ABS(T) THEN 110
160 A(X)=A(X)-1
170 IF A(X)<>0 THEN 90
180 X=X-1
190 IF X<>0 THEN 160
200 PRINT S
210 BEEP 1

On some calculators you can use the variables A-Z as an array a[], so the DIM command in line 20 is not necessary then. The result for S should be 875 if the program runs correctly.

The version for the HP-41CV:

LBL_A
CLX STO_11
8 STO_12 STO_01
1 STO_00
LBL_00
RCL_00 RCL_12
X=Y? GTO_04
ISG_00 DEG
STO_IND_00
LBL_01
ISG_11 DEG
RCL_00 STO_10
LBL_02
DSE_10 DEG
RCL_10 X=0? GTO_00
RCL_IND_00 RCL_IND_10 -
X=0? GTO_03
ABS RCL_10 + RCL_00 -
X<>0? GTO_02
LBL_03
DSE_IND_00 GTO_01
DSE_00 GTO_03
LBL_04
RCL_11
BEEP

The HP-41CV takes 1120 sec for this program. I guess the HP-71/75 are much faster.

If somebody wants to test it on FX-602P:

AC Min1F
8 MinF Min01
1 Min00
LBL0
MR00 x=F GOTO4
ISZ
MRF IND Min00
LBL1
1 M+1F
MR00 Min10
LBL2
1 M-10
MR10 x=0 GOTO0
IND MR00 - IND MR10 =
x=0 GOTO3
ABS + MR10 - MR00 =
x=0 GOTO3 GOTO2
LBL3
IND DSZ GOTO1
DSZ GOTO3
LBL4
MR1F

FX-603P : 165 sec

FX-603P [turbo 2.0]: 82.9 sec

Edited: 31 Jan 2007, 12:47 p.m. after one or more responses were posted

      
Re: Speed Comparison
Message #2 Posted by gileno on 29 Jan 2007, 1:49 p.m.,
in response to message #1 by Xerxes

75C Version aaaaaa - 47 sec 75D Version aaaaaa - 44 sec 75D Version dddddd - 32 sec HP41CY (TURBO ON) - 520 sec hp41CY (TURBO OFF) - 1080 sec PC1600 - 110 sec

Edited: 2 Feb 2007, 5:57 p.m. after one or more responses were posted

            
Re: Speed Comparison
Message #3 Posted by Xerxes on 29 Jan 2007, 2:48 p.m.,
in response to message #2 by gileno

Thank you for testing, but what is the HP-41CY exactly? Simply a faster 41CX?

                  
Re: Speed Comparison
Message #4 Posted by gileno on 29 Jan 2007, 2:53 p.m.,
in response to message #3 by Xerxes

"Message #3 Posted by Raymond Del Tondo on 3 June 2003, 6:11 a.m., in response to message #2 by Gene

Hello Gene,

an HP-41CY is an upgraded HP-41CX. These were only available from W&W Software Products.

It has the 'Turbo' switch, of course, which nearly doubles it's CPU clock speed.

But the most important fact: It has a 64K RAM box built-in.

And about stability: Many years ago I helped making some Baustatik (civil engineering?) programs especially for the HP-41CY. Some of the programs forced bank switching to call routines from the other 32K block, and vice versa.

The machines and programs worked very well, and very stable.

Regards,

Raymond"

      
Re: Speed Comparison
Message #5 Posted by John Pierce on 29 Jan 2007, 2:17 p.m.,
in response to message #1 by Xerxes

HP-71B Version 2CDCC 153 seconds

            
Re: Speed Comparison
Message #6 Posted by Maximilian Hohmann on 30 Jan 2007, 12:28 p.m.,
in response to message #5 by John Pierce

Hello!

Quote:
HP-71B Version 2CDCC 153 seconds

My HP-71B Version 1BBBB: exactly the same - 153 seconds.

For comparison: Ti Voyage 200: 106 Seconds.

Hard to believe that there are 20 years between the two! (but then, the Ti Voyage's Basic dialect is not really happy with "goto" and "lbl" statements I think, a more structured programm should run a lot faster).

Greetings, Max

                  
Re: Speed Comparison
Message #7 Posted by Garth Wilson on 30 Jan 2007, 4:25 p.m.,
in response to message #6 by Maximilian Hohmann

Quote:
(but then, the Ti Voyage's Basic dialect is not really happy with "goto" and "lbl" statements I think, a more structured programm should run a lot faster).
Benchmarks are not very useful if the program is not optimized for each machine in question. Even if they are optimized, the benchmark would only be good for the particular application and may ignore a machine's strengths in other areas. I've forgotten the details now, but I remember reading in one of the electronics trade industry magazines maybe ten or fifteen years ago that someone was trying to put together a more universal microprocessor benchmark. So they got the manufacturers together and began discussing, but there was too much disagreement between manufacturers to be able to make any progress. Each insisted on methods that would give their own products the advantage. The proof of the pudding of course is how well it does what you want it to do.
                        
Re: Speed Comparison
Message #8 Posted by Xerxes on 30 Jan 2007, 5:45 p.m.,
in response to message #7 by Garth Wilson

Sure, there cannot be an overall benchmark. But most calculator benchmarks in the net are tests like an empty loop, that is really not very convincing. Other tests are often only for special mathematical problems or only a few calculators are tested.

In this test only basic programming elements are used to not be specialized in a language and to have an approximately idea of the speed of the programming language.

                  
Re: Speed Comparison
Message #9 Posted by Xerxes on 30 Jan 2007, 5:23 p.m.,
in response to message #6 by Maximilian Hohmann

I have compared on some calculators the difference between goto and strutured jumps. The timings are very close to each other. It is known, that the TI Formula Language is not very fast cosidering the CPU.

Here is the version for the older Casio graphical calculators. I guess the Casio Formula Language is very similar to TI-Basic.

8->R
0->S
1->X
R->A[X]
Lbl 0
X=R=>Goto 4
Isz X
R->A[X]
Lbl 1
Isz S
X->Y
Lbl 2
Dsz Y
Deg
Y=0=>Goto 0
A[X]-A[Y]->T
T=0=>Goto 3
X-Y<>Abs T=>Goto 2
Lbl3
Dsz A[X]
Goto 1
Dsz X
Goto 3
Lbl 4
S

FX-4500PA: 1220 sec

FX-5800P: 234 sec

FX-7500G : 95.8 sec

FX-7500G [turbo 3.3] : 29.0 sec

FX-9860G : 21.3 sec

Edited: 30 Jan 2007, 8:19 p.m.

                        
Re: Speed Comparison
Message #10 Posted by Palmer O. Hanson, Jr. on 1 Feb 2007, 10:46 p.m.,
in response to message #9 by Xerxes

Your results for some early Casios:

Quote:

FX-4500PA: 1220 sec

FX-5800P: 234 sec

FX-7500G : 95.8 sec

FX-7500G [turbo 3.3] : 29.0 sec

FX-9860G : 21.3 sec


My fx7000G does your program in 127 seconds.

I tried to do your program on my Durabrand 828 -- the Wal-mart twenty dollar graphing calculator with a programming language very similar to the fx7000G. It won't do a Dsz A[X] as in liine 20 of your program. If I synthesize an equivalent the 828 does the calculation in 92 seconds. If I do the same substitution for Dsz A[X] on my fx7000G it does the problem in 141 seconds.

                              
Re: Speed Comparison
Message #11 Posted by Xerxes on 2 Feb 2007, 10:30 a.m.,
in response to message #10 by Palmer O. Hanson, Jr.

It is a bit strange to me, that the Durabrand is faster than the TI-V200 with a 68000 @ 10 MHz. Of course TI-Basic is more powerfull, but this cannot be the explanation.

There is a problem in general. For an example look at the version for the FX-9860GSD:

8->R
{R,1}->Dim Mat A
0->S
1->X
R->Mat A[X,1]
Lbl 0
X=R=>Goto 4
Isz X
R->Mat A[X,1]
Lbl 1
Isz S
X->Y
Lbl 2
Dsz Y
Deg
Y=0=>Goto 0
Mat A[X,1]-Mat A[Y,1]->T
T=0=>Goto 3
X-Y<>Abs T=>Goto 2
Lbl 3
Mat A[X,1]-1->Mat A[X,1]
Mat A[X,1]<>0=>Goto 1
Dsz X
Goto 3
Lbl 4
S

As you can see, the newer Casio graphic calculators do not support arrays any more. So you have to use a matrix (faster) or a list (slower) instead, but both ways are slower than using arrays. So it is very difficult to have an algorithm that considerates all the different dialects. In spite of this drawback, the FX-9860GSD is ralatively fast.

Edited: 2 Feb 2007, 10:32 a.m.

                                    
Re: Speed Comparison
Message #12 Posted by Palmer O. Hanson, Jr. on 3 Feb 2007, 3:06 a.m.,
in response to message #11 by Xerxes

Quote:
It is a bit strange to me, that the Durabrand is faster than the TI-V200 with a 68000 @ 10 MHz. Of course TI-Basic is more powerfull, but this cannot be the explanation.

I am still not sure just what to make of the 828; for example, while many pages of the manual have EXACTLY the same information as in the fx-7000G manual, other pages are close to the material in the fx-7000G manual but some errors have crept in. Furthermore, the errors in the ditsy little manual that comes with the device (really hard for these 78 year old eyes to read) are different from the errors in the on-line version of the manual. Even so, I have been able to squeeze a sixth order linear equation solver onto the device.

                                          
Re: Speed Comparison
Message #13 Posted by Xerxes on 3 Feb 2007, 5:05 a.m.,
in response to message #12 by Palmer O. Hanson, Jr.

Do not missunderstand me. What is strange to me is the speed of the TI-V200. I have heared about the slow programming language, but it is slower as I expected.

      
Re: Speed Comparison
Message #14 Posted by Chris Roccati on 29 Jan 2007, 4:00 p.m.,
in response to message #1 by Xerxes

SHARP PC-1248 172 sec
SHARP PC-1261 441 sec
PSION ORGANISER II XP 62 sec

The ORGANISER II XP does not use basic, but a structured language called OPL, so the program was translated; no effort was made to un-spaghettize the code:

BENCH:
LOCAL a(8),r,s,t,x,y

r=8 s=0 x=1 a(x)=r

l60:: IF x=r GOTO l200:: ENDIF x=x+1 a(x)=r

l90:: s=s+1 y=x

l110:: y=y-1 IF y=0 GOTO l60:: ENDIF t=a(x)-a(y) IF t=0 GOTO l160:: ENDIF IF (x-y)<>ABS(T) GOTO l110:: ENDIF

l160:: a(x)=a(x)-1 IF a(x)<>0 GOTO l90:: ENDIF x=x-1 IF X<>0 GOTO l160:: ENDIF

l200: PRINT s BEEP 1000,40 PAUSE 0

The code, changed to use integer-only math (basically appending '%' to every variable name), runs in less than 10 seconds.

            
Re: Speed Comparison
Message #15 Posted by Xerxes on 29 Jan 2007, 4:26 p.m.,
in response to message #14 by Chris Roccati

Very interesting. Can you please run your program with intergers for example 10 times in a loop, to have an more accurate timing. I try to stop the time as exact as possible, mostly with 3 significant digits, because some calculators are very near to each other in ranking. In consideration of the reaction time of hand-stopped results, i subtract 0.2 sec, to have an accurate benchmark table. In the table are about 40 results till now. As soon as i have finished it, i will post it here. Thank you all for testing.

The spaghetti-code is the result of having an algorithm usable in nearly all calculator programming languages, that can be very poor sometimes. ;-)

Edited: 29 Jan 2007, 4:40 p.m.

                  
Re: Speed Comparison
Message #16 Posted by Chris Roccati on 30 Jan 2007, 8:38 a.m.,
in response to message #15 by Xerxes

I timed the integer version of the code, encased in a 100 times DO .. UNTIL loop (OPL does not have a FOR equivalent: apparently, the designer thought it was useless syntactic sugar)...

IBENCH:
LOCAL a%(8),r%,s%,t%,x%,y%
LOCAL n%

n%=100 DO r%=8 s%=0 x%=1 a%(x%)=r%

l60:: IF x%=r% GOTO l200:: ENDIF x%=x%+1 a%(x%)=r%

l90:: s%=s%+1 y%=x%

l110:: y%=y%-1 IF y%=0 GOTO l60:: ENDIF t%=a%(x%)-a%(y%) IF t%=0 GOTO l160:: ENDIF IF (x%-y%)<>IABS(t%) GOTO l110:: ENDIF

l160:: a%(x%)=a%(x%)-1 IF a%(x%)<>0 GOTO l90:: ENDIF x%=x%-1 IF x%<>0 GOTO l160:: ENDIF

l200: n%=n%-1 UNTIL n%=0

PRINT s% BEEP 1000,40 PAUSE 0

I've also timed an empty loop:

ELOOP:
LOCAL n%

n%=100 DO n%=n%-1 UNTIL n%=0 BEEP 1000,40

Benchmark loop 16:21.8 sec
Then empty loop takes almost nothing, I'd say 0:0.2 sec

A single iteration of the benchmark would be (981.8-0.2)/100 ~ 9.82 sec

      
Re: Speed Comparison
Message #17 Posted by Marcus von Cube, Germany on 30 Jan 2007, 3:19 a.m.,
in response to message #1 by Xerxes

Here is the result for the TI-74 BASICALC:

2 minutes 19 seconds = 139 seconds.

It can't be convinced to just use integers but it still seems to be reasonably fast.

Edited: 30 Jan 2007, 3:22 a.m.

            
Re: Speed Comparison
Message #18 Posted by Xerxes on 30 Jan 2007, 6:26 a.m.,
in response to message #17 by Marcus von Cube, Germany

The main reason for the higher speed of the Psion is, that OPL compiles the source to bytecode and then a bytecode-interpreter executes the program.

I am not sure, but I do not think that there is a basic calculator that supports integer variables.

                  
Re: Speed Comparison - HP 71, 75, 85
Message #19 Posted by J-F Garnier on 30 Jan 2007, 3:09 p.m.,
in response to message #18 by Xerxes

Actually, the HP-75 provides a feature called "Fast Integer Processing" that speeds up calculations on integers.

Consider the following test code:

10 !
20 T=TIME
30 X=1
40 FOR I=X TO 1000 @ NEXT I
50 DISP TIME-T

HP-71B: 9.2s HP-75D: 2.4s

If line 30 is changed to 30 X=0.99, results are: HP-71B: 9.2s (same) HP-75D: 5.6s

It explains why the HP-75 is often reported as much faster than the HP-71B. The other reason of speed difference is of couse that the HP-75 uses a 8-bit CPU, and the HP-71B a 4-bit one.

The Fast Integer Processing comes from the HP-85, and is described in the HP Journal, July 1980, page 30 (available on the Museum DVD ROM).

It's a shame that the same feature was not included in the HP-71B!

J-F

                        
Re: Speed Comparison - HP 71, 75, 85
Message #20 Posted by Xerxes on 30 Jan 2007, 5:55 p.m.,
in response to message #19 by J-F Garnier

Really interesting. I was surprised of the outstanding speed of the HP-75. A very good idea of HP.

      
Re: Speed Comparison - Radio Shack Model 100
Message #21 Posted by Palmer O. Hanson, Jr. on 30 Jan 2007, 11:05 p.m.,
in response to message #1 by Xerxes

My old Model 100 does your problem in 71 seconds. If I add a DEFINT A-Z line to run it in integer mode the execution time is reduced to 57 seconds.

            
More on the Radio Shack Model 100
Message #22 Posted by Palmer O. Hanson, Jr. on 31 Jan 2007, 11:12 p.m.,
in response to message #21 by Palmer O. Hanson, Jr.

Quote:
My old Model 100 does your problem in 71 seconds. If I add a DEFINT A-Z line to run it in integer mode the execution time is reduced to 57 seconds.

The Model 100 runs in double precision (14 digits) in the default mode. A user can run in single precision (6 digits) by entering a DEFSNG A-Z line. If I do that instead of using DEFINT A-Z the execution time is 67 seconds. If I include both a DEFINT A-Z and a DEFSNG A-Z line the execution time is 57 seconds, the same as with DEFINT A-Z alone.

                  
Re: More on the Radio Shack Model 100
Message #23 Posted by Marcus von Cube, Germany on 1 Feb 2007, 2:21 a.m.,
in response to message #22 by Palmer O. Hanson, Jr.

Quote:
If I include both a DEFINT A-Z and a DEFSNG A-Z line the execution time is 57 seconds, the same as with DEFINT A-Z alone
What do you expect? The commands define all variables starting with a letter from A to Z, i. e. all of them, to be of type single precision or integer, respectively. Only one of them can be in effect. I assume the second but the interpreter might take the first definition and ignore the second, conflicting one.

Marcus

      
What exactly does this comparison program do?
Message #24 Posted by John on 2 Feb 2007, 10:57 a.m.,
in response to message #1 by Xerxes

What does the sum 875 represent?

            
Re: What exactly does this comparison program do?
Message #25 Posted by Xerxes on 2 Feb 2007, 1:02 p.m.,
in response to message #24 by John

The variable S counts the positions generated till the solution is found. It is only for having a quick way to see, if the program runs correctly. Of course in A[] you can look at the solution and you can use for R any dimension from 1 upwards.

Note that this program is only for benchmarking. There are much better algorithms to solve the N-Queens-Problem, but many calculators are too limited to execute them.

      
Re: Speed Comparison
Message #26 Posted by Albert Graef on 2 Feb 2007, 1:13 p.m.,
in response to message #1 by Xerxes

HP 32s: 266 secs

Program in ASCII format: 8queens.32s

This is more or less a literal translation of your Basic program, so not optimal for the device. I could have started from the 41CV program, but I was too lazy to fiddle around with that to make it work with the 32s, which only has a single index register. I guess it's been some 10 years since I've done any non-trivial keystroke programming, so I totally forgot how clumsy that is, but it was still quite fun for a change. ;-)

I'd say that for a calculator of its age and capabilities, the 32s is blazingly fast (reportedly it also beats the 32sii and the 42s hands down in that respect).

            
Re: Speed Comparison
Message #27 Posted by Gerson W. Barbosa on 2 Feb 2007, 8:50 p.m.,
in response to message #26 by Albert Graef

HP-33S: 251 seconds

Not bad, considering there are 12 additional instructions compared to the original HP-41 program. Also, the battery annunciator was blinking when running the program. I don't know how this might have affected the performance.

Regards,

Gerson.

LBL A CLX STO L 8 STO M STO B 1 STO A LBL B RCL A RCL M X=Y? GTO F ISG A DEG 1 RCL+ A STO i Rv STO(i) ; STO IND A LBL C ISG L DEG RCL A STO K LBL D DSE K DEG RCL K X=0? GTO B 1 RCL+ A STO i Rv RCL(i) ; RCL IND A 1 RCL+ K STO i Rv RCL(i) ; RCL IND K - X=0? GTO E ABS RCL K + RCL A - X<>0? GTO D LBL E 1 RCL+ A STO i Rv DSE(i) ; DSE IND A GTO C DSE A GTO E LBL F RCL L RTN

LBL LN CK A 48 E17C B 48 170E C 15 46BD D 102 0DA8 E 39 4A43 F 9 F89E

                  
Re: Speed Comparison
Message #28 Posted by Gerson W. Barbosa on 2 Feb 2007, 9:38 p.m.,
in response to message #27 by Gerson W. Barbosa

HP-32SII: 388 seconds

LBL  LN   CK
 A 012.0 CFF4
 B 018.0 7663
 C 007.5 637A
 D 039.0 255F
 E 013.5 0989
 F 004.5 B4C7

Probably more than 300 seconds on the HP-32S, which means Albert Graef's program is better suited for these calculators. This is just a straightforward adaptation of the original HP-41 program.

                        
Re: Speed Comparison
Message #29 Posted by Albert Graef on 3 Feb 2007, 4:28 a.m.,
in response to message #28 by Gerson W. Barbosa

Quote:
Probably more than 300 seconds on the HP-32S, which means Albert Graef's program is better suited for these calculators.

Yep, 299 secs on the 32s. Those ISG and DSE instructions seem to be quite expensive. You'd also want to avoid the recall arithmetic when addressing the position array (let the array start at 'A' and store the index in another variable). That would essentially give you my program.

                              
Re: Speed Comparison
Message #30 Posted by Gerson W. Barbosa on 3 Feb 2007, 6:25 a.m.,
in response to message #29 by Albert Graef

Quote:
You'd also want to avoid the recall arithmetic when addressing the position array (let the array start at 'A' and store the index in another variable). That would essentially give you my program.

I only copied the original 41 program and pasted it to Notepad and reformatted it to one step a line. Then I changed 0, 1, 10, 11 and 12 to A, B, K, L and M, respectively. What you have suggested should have been my next step if I were willing to think :-)

Regards,

Gerson.

                                    
Re: Speed Comparison
Message #31 Posted by Albert Graef on 3 Feb 2007, 7:04 a.m.,
in response to message #30 by Gerson W. Barbosa

Quote:
I only copied the original 41 program and pasted it to Notepad and reformatted it to one step a line. Then I changed 0, 1, 10, 11 and 12 to A, B, K, L and M, respectively. What you have suggested should have been my next step if I were willing to think :-)

I was even lazier! Taking a look at the 41 program, I decided that translating the numeric register addresses to letters was too much brain work. :)

Best, Albert

                                          
Re: Speed Comparison
Message #32 Posted by Gerson W. Barbosa on 3 Feb 2007, 9:23 a.m.,
in response to message #31 by Albert Graef

Quote:
I was even lazier!

Hello, Albert!

I think you can't beat me on this. I didn't even try to understand the algorithm! :-)

I am sure your version will perform better on the HP-15C than the direct conversion below. 5104 seconds! (Sorry, only one measurement).

Best regards,

Gerson.

---------------

001- LBL_A 002- CLX STO_.1 004- 8 STO_.2 STO_1 007- 1 STO_0 009- LBL_0 010- RCL_0 RCL_.2 012- TEST_5 GTO_4 014- ISG_0 DEG 016- RCL_0 STO_I Rv STO_(i) 020- LBL_1 021- ISG_.1 DEG 023- RCL_0 STO_.0 025- LBL_2 026- DSE_.0 DEG 028- RCL_.0 X=0? GTO_0 031- RCL_0 STO_I Rv RCL_(i) RCL_.0 STO_I Rv RCL_(i) - 040- X=0? GTO_3 042- ABS RCL_.0 + RCL_0 - 047- TEST_0 GTO_2 049- LBL_3 050- RCL_0 STO_I Rv DSE_(i) GTO_1 055- DSE_0 GTO_3 057- LBL_4 058- RCL_.1 059- RTN

Edited: 3 Feb 2007, 9:25 a.m.

                                                
Re: Speed Comparison
Message #33 Posted by Albert Graef on 3 Feb 2007, 11:59 a.m.,
in response to message #32 by Gerson W. Barbosa

Hi Gerson,

Quote:
I think you can't beat me on this. I didn't even try to understand the algorithm! :-)

LOL, ok I'll let you have that crown.

Quote:
I am sure your version will perform better on the HP-15C than the direct conversion below. 5104 seconds! (Sorry, only one measurement).

I'd say that you'll have to run that at least 100 times in a loop to get an accurate result. 8-)

Seriously, 5104 is pretty good given that the 15c is so much slower than the 32s. It's a shame that HP doesn't sell a Kinpo remake of that one, it's a darn nice calculator, I might actually be tempted to buy one.

Albert

                              
Re: Speed Comparison
Message #34 Posted by Xerxes on 5 Feb 2007, 7:36 p.m.,
in response to message #29 by Albert Graef

On the HP-41C it is faster to use DSE and ISG instead of 1 STO+ or STO-.

            
Re: Speed Comparison
Message #35 Posted by Albert Graef on 3 Feb 2007, 4:48 a.m.,
in response to message #26 by Albert Graef

Correction:

HP 32s: 262 secs

This is the average of three runs (260.32, 261.75, 262.78). I don't know where the figure of 266 secs in my original post came from, probably a typo. So it fares quite well in comparison to the 33s. In fact, I'm somewhat surprised by the (lack of) speed of the 33s, given that the 32s is almost 20 years old...

      
Re: Speed Comparison
Message #36 Posted by Albert Graef on 2 Feb 2007, 1:50 p.m.,
in response to message #1 by Xerxes

HP 50g: 108 secs

RPL program in ASCII format: 8queens.rpl

This is also a simple knockoff of the Basic program, but of course there are no GOTOs in RPL, so it is a bit more structured.

Below is a rather more elegant recursive solution, which uses some of the advanced list processing functions of the GoferLists library. It enumerates the solutions in a different order, but takes essentially the same number of iterations, and runs much quicker: 81 secs.

Queens: @ assumes size of board N is on the stack
\<< { } Search \>>

Search: @ the backtracking algorithm \<< \-> N B \<< IF B Length N \>= THEN B ELSE 1. N 1. Seq NOVAL \<< \-> C Y \<< IF C NOVAL \=/ THEN C ELSE IF B Y Safe THEN N Y B + Search ELSE NOVAL END END \>> \>> Foldl END \>> \>>

Safe: @ check whether a given position is safe w.r.t. an existing board \<< 0. \-> Y1 X \<< \<< \-> Y2 \<< Y1 Y2 \=/ Y1 Y2 - ABS 'X' INCR \=/ AND \>> \>> All \>> \>>

You can find these programs in ASCII format here or as a binary file ready to be transferred to the calculator here.

            
Re: Speed Comparison
Message #37 Posted by Xerxes on 2 Feb 2007, 2:35 p.m.,
in response to message #36 by Albert Graef

Is it correct to say, that 8queens.rpl does the same as Basic? Does the secound program the same, but recursive?

If somebody wants to run the program under C for example on a TI-89 or HP-48/49/50:

main(){
    int x,y,r,s,t,a[9];
    r=8;
    s=0;
    x=1;
    a[x]=r;
l0: if(x==r)goto l4;
    a[++x]=r;
l1: ++s;
    y=x;
l2: if(--y==0)goto l0;
    if((t=a[x]-a[y])==0)goto l3;
    if(x-y!=abs(t))goto l2;
l3: if(--a[x])goto l1;
    if(--x)goto l3;
l4: printf("%d",s);
    beep(1);}

It could be necessary to use a loop for repeating the test for a more accurate timing.

                  
Re: Speed Comparison
Message #38 Posted by Albert Graef on 2 Feb 2007, 5:51 p.m.,
in response to message #37 by Xerxes

Is it correct to say, that 8queens.rpl does the same as Basic?

Yes, the algorithm is exactly the same, down to the variable names. The position array is implemented as a list, though, and the conditional branches were replaced by nested WHILE REPEAT loops.

Does the secound program the same, but recursive?

Yes, but it enumerates positions starting at 1, rather than counting down starting at the board size. But that doesn't really matter much, as solutions remain valid under reflection.

                        
Re: Speed Comparison
Message #39 Posted by Xerxes on 2 Feb 2007, 8:04 p.m.,
in response to message #38 by Albert Graef

Good work. I guess it is not so easy to make a version in RPL with the same algorithm. I will place both versions as iterative and recursive in the table.

The reason of counting down in the program is, that for most keystroke calculators it is more easy to compare a register to zero.

                              
Re: Speed Comparison
Message #40 Posted by Albert Graef on 3 Feb 2007, 5:01 a.m.,
in response to message #39 by Xerxes

Quote:
Good work. I guess it is not so easy to make a version in RPL with the same algorithm. I will place both versions as iterative and recursive in the table.

Well, it's just the standard backtracking algorithm for this problem, so that was fairly straightforward after all. What surprised me is that the recursive version runs so fast, despite the extra function call and list manipulation overhead. The RPL system seems to be optimized fairly well for that kind of usage.

Quote:
The reason of counting down in the program is, that for most keystroke calculators it is more easy to compare a register to zero.

Yes, in bygone days I've programmed enough calcs with only a decrement and skip on zero looping facility, so I understand that issue very well. ;-)

                              
Re: Speed Comparison
Message #41 Posted by Albert Graef on 3 Feb 2007, 5:10 a.m.,
in response to message #39 by Xerxes

NB: As I mentioned, the recursive version does use some non-builtin operations from the GoferLists library. However, these operations are in fact just frontends for builtins like STREAM, so pretty much the same figures should be achievable with the builtin ops of the calc alone.

                  
Re: Speed Comparison
Message #42 Posted by Marcus von Cube, Germany on 3 Feb 2007, 9:04 a.m.,
in response to message #37 by Xerxes

I entered the C programm into my Casio PB-2000C. It runs interpreted C and isn't the fastest: 572 seconds.

The same programm running on a Casio Z-1GR with the same interpreter but on a faster 16 bit CPU takes just 14.3 seconds.

Marcus

Edited: 3 Feb 2007, 9:19 a.m.

                        
Re: Speed Comparison
Message #43 Posted by Xerxes on 4 Feb 2007, 7:27 p.m.,
in response to message #42 by Marcus von Cube, Germany

I have tested the Z-1GRA. This is the latest version of the FX-890P with a high contrast display.

    ORG 2000H
    MOV CX,1000   ;repetitiones for timing
L6: MOV DX,8
    LEA BX,ARY
    MOV WORD PTR CNT,0
    MOV SI,1
    MOV [BX+SI],DL
L0: CMP DX,SI
    JZ  L5
    INC SI
    MOV [BX+SI],DL
L1: INC WORD PTR CNT
    MOV DI,SI
L2: DEC DI
    JZ  L0
    MOV AL,[BX+SI]
    SUB AL,[BX+DI]
    JZ  L4
    JNC L3
    NEG AL
L3: XOR AH,AH
    ADD AX,DI
    SUB AX,SI
    JNZ L2
L4: DEC BYTE PTR [BX+SI]
    JNZ L1
    DEC SI
    JNZ L4
L5: LOOP L6
    IRET
CNT DW 0
ARY DB 32 DUP (?)
    END

The Assembler version have to be called from Basic or C with CALL &H2000 after assembling the source. To be sure for the right segment use DEFSEG=0 before calling.

Basic : 58.6 sec

C: 14.0 sec (First use LOAD and the timing begins with RUN)

Assembler: 0.0753 sec (80L188EB @ 3.68 MHz)

      
Re: Speed Comparison
Message #44 Posted by Marcus von Cube, Germany on 3 Feb 2007, 9:32 a.m.,
in response to message #1 by Xerxes

Casio Z-1GR: 59 seconds (BASIC mode)

      
Re: Speed Comparison
Message #45 Posted by Gerson W. Barbosa on 3 Feb 2007, 6:25 p.m.,
in response to message #1 by Xerxes

I wonder why the HP-42S hadn't been tested yet, as your HP-41 program is fully compatible with it. Anyway, here is the result: 806 seconds.

Regards,

Gerson.

            
Re: Speed Comparison
Message #46 Posted by Gene on 3 Feb 2007, 6:42 p.m.,
in response to message #45 by Gerson W. Barbosa

And the 42s would be around 400 seconds in FAST MODE.

Gene

http://www.rskey.org/gene/hpgene/hp42fast.htm

                  
Re: Speed Comparison
Message #47 Posted by Gerson W. Barbosa on 3 Feb 2007, 6:55 p.m.,
in response to message #46 by Gene

Yes, I have already tried the fast mode on my 42S, following your instructions. Too bad mine doesn't allow the programatic fast mode :-(

I think it would be fair to declare 403 second in fast mode without going through that procedure. Anyway, I might try it later and post the actual result.

Regards,

Gerson.

                  
Re: Speed Comparison
Message #48 Posted by Gerson W. Barbosa on 3 Feb 2007, 9:03 p.m.,
in response to message #46 by Gene

Quote:
And the 42s would be around 400 seconds in FAST MODE

400 seconds! (Stop-watch readout: 06'39.55)

Gerson


[ Return to Index | Top of Index ]

Go back to the main exhibit hall