### Author Topic: Tower of Hanoi puzzle  (Read 7126 times)

0 Members and 1 Guest are viewing this topic.

#### Arnold

• Hero Member
• Posts: 977
##### Tower of Hanoi puzzle
« on: March 22, 2016, 04:56:09 am »
Hello,

This is the Tower of Hanoi problem in Oxygenbasic. The recursive algorithm I found at Rosetta code:
https://rosettacode.org/wiki/Towers_of_Hanoi
The Basic solution using a Subroutine can be run almost unchanged with Oxygenbasic. (the print statement must be adapted).
The iterative binary algorithm I found here:
http://hanoitower.mkolar.org/shortestTHalgo.html

When I started to read about ToH in Wikipedia I noticed that this problem and the possible variations is indeed not a trivial task. ToH is even used in psychological research on problem solving or is also used as a test by neuropsychologists trying to evaluate frontal lobe deficits. And much more. This is really astonishing.

The two algorithms I found are brilliant. I am jealous that I probably will never have such enlightenments. The binary solution is a little bit faster but using faster computers than mine I think this will not play a big role.

Nevertheless I wonder how this little piece of code would look in assembler and if there would be a gain in speed:

sub bmove(int n)
for x=1 to (1 << n)-1
count+=1
xm1=x-1
i=x & xm1     : fp=(i+i\3)&3
i=(x | xm1)+1 : tp=(i+i\3)&3

i=x : j=1
do
if (i & 1) then exit do
i=i >> 1 : j++
end do
next
end sub

Roland

Code: OxygenBasic
1. #include "\$/inc/console.inc"
2.
3. SetConsoleTitle "Towers of Hanoi problem"
4.
5. ! function GetTickCount lib "KERNEL32.DLL" () as dword
6.
7. function time() as double
8.   return GetTickCount()/1000
9. end function
10.
11. int count, seeMoves
12. double t1,t2
13.
14. sub rmove (int n, fromPeg, toPeg, viaPeg)
15.    if n>0 then
16.      rmove n-1, fromPeg, viaPeg, toPeg
17.      count+=1
18.      if seeMoves then
19.        printl count ": Move disc " n " from " chr(fromPeg+64) " to " chr(toPeg+64)
20.      end if
21.      rmove n-1, viaPeg, toPeg, fromPeg
22.    end if
23. end sub
24.
25. sub bmove(int n)
26.    for x=1 to (1 << n)-1
27.      count+=1
28.      xm1=x-1
29. '     fp=mod(x & xm1,3) : tp=mod((x | xm1)+1,3) 'slower
30.     i=x & xm1     : fp=(i+i\3)&3
31.      i=(x | xm1)+1 : tp=(i+i\3)&3
32.
33.      i=x : j=1
34.      do
35.        if (i & 1) then exit do
36.        i=i >> 1 : j++
37.      end do
38.
39.      if seeMoves then
40.        printl count ": Move disc " j " from " chr(fp+65) " to " chr(tp+65)
41.      end if
42.    next
43. end sub
44.
45.
46. start:
47.
48. cls
49. seeMoves=0
50. print "Number of discs? " : num = val(input)
51. print "See the moves? (y/n) "
52. ans=waitkey : if lcase(chr(ans))="y" or lcase(chr(ans))="j" then seeMoves=1
53. printl "Minimum moves required: " pow(2,num)-1 & cr
54.
55. printl "Calculating recursive, wait ..."
56. count=0
57. t1=time() : rmove num,1,2,3 : t2=time()
58. printl "Calculated " count " moves in " str(t2-t1,3) " seconds" & cr
59.
60. printl "Calculating binary, wait ..."
61. count=0
62. t1=time() : bmove num : t2=time()
63. printl "Calculated " count " moves in " str(t2-t1,3) " seconds" & cr
64.
65. printl "Another Try? (y/n)"
66. ans = getkey
67. if lcase(chr(ans))="y" or lcase(chr(ans))="j" then goto start
68.
69.

.

#### John

• Hero Member
• Posts: 3966
##### Re: Tower of Hanoi puzzle
« Reply #1 on: March 23, 2016, 10:30:36 pm »
Roland,

Is this doing bit shifting?

Code: OxygenBasic
1. i=i >> 1
2.

#### Arnold

• Hero Member
• Posts: 977
##### Re: Tower of Hanoi puzzle
« Reply #2 on: March 24, 2016, 12:39:56 am »
Hi John,

yes I think << and >> do the same job as the C operators. (binary left/right shift by the number of bits). I assume it is the same as integer divide / multiply with 2 ^ NumberOfBits. I also found <<< and >>> but I am not quite sure about the purpose of these operators.

Roland

Code: OxygenBasic
1. #include "\$/inc/console.inc"
2.
3. int i=100000000, j=i
4. int nb=4  'number of bits to shift
5.
6. i = i >> nb : printl i
7. j = j \ (pow(2,nb)) : printl j
8.
9. 'reverse
10.
11. i = i << nb : printl i
12. j = j * (pow(2,nb)) : printl j
13.
14. waitkey
15.

#### John

• Hero Member
• Posts: 3966
##### Re: Tower of Hanoi puzzle
« Reply #3 on: March 24, 2016, 01:03:12 am »
Charles created these Script BASIC extension module functions to deal with shift and rotate of bits.

@Charles - I'm unable to find the docs for these functions. Can you refresh my memory?

Code: C
1. besFUNCTION(gfx_Shift)
2.   DIM AS int bp, co, v, x, y, d, p, ar;
3.   besARGUMENTS("ii[i]")
4.     AT v, AT p, AT ar
5.   besARGEND
6.   IF (ar EQ NULL) THEN_DO ar = 0;
7.   x = 0xffffffff & v;
8.   IF (p >= 0) THEN
9.     y = x << p; // bit shift left
10.   ELSE
11.     y = x >> (-p); // bit shift right
12.   END_IF
13. //
14. // SUPPORT FOR ARITHMETIC RIGHT SHIFTS
15. //
16.   IF ((ar) AND (p < 0) AND (x & 0x80000000)) THEN
17.     d = 31 + p;
18.     IF (d < 0) THEN_DO d = 0; // LIMIT
19.     bp = 0x80000000;
20.     DEF_FOR (co = 31 TO co >= d STEP DECR co)
21.     BEGIN_FOR
22.       y = y | bp;
23.       bp = bp >> 1;
24.     NEXT
25.   END_IF
26.   besRETURN_LONG(y);
27. besEND
28.
29. besFUNCTION(gfx_Rotate)
30.   DIM AS int co, v, x, y, d, p;
31.   besARGUMENTS("ii")
32.     AT v, AT p
33.   besARGEND
34.   x = 0xffffffff & v;
35.   d = p & 0x1f;
36.   DEF_FOR (co = 1 TO co <= d STEP INCR co)
37.   BEGIN_FOR
38.     y = x << 1;
39.     IF (x & 0x80000000) THEN_DO y |= 1;
40.     x = y;
41.   NEXT
42.     besRETURN_LONG(x & 0xffffffff);
43. besEND
44.
« Last Edit: March 24, 2016, 01:58:19 am by John »

#### Charles Pegge

• Posts: 4486
##### Re: Tower of Hanoi puzzle
« Reply #4 on: March 24, 2016, 02:03:26 pm »

OxygenBasic incorporates bit rotation operators. It uses assembly code instructions ROL and ROR.

In the case of 32 bit integers:

<<< shift left with bit 31 moving to bit 0

>>> shift right with bit 0 moving to bit 31

In C without recourse to Assember, such operators have to be emulated.

Shift Arithmetic Right (SAR) is the same as Shift Right (SHR) except that if bit 31, the sign bit,  is set then it remains set after each bit shift, instead of being cleared. The effect is to retain sign. Thus, -4 becomes -2 etc.

#### John

• Hero Member
• Posts: 3966
##### Re: Tower of Hanoi puzzle
« Reply #5 on: March 25, 2016, 12:56:37 am »
I can't understand how this code would do a shift right with the Script BASIC gfx_shift function.

Code: OxygenBasic
1. i=i >> 1
2.

If I translate this to

Code: Script BASIC
1. i = SHIFT(i, 1)
2.

It's going to do a shift left as the second argument is greater than zero.

#### Charles Pegge

• Posts: 4486
##### Re: Tower of Hanoi puzzle
« Reply #6 on: March 25, 2016, 01:08:02 am »

Hi John,

use negative values to shift right, for this function:

shift(i,-1)

#### Arnold

• Hero Member
• Posts: 977
##### Re: Tower of Hanoi puzzle
« Reply #7 on: March 25, 2016, 01:38:17 am »
I do not know about Scriptbasic, but I think instead using shift operaters integer multiplication or division can be used. I assume for quads this is necessary anyway. So in OxygenBasic I could use for:

i=i>>1
i=i\2
and the loop would be:
for x=1 to (1 << n)-1
for x=1 to x*pow(2,n)-1

But I wanted to keep some of the original code. (and shifting is a little bit faster)

Roland

#### Mike Lobanovsky

• Hero Member
• Posts: 1993
##### Re: Tower of Hanoi puzzle
« Reply #8 on: March 25, 2016, 03:20:49 am »
(and shifting is a little bit faster)

Hi,

Actually, right shifts are a hellofalot faster on a modern Pentium than the respective integer division by a power-of-two (POT):
• SHR/SAR instructions take only 1 CPU cycle to execute if the dividend is already in a register, or only 3 cycles if it is in memory;
• SHR/SAR can be paired with other instructions in the Pentium UV pipes (if only the memory dividend and/or divisor aren't using an immediate value for displacement addressing), which effectively halves the execution time to 0.5 and 1.5 CPU cycles, respectively;
• DIV/IDIV take 41/46 CPU cycles to execute on a Pentium and they need a few extra cycles to load at least the dividend into a register (memory and immediate dividends aren't permitted);
• DIV/IDIV instructions aren't pairable at all.
Left shifts are also much faster than unsigned/signed multiplication by a POT: SHL/SAL are as fast and pairable as SHR/SAR while MUL/IMUL take at least 10 CPU cycles to execute and aren't pairable in the UV pipes.

Please correct me Charles if I am wrong, but in my opinion, since Oxygen resolves its BASIC code to assembly, the above considerations hold true for O2 as well.
« Last Edit: March 25, 2016, 03:33:13 am by Mike Lobanovsky »
Mike
(3.6GHz Intel Core i5 Quad w/ 16GB RAM, nVidia GTX 1060Ti w/ 6GB VRAM, Windows 7 Ultimate Sp1)

#### Charles Pegge

• Posts: 4486
##### Re: Tower of Hanoi puzzle
« Reply #9 on: March 25, 2016, 11:56:19 am »
Hi Mike, Glad to see you back

Yes O2 resolves shifts directly to assembler.

I recall my last DIV timing was about 35 clocks. Division fundamentally requires successive approximation. But muls have improved considerably on recent Pentiums, down to 1 or 2 clocks - in one massive hardware mul-gasm, I imagine.

#### John

• Hero Member
• Posts: 3966
##### Re: Tower of Hanoi puzzle
« Reply #10 on: March 25, 2016, 05:55:18 pm »
Quote from: Charles
Hi Mike, Glad to see you back.

+1

#### John

• Hero Member
• Posts: 3966
##### Re: Tower of Hanoi puzzle
« Reply #11 on: March 25, 2016, 10:34:39 pm »
Roland,

Here is the Script BASIC version. The Script BASIC POW() is base 10 only.

Code: Script BASIC
1. IMPORT gfx.inc
2.
3. PRINT "Towers of Hanoi problem\n"
4.
5. count = 0
6. seeMoves = 0
7. t1 = .0
8. t2 = .0
9.
10. SUB rmove (n, fromPeg, toPeg, viaPeg)
11.    IF n > 0 THEN
12.      rmove n - 1, fromPeg, viaPeg, toPeg
13.      count += 1
14.      IF seeMoves THEN
15.        PRINT count, ": Move disc ", n, " from ", CHR(fromPeg + 64), " to ", CHR(toPeg + 64),"\n"
16.      END IF
17.      rmove n - 1, viaPeg, toPeg, fromPeg
18.    END IF
19. END SUB
20.
21. SUB bmove(n)
22.    FOR x = 1 TO n - 1
23.      count += 1
24.      xm1 = x -1
25.      ' fp = x AND xm1 % 3
26.     ' tp = (x OR xm1) + 1 % 3
27.     i = x AND xm1
28.      fp = (i + i \ 3) AND 3
29.      i = (x OR xm1) + 1
30.      tp = (i + i \ 3) AND 3
31.      i = x
32.      j = 1
33.      WHILE NOT i AND 1
34. '      IF i AND 1 THEN GOTO Exit_Do
35.       i = gfx::Shift(i, -1)
36.        j += 1
37.      WEND
38. '    Exit_Do:
39.     IF seeMoves THEN
40.        PRINT count, ": Move disc ", j, " from ", CHR(fp + 65), " to ", CHR(tp + 65), "\n"
41.      END IF
42.    NEXT
43. END SUB
44.
45.
46. start:
47.
48. ' cls
49. seeMoves = 0
50. PRINT "Number of discs? "
51. LINE INPUT user_input
52. num = VAL(CHOMP(user_input))
53. PRINT "See the moves? (y/n) "
54. LINE INPUT waitkey
55. ans = CHOMP(waitkey)
56. IF LCASE(ans) = "y" OR LCASE(ans) = "j" THEN seeMoves = 1
57. ' PRINT "Minimum moves required: ", POW(num) - 1, "\n"
58.
59. PRINT "Calculating recursive, wait ...\n"
60. count = 0
61. t1 = gfx::TIME()
62. rmove(num, 1, 2, 3)
63. t2 = gfx::time()
64. PRINT "Calculated ", count, " moves in ", FORMAT("%.4f",(t2-t1)/1000), " seconds\n"
65.
66. PRINT "Calculating binary, wait ...\n"
67. count = 0
68. t1 = gfx::time()
69. bmove(num)
70. t2 = gfx::time()
71. PRINT "Calculated ", count, " moves in ", FORMAT("%.4f",(t2-t1)/1000), " seconds\n"
72.
73. PRINT "Another Try? (y/n) "
74. LINE INPUT getkey
75. ans = CHOMP(gettkey)
76. IF LCASE(ans) = "y" OR LCASE(ans) = "j" THEN GOTO start
77.

jrs@laptop:~/sb/sb22/test\$ scriba hanoi.sb
Towers of Hanoi problem
Number of discs? 4
See the moves? (y/n) y
Calculating recursive, wait ...
1: Move disc 1 from A to C
2: Move disc 2 from A to B
3: Move disc 1 from C to B
4: Move disc 3 from A to C
5: Move disc 1 from B to A
6: Move disc 2 from B to C
7: Move disc 1 from A to C
8: Move disc 4 from A to B
9: Move disc 1 from C to B
10: Move disc 2 from C to A
11: Move disc 1 from B to A
12: Move disc 3 from C to B
13: Move disc 1 from A to C
14: Move disc 2 from A to B
15: Move disc 1 from C to B
Calculated 15 moves in 0.0000 seconds
Calculating binary, wait ...
1: Move disc 1 from A to C
2: Move disc 2 from A to B
3: Move disc 1 from C to B
Calculated 3 moves in 0.0000 seconds
Another Try? (y/n)

« Last Edit: March 26, 2016, 12:58:21 am by John »

#### Mike Lobanovsky

• Hero Member
• Posts: 1993
##### Re: Tower of Hanoi puzzle
« Reply #12 on: March 26, 2016, 02:39:47 am »
Hi everyone,

I'm also glad to see you around!

@Charles:

Intel is very reluctant to publish exact data on their modern superscalar CPUs (the ones that allow "out-of-order" parallel execution of instructions in the U and V execution pipes) so I won't be able to quote their quadcore iN CPUs, but their Core2 processors are still very slow in muldiv operations' latency which is also heavily bitness-dependent:

0. DIV : 40 cycles in 32 bits, 116 cycles in 64 bits, non-pairable
1. MUL : 5 cycles in 32 bits, 8 cycles in 64 bits, non-pairable
2. IMUL : 3 cycles in 32 bits, 5 cycles in 64 bits, non-pairable
3. left/right shift : 1 cycle in any bitness, freely pairable (i.e. 0.5 cycles if paired)

This means that the left shift is still 3 times faster than the fastest IMUL (non-paired 32 bits, worst case) and 16 times faster than the slowest MUL (paired 64 bits, best case).

DIV indeed remains the toughest bottleneck, and especially so, under 64 bits.
Mike
(3.6GHz Intel Core i5 Quad w/ 16GB RAM, nVidia GTX 1060Ti w/ 6GB VRAM, Windows 7 Ultimate Sp1)

#### Arnold

• Hero Member
• Posts: 977
##### Re: Tower of Hanoi puzzle
« Reply #13 on: March 28, 2016, 12:39:33 am »
Hi Charles,

this was my laborious task yesterday. I tried to transfer the statements for the ToH bmove function into assembler (amove). You will recognise the code.

Would there be a strategy to make this code still a little bit more efficient? As is at the moment there is not much gain of speed, but this is clear of course.

The reason for my question is if it makes sense to try assembly code for some small critical pieces in a function or sub or if this would be "much do about nothing". I personally think a good algorithm would save a lot of time anyway.

Roland

Code: OxygenBasic
1. \$ filename "Hanoi.exe"
2. '#include "\$/inc/RTL32.inc"
3.
4. #include "\$/inc/console.inc"
5.
6. ! function GetTickCount lib "KERNEL32.DLL" () as dword
7.
8. function time() as double
9.   return GetTickCount()/1000
10. end function
11.
12. int num, seeMoves
13. string ans
14. double t1,t2
15.
16. #view
17. sub bmove(int n)
18.   int count=0
19.   for ix=1 to (1 << n)-1
20.      count+=1
21.      xm1=ix-1
22.
23.      i=ix & xm1
24.      fp=(i+i\3)&3
25.      i=(ix | xm1)+1
26.      tp=(i+i\3)&3
27.
28.
29.      i=ix
30.      j=1
31.      do
32.        if (i & 1) then exit do
33.        i=i >> 1
34.        j++
35.      end do
36.      if seeMoves
37.        printl count ": Move disc " j " from " chr(fp+65) " to " chr(tp+65)
38.      end if
39.   next
40.   printl "Calculated " count " moves"
41. end sub
42. #endv
43.
44.
45. sub amove(int n) '0x8
46.  int count,ix,to_limit,xm1,i,tmp1,fp,tmp2,tp,j
47.
48. '_7     '  for ix=1 to (1 << n)-1
49.  mov eax,1
50.   mov ix,eax
51.   mov eax,1
52.   mov cl,n
53.   shl eax,cl
54. ''  mov [ebp-0x20],eax
55. ''  mov eax,[ebp-0x20]
56.  sub eax,1
57.   mov to_limit,eax
58. (
59. ._for
60.   mov eax,to_limit
61.   cmp ix,eaX
62.   mov eax,-1
63.   jle fwd _c
64.   inc eax
65. ._c
66.   or eax,eax
67.   jz fwd _exit_for
68.
69.
70. '_8     '     count+=1
72. '_9     '     xm1=ix-1
73.  mov eax, ix
74.   sub eax,1
75.   mov xm1,eax
76. '_11'     i=ix & xm1
77.  mov eax,ix
78.   and eax,xm1
79.   mov i,eax
80. '_12    '     fp=(i+i\3)&3
81.  mov eax,i
82.   cwd
83.   mov ecx,3
84.   idiv ecx
85.   mov tmp1,eax
86.   mov eax,i
88. ''  mov [ebp-0x30],eax
89. ''  mov eax,[ebp-0x30]
90.  and eax,3
91.   mov fp,eax
92. '_13'     i=(ix | xm1)+1
93.  mov eax,ix
94.   or eax,xm1
95. ''  mov [ebp-0x44],eax
96. ''  mov eax,[ebp-0x44]
98.   mov i,eax
99. '_14    '     tp=(i+i\3)&3
100.  mov eax,i
101.   cwd
102.   mov ecx,3
103.   idiv ecx
104.   mov tmp2,eax
105.   mov eax,i
107. ''  mov [ebp-0x4C],eax
108. ''  mov eax,[ebp-0x4C]
109.  and eax,3
110.   mov tp,eax
111. '_16    '     i=ix
112.  mov eax, ix
113.   mov i,eax
114. '_17    '     j=1
115.  mov eax,1
116.   mov j,eax
117.
118. '_18    '     do
119. (
120. ._do
121.         '       if (i & 1) then exit do
122. (
123.   mov eax,i
124.   and eax,1
125. ._cnd
126.   or eax,eax
127.   jz fwd _exit_cnd
128.   jmp fwd _exit_do
129. ._exit_cnd
130. ._exit_if
131. )
132.
133. '_20    '       i=i >> 1
134.  mov eax,i
135.   shr eax,1
136.   mov i,eax
137. '_21    '       j++
138.  inc [ebp-0x5C]
139.   inc j
140. '_22    '     end do
141.  jmp long _do
142. ._exit_do
143. )
144.
145.   if seeMoves then
146.      printl count ": Move disc " j " from " chr(fp+65) " to " chr(tp+65)
147.   end if
148.
149. '_24    '  next
150.  inc ix
151.   jmp long _for
152. ._exit_for
153.
154.   printl "Calculated " count " moves"
155. )
156.
157. end sub
158.
159.
160.
161. start:
162.
163. cls
164. seeMoves=0
165. print "Number of discs? " : num = val(input)
166. print "See the moves? (y/n) "
167. ans=waitkey : if lcase(chr(ans))="y" then seeMoves=1
168. printl "Minimum moves required: " pow(2,num)-1 & cr
169.
170. printl "Calculating binary, wait ..."
171. t1=time() : bmove num : t2=time : print " in " str(t2-t1,3) " seconds" & cr
172.
173. printl "Calculating binary with ASM, wait ..."
174. t1=time() : amove num : t2=time : print " in " str(t2-t1,3) " seconds" & cr
175.
176. printl "Another Try? (y/n)"
177. ans = getkey
178. if lcase(chr(ans))="y" then goto start
179.

Output:

Number of discs? 28
See the moves? (y/n)
Minimum moves required: 268435455

Calculating binary, wait ...
Calculated 268435455 moves in 22.557 seconds

Calculating binary with ASM, wait ...
Calculated 268435455 moves in 20.639 seconds

Another Try? (y/n)

#### Mike Lobanovsky

• Hero Member
• Posts: 1993
##### Re: Tower of Hanoi puzzle
« Reply #14 on: March 28, 2016, 05:27:15 am »
Hi Roland,

The asm code you suggest is rather slow because it is built around memory variable access and integer division. You can speed it up almost 3 times by:
• saving more temp vars in the CPU registers; and
• using a much faster approximation of integer divide by 3.
There are a lot of tricks described on the net to speed up hand-written assembly for slower processor instructions like integer division and multiplication and FPU maths.

Code: OxygenBasic
1.     \$ filename "Hanoi.exe"
2.     '#include "\$/inc/RTL32.inc"
3.
4.     #include "\$/inc/console.inc"
5.
6.     ! function GetTickCount lib "KERNEL32.DLL" () as dword
7.
8.     function time() as double
9.       return GetTickCount()/1000
10.     end function
11.
12.     int num, seeMoves
13.     string ans
14.     double t1,t2
15.
16.     #view
17.     sub bmove(int n)
18.       int count=0
19.       for ix=1 to (1 << n)-1
20.          count+=1
21.          xm1=ix-1
22.
23.          i=ix & xm1
24.          fp=(i+i\3)&3
25.          i=(ix | xm1)+1
26.          tp=(i+i\3)&3
27.
28.
29.          i=ix
30.          j=1
31.          do
32.            if (i & 1) then exit do
33.            i=i >> 1
34.            j++
35.          end do
36.          if seeMoves
37.            printl count ": Move disc " j " from " chr(fp+65) " to " chr(tp+65)
38.          end if
39.       next
40.       printl "Calculated " count " moves"
41.     end sub
42.     #endv
43.
44.
45.     sub amove(int n) '0x8
46.      int count,ix,to_limit,xm1,i,tmp1,fp,tmp2,tp,j
47.
48.     '_7     '  for ix=1 to (1 << n)-1
49.      mov eax,1
50.       mov ix,eax
51.       mov eax,1
52.       mov cl,n
53.       shl eax,cl
54.     ''  mov [ebp-0x20],eax
55.    ''  mov eax,[ebp-0x20]
56.      sub eax,1
57.       mov to_limit,eax
58.     (
59.     ._for
60.       mov eax,to_limit
61.       cmp ix,eaX
62.       mov eax,-1
63.       jle fwd _c
64.       inc eax
65.     ._c
66.       or eax,eax
67.       jz fwd _exit_for
68.
69.
70.     '_8     '     count+=1
72.     '_9     '     xm1=ix-1
73.      mov eax, ix
74.       sub eax,1
75.       mov xm1,eax
76.     '_11'     i=ix & xm1
77.      mov eax,ix
78.       and eax,xm1
79.       mov i,eax
80.     '_12    '     fp=(i+i\3)&3
81.      mov eax,i
82.       cwd
83.       mov ecx,3
84.       idiv ecx
85.       mov tmp1,eax
86.       mov eax,i
88.     ''  mov [ebp-0x30],eax
89.    ''  mov eax,[ebp-0x30]
90.      and eax,3
91.       mov fp,eax
92.     '_13'     i=(ix | xm1)+1
93.      mov eax,ix
94.       or eax,xm1
95.     ''  mov [ebp-0x44],eax
96.    ''  mov eax,[ebp-0x44]
98.       mov i,eax
99.     '_14    '     tp=(i+i\3)&3
100.      mov eax,i
101.       cwd
102.       mov ecx,3
103.       idiv ecx
104.       mov tmp2,eax
105.       mov eax,i
107.     ''  mov [ebp-0x4C],eax
108.    ''  mov eax,[ebp-0x4C]
109.      and eax,3
110.       mov tp,eax
111.     '_16    '     i=ix
112.      mov eax, ix
113.       mov i,eax
114.     '_17    '     j=1
115.      mov eax,1
116.       mov j,eax
117.
118.     '_18    '     do
119.    (
120.     ._do
121.             '       if (i & 1) then exit do
122.    (
123.       mov eax,i
124.       and eax,1
125.     ._cnd
126.       or eax,eax
127.       jz fwd _exit_cnd
128.       jmp fwd _exit_do
129.     ._exit_cnd
130.     ._exit_if
131.     )
132.
133.     '_20    '       i=i >> 1
134.      mov eax,i
135.       shr eax,1
136.       mov i,eax
137.     '_21    '       j++
138.      inc [ebp-0x5C]
139.       inc j
140.     '_22    '     end do
141.      jmp long _do
142.     ._exit_do
143.     )
144.
145.       if seeMoves then
146.          printl count ": Move disc " j " from " chr(fp+65) " to " chr(tp+65)
147.       end if
148.
149.     '_24    '  next
150.      inc ix
151.       jmp long _for
152.     ._exit_for
153.
154.       printl "Calculated " count " moves"
155.     )
156.
157.     end sub
158.
159. sub amove2(int n)
160.   int count,i,j,fp,tp
161.
163.
164.   '_7 for ix=1 to (1 << n)-1
165.  mov esi, 1 ' ix
166.  mov edi, esi
167.   mov cl, n
168.   shl edi, cl
169.   dec edi ' to_limit
170.
171. (
172.   ._for
173.   cmp esi, edi
174.   jle fwd _c
175.   jmp fwd _exit_for
176.
177.   '_8 count+=1
178.  ._c
180.
181.   '_9 xm1=ix-1
182.  mov ebx, esi
183.   dec ebx ' xm1
184.
185.   '_11 i=ix & xm1
186.  mov eax, esi ' ix
187.  and eax, ebx ' xm1
188.  mov i, eax
189.
190.   '_12 fp=(i+i\3)&3
191.  mov ecx, 0xAAAAAAAB ' 1/3
192.  mul ecx ' multiply with inverse
193.  shr edx, 1 ' shift by 33
195.   and edx, 3
196.   mov fp, edx
197.
198.   '_13 i=(ix | xm1)+1
199.  mov eax, esi ' ix
200.  or eax, ebx ' xm1
201.  inc eax
202.   mov i, eax
203.
204.   '_14 tp=(i+i\3)&3
205.  mov ecx, 0xAAAAAAAB ' 1/3
206.  mul ecx ' multiply with inverse
207.  shr edx, 1 ' shift by 33
209.   and edx, 3
210.   mov tp, edx
211.
212.   '_16 i=ix
213.  mov ecx, esi
214.
215.   '_17 j=1
216.  mov edx, 1
217.
218.   '_18 do
219. (
220.   ._do
221. (
222.   ' if (i & 1) then exit do
223.  mov eax, ecx ' i
224.  and eax, 1
225.   ._cnd
226.   or eax, eax
227.   jz fwd _exit_cnd
228.   jmp fwd _exit_do
229.   ._exit_cnd
230.   ._exit_if
231. )
232.
233.   '_20 i=i >> 1
234.  shr ecx, 1
235.
236.   '_21 j++
237.  '    inc [ebp-0x5C]
238.  inc edx ' j
239.
240.   '_22 end do
241.  jmp long _do
242.   ._exit_do
243. )
244.
245.   '_24 next
246.  inc esi ' ix
247.  jmp long _for
248.   ._exit_for
249.
251. )
252.
253.   printl "Calculated " count " moves"
254. end sub
255.
256.     start:
257.
258.     cls
259.     seeMoves=0
260.     print "Number of discs? " : num = val(input)
261.     print "See the moves? (y/n) "
262.     ans=waitkey : if lcase(chr(ans))="y" then seeMoves=1
263.     printl "Minimum moves required: " pow(2,num)-1 & cr
264.
265.     printl "Calculating binary, wait ..."
266.     t1=time() : bmove num : t2=time : print " in " str(t2-t1,3) " seconds" & cr
267.
268.     printl "Calculating binary with Roland's ASM, wait ..."
269.    t1=time() : amove num : t2=time : print " in " str(t2-t1,3) " seconds" & cr
270.
271.     printl "Calculating binary with Mike's ASM, wait ..."
272.    t1=time() : amove2 num : t2=time : print " in " str(t2-t1,3) " seconds" & cr
273.
274.     printl "Another Try? (y/n)"
275.     ans = getkey
276.     if lcase(chr(ans))="y" then goto start

.
« Last Edit: March 28, 2016, 11:08:56 pm by Mike Lobanovsky »
Mike
(3.6GHz Intel Core i5 Quad w/ 16GB RAM, nVidia GTX 1060Ti w/ 6GB VRAM, Windows 7 Ultimate Sp1)