[pieguy]

Here's an iterative solution which is shorter and 3 times as fast:

  void iterative(int n)
  {
      int from[2][3] = {{0,1,2},{0,2,1}};
      int   to[2][3] = {{1,2,0},{2,1,0}};
      for(int i=1; i<1<<n; i++)
      {
          int disk = __builtin_ctz(i);
          int count = (i>>(1+disk))%3;
          int parity = (disk^n)&1;
          move(from[parity][count], to[parity][count]);
      }
  }

[thaumaturgy]

Neat. Were you able to get his code to run? What did you change / what compiler flags did you use?

[pieguy]

I removed the free() call because it was crashing. I also added a cast to the malloc() because I was compiling in C++. Compiled with

  g++ -o hanoi hanoi.cpp -O2 -lrt

[thaumaturgy]

Thanks. I had also cast malloc() but didn't think to just comment out free().

So I'm seeing similar results as you. Your iterative implementation is about 3x faster than the author's, but still not as fast as the recursive version. I'm surprised!