S&SMC #9, Act II



#7

Valentin wrote:

" ... the number of solutions seems to grow forever that's not the case. Actually, 2492 is the maximum number of solutions for any N (in this case, for N=9 and N=10).
After that (N=11, 12, etc), the number of solutions decreases steadily till N=25, which again has a unique, 25-digit solution".

My personal challenge was then to find this unique solution on the HP-71B (actually using Emu71).
I wrote a program (non-recursive, with no GOSUB) that solves the problem in less that 40 seconds with Emu71 in Fast mode.
I will post my solution in a few days to let you play with this challenge, if you like it.

J-F

Note: Emu71 Fast mode is just Emu71 with /fx option,

e.g. "Emu71 /f50" with a 1.7GHz processor, or even "Emu71 /f80" with a 2.3GHz processor (close to a virtual Saturn running at 80MHz...).


#8

Hi, Jean-François:

J-F posted:

"Note: Emu71 Fast mode is just Emu71 with /fx option,
e.g. "Emu71 /f50" with a 1.7GHz processor, or even "Emu71 /f80" with a 2.3GHz processor (close to a virtual Saturn running at
80MHz...)."

I didn't know that you could use a number after the "/f", I was using just "Emu71 /f", per se, no number after.

What does this number mean and how can you deduce its optimum value for a given processor and/or processor speed ?

As for your "personal challenge", that was my intention when mentioning that 25-digits had just an unique solution, that someone would "take the bait" and would decide to try and find that solution. I'm glad that you did, and even more that you used Emu71 to do it, with such good timing.

Best regards from V.


#9

The number after the /f option set the size of the emulated opcode 'burst' before checking keyboard, updating display and timers and so on. As Emu71 is basically a DOS program, these calls to the OS I/O primitives also set the relative CPU usage given by the Windows OS due to the automatic idle detection. Max value is 255, but if you set a too high value, Emu71 realtime clock will not be emulated correctly.

There is no direct relation with the equivalent Saturn frequency, I said that /f80 was close to a 80MHz Saturn, but it's only by chance.

A convenient way to optimize the parameter for a particular machine is to use the CPU usage display (in the Task Manager utility), and to target about 80% CPU usage.

J-F

Valentin: you may notice that the speed-up is not effective in your last challenge solution. This is due to the CALL function, I don't know why right now and I'm working to correct this. That's why I don't use recursive calls in Emu71 for 'force brute' approach. BTW such challenges are very usefull to test emulator behaviors...


#10

Correction:

With /f50 on a 1.7GHz processor the speed-up is actually about x140, measured by the following test program:

240 SUB SPEED
250 ! test emulator speed
260 ! a HP71B needs about 20 s for 2000 iterations
270 N=2000
275 T=TIME
280 FOR I=1 TO N @ NEXT I
290 T=TIME-T @ IF T<2 THEN N=N*2 @ GOTO 275
295 DISP T;"s. SPEED=";IP(N/T)/100;"TIMES HP-71B SPEED"
300 END SUB

J-F


#11

Thanks a lot for the detailed explanation, Jean-François ! :-)

I'm truly glad that you find my challenges useful and interesting. Certainly, were it not for your Emu71 and kind answers to my requests, many of my 71B-related articles and challenges would've never seen the light.

Being able to use Emu71 for development and testing purposes increases productivity a hundredfold, which, with the very little free time I can gather for these activities, is absolutely of the essence.

Best regards from V.

#12

Below is my solution. First, I noticed that to be divisible by 25, a number should end with 00,25,50 or 75 so it is enough to find all the 24-digit solutions. This means that double length arithmeric can be used on Saturn (and Capricorn...) machines (2*12 digits), with only the implementation of MOD, *10 and div10 operations, which is quite easy to do.


10 ! S&SMC #9, Act II
20 ! JFG, May 2005
30 H=24 ! # of digits (24 max)
40 C=0 ! solution counter
50 FOR I=10 TO 98 STEP 2 ! loop for 1st and 2nd digit positions
60 L=3 ! start tests from 3rd position
70 M=I*10 ! lower part of candidate number
80 N=0 ! higher part
90 'A': X=MOD(N*1.E+12,L)+MOD(M,L) @ IF X>=L THEN X=X-L ! x= [n,m] mod L
100 IF X<>0 THEN X=L-X ! find Lth digit
110 IF X>9 THEN 'D' ! is it a possible candidate?
120 M=M+X ! yes, built it.
130 IF L=H THEN C=C+1 @ DISP N;M @ GOTO 'C' ! found one!
140 'B': N=N*10+M DIV 100000000000 @ M=MOD(M,100000000000)*10 ! go on [n,m]*=10
150 L=L+1 @ GOTO 'A'
160 'C': X=X+L @ IF X<=9 THEN M=M+L @ GOTO 'B' ! next try, if possible
170 'D': M=MOD(N,10)*100000000000+M DIV 10 @ N=N DIV 10 ! else [n,m]/=10
180 X=MOD(M,10)
190 L=L-1 @ IF L>2 THEN 'C'
200 NEXT I

The only three 24-digit solutions are:

 144408645048  225636603816 
360852885036 840078603672
402852168072 900828009216
So the unique 25-digit solution is: 3608528850368400786036725.

You can notice that I used a few GOTOs and 4 labels. Actually, I'm a supporter of structured programming style with WHILE/LOOP/REPEAT/etc structures (such as in the HP71 JPCROM), so it can be a challenge to rewrite the program with no explicit GOTO.

Will someone implement this simple but non-trivial algorithm on HP48's RPL for instance?

J-F


#13

Hi J-F,

nice exercise.

For an HP-48 (or generally RPL) solution

I think the runtime structure will have to be rewritten,

as you do jumps into and out of 'loops' in your BASIC program.

My first steps would be maybe reordering

the test logic to omit labels 'C' and 'D',

and in consequence omitting label 'B'.

The following code leaves out some assignments,

and maybe has still some logic error inside,

but it is intended only for showing the principle

how it could be solved completely w/o GOTO;-)


However, it's deep in the night and I'll go to sleep soon...

Regards

Raymond

::  %24 'H' STO %0 'C' STO
NINEYEIGHT TEN
DO
:: %3 'L' STO INDEX@ #10* UNCOERCE 'M' STO %0 'N' STO

* 'A'-Loop:
:: BEGIN
::
* some code
X %9 %> ITE
:: (this seco was label 'D')
L %2 %> (leaves flag on stack for 'C')
TRUE (leaves flag on stack for 'A' test)
;
:: M X %+ 'M' STO
L H %= NOTcaseTRUE ('GOTO C')

C %1+ 'C' STO
FALSE (SKIP C)
FALSE (leaves flag on stack for 'A' test)
;

caseTRUE (leaves flag on stack for 'A': Exit 'A')

ITE
:: (this seco was label 'C')
X %9 %> (leaves flag on stack for 'B')
;
TRUE

?SKIP
:: (this seco was label 'B')
L %1+ 'L' STO
;

FALSE
;
UNTIL
;

INDEX@ #1+ INDEXSTO
;
LOOP
;

#14

Here is my structured programming style solution, using the HP-71B JPCROM:

  10 ! S&SMC #9, Act II
20 ! JFG, May 2005 - with JPCROM
30 H=24 ! # of digits (24 max)
40 C=0 ! solution counter
50 FOR I=10 TO 98 STEP 2 ! loop for 1st and 2nd digit positions
60 L=2 ! start of search
70 M=I ! lower part of candidate number
80 N=0 ! higher part
90 REPEAT
100 REPEAT
110 N=N*10+M DIV 100000000000 @ M=MOD(M,100000000000)*10 ! go on [n,m]*=10
120 L=L+1
130 X=MOD(N*1.E+12,L)+MOD(M,L) @ IF X>=L THEN X=X-L ! x= [n,m] mod L
140 IF X<>0 THEN X=L-X ! find Lth digit
150 IF X<=9 THEN M=M+X ! if possible candidate, build number
160 UNTIL X>9 OR L=H ! until no more possible, or solution reached
170 IF X<=9 AND L=H THEN C=C+1 @ DISP N;M ! found one!
180 REPEAT
190 M=MOD(N,10)*100000000000+M DIV 10 @ N=N DIV 10 ! go back [n,m]/=10
200 X=MOD(M,10)
210 L=L-1
220 X=X+L ! next try
230 UNTIL X<=9 OR L=2 ! until a possible try, or end of search
240 M=M+L
250 UNTIL L=2 ! until end of search
260 NEXT I


The algorithm is now much easier to read and understand, at the expense of some reduntant tests.

Nice exercice, indeed.

J-F


#15

Wonderful lex file.

Gene

#16

Hi, J-F:

Excellent solution to the extended version of my S&SMC#9. Frankly, I didn't expect anyone at all to come up with the unique
25-digit solution but then I wasn't expecting you to try your hand at it, either ! :-)

By the way, despite your titanic effort the topic isn't exhausted yet. What about bases other than 10 ? ;-)

Glad that you enjoyed my challenge, hope to see you attempt the next one as well.

Best regards from V.

#17

Hi J-F,

did you see my last post?

Your today's solution will be even easier to port to RPL;-)

Regards

Raymond


#18

Hi Raymond,

Yes I read your post, this was one reason to me to write a GOTO-less version (the other reason was to demonstrate the JPCROM powerfull features).

But User RPL is good enough for this problem :-)

J-F

Edited: 31 May 2005, 3:25 p.m.


Possibly Related Threads...
Thread Author Replies Views Last Post
  The HP Prime saga - Part II Michael de Estrada 21 2,019 11-30-2013, 01:04 PM
Last Post: Michael de Estrada
  ACT insights davorin 1 374 09-14-2013, 03:51 AM
Last Post: davorin
  HP-32S II Expansion Matt Agajanian 14 1,461 07-21-2013, 10:19 PM
Last Post: Matt Agajanian
  Classpad II fx-CP400 emulator Namir 0 404 07-07-2013, 08:07 AM
Last Post: Namir
  HP 32S-II Vertical Curve Program Ron Cardwell 2 539 05-20-2013, 07:54 AM
Last Post: Thomas Klemm
  ACT CHIP aj04062 5 666 01-27-2013, 02:11 PM
Last Post: Eric Smith
  HP-39g II Acquistion Matt Agajanian 54 4,164 07-21-2012, 02:31 AM
Last Post: Gilles Carpentier
  Closest thing to a 42S-II Matt Agajanian 17 1,662 06-27-2012, 01:00 PM
Last Post: Matt Agajanian
  HP-41CV System II aj04062 1 421 06-22-2012, 08:49 PM
Last Post: Allen
  HP-41's ARCL on the 32S-II Matt Agajanian 2 426 05-04-2012, 04:45 PM
Last Post: Matt Agajanian

Forum Jump: