▼
Posts: 412
Threads: 40
Joined: Mar 2006
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, 25digit solution".
My personal challenge was then to find this unique solution on the HP71B (actually using Emu71).
I wrote a program (nonrecursive, 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.
JF
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...).
▼
Posts: 1,755
Threads: 112
Joined: Jan 2005
Hi, JeanFrançois:
JF 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 25digits 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.
▼
Posts: 412
Threads: 40
Joined: Mar 2006
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.
JF
Valentin: you may notice that the speedup 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...
▼
Posts: 412
Threads: 40
Joined: Mar 2006
Correction:
With /f50 on a 1.7GHz processor the speedup 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=TIMET @ IF T<2 THEN N=N*2 @ GOTO 275
295 DISP T;"s. SPEED=";IP(N/T)/100;"TIMES HP71B SPEED"
300 END SUB
JF
▼
Posts: 1,755
Threads: 112
Joined: Jan 2005
Thanks a lot for the detailed explanation, JeanFranç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 71Brelated 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.
Posts: 412
Threads: 40
Joined: Mar 2006
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 24digit 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=XL ! x= [n,m] mod L
100 IF X<>0 THEN X=LX ! 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=L1 @ IF L>2 THEN 'C'
200 NEXT I
The only three 24digit solutions are:
144408645048 225636603816
360852885036 840078603672
402852168072 900828009216
So the unique 25digit 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 nontrivial algorithm on HP48's RPL for instance?
JF
▼
Posts: 1,841
Threads: 54
Joined: Jul 2005
Hi JF,
nice exercise.
For an HP48 (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
;
Posts: 412
Threads: 40
Joined: Mar 2006
Here is my structured programming style solution, using the HP71B 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=XL ! x= [n,m] mod L
140 IF X<>0 THEN X=LX ! 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=L1
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.
JF
▼
Posts: 1,107
Threads: 159
Joined: Jan 1970
Posts: 1,755
Threads: 112
Joined: Jan 2005
Hi, JF:
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
25digit 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.
Posts: 1,841
Threads: 54
Joined: Jul 2005
Hi JF,
did you see my last post?
Your today's solution will be even easier to port to RPL;)
Regards
Raymond
▼
Posts: 412
Threads: 40
Joined: Mar 2006
Hi Raymond,
Yes I read your post, this was one reason to me to write a GOTOless version (the other reason was to demonstrate the JPCROM powerfull features).
But User RPL is good enough for this problem :)
JF
Edited: 31 May 2005, 3:25 p.m.
