[math-fun] sqrt( |Rubik| )
From: "Schroeppel, Richard" <rschroe@sandia.gov>
We now have enough computing power to find & prove the distance- to-start for any particular position, using the obvious square-root meet-in-the-middle algorithm and a big disk.
http://en.wikipedia.org/wiki/Rubik%27s_Cube_group says that the number of positions is ( 8! 3^8 12! 2^12 ) / 12 = 43,252,003,274,489,856,200 so the square root is about 6,576,625,523 Each position needs about 5 bytes, and I guess having two copies of the set would make it go a lot faster, so that's 66 terabytes...by my amateur guess. This NYT article about Google's new server farm complex in The Dalles, Oregon http://tinyurl.com/pfvz8 says, "The best guess is that Google now [pre-The Dalles] has more than 450,000 servers spread in at least 25 locations around the world. " If those servers each have 2x10^8 ips, that's about 10^14 ips, which matches Hans Moravec's estimate of the effective power of a human brain (though not in a tight enough cluster). --Steve
On Mon, 10 Jul 2006, Steve Witham wrote:
From: "Schroeppel, Richard" <rschroe@sandia.gov>
We now have enough computing power to find & prove the distance- to-start for any particular position, using the obvious square-root meet-in-the-middle algorithm and a big disk.
http://en.wikipedia.org/wiki/Rubik%27s_Cube_group says that the number of positions is ( 8! 3^8 12! 2^12 ) / 12 = 43,252,003,274,489,856,200 so the square root is about 6,576,625,523
Each position needs about 5 bytes, and I guess having two copies of the set would make it go a lot faster, so that's 66 terabytes...by my amateur guess.
This NYT article about Google's new server farm complex in The Dalles, Oregon http://tinyurl.com/pfvz8 says, "The best guess is that Google now [pre-The Dalles] has more than 450,000 servers spread in at least 25 locations around the world. "
If somebody is serious about coding up an algorithm, let's work up some resource estimates and I can ask if we can get them for this important bit of mathematical research. I work for a company that reportedly has servers spread in at least 25 locations around the world. -J
participants (2)
-
Jason Holt -
Steve Witham