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

  • Admin Support Member
  • *****
  • Posts: 4486
    • Oxygen Basic
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

  • Admin Support Member
  • *****
  • Posts: 4486
    • Oxygen Basic
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

  • Admin Support Member
  • *****
  • Posts: 4486
    • Oxygen Basic
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
  71.  add dword 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
  87.   add eax,tmp1
  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]
  97.  add eax,1
  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
  106.   add eax,tmp2
  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.

Please try the following code:

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
  71.      add dword 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
  87.       add eax,tmp1
  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]
  97.      add eax,1
  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
  106.       add eax,tmp2
  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.  
  162.   pushad
  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
  179.   add dword [count], 1
  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
  194.  add edx, i
  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
  208.  add edx, i
  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.  
  250.   popad
  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)