How can I construct a 2^63-gon with a straightedge and compass?

I entered 2^63 as a stand alone value at WolframAlpha. Among the responses was a factoid that 'A regular 9223372036854775808-gon is constructible with a straightedge and compass.'

What is such a shape and how can I construct one?

-
Draw a circle with the compass. Label it a $2^{63}$-gon ;) – Dario Aug 3 '12 at 20:25
You should probably try it with a heptagon first, before moving on to the hard stuff. – SiliconCelery Aug 3 '12 at 20:52
This is doable if you have a big enough piece of paper. At 1 inch per side, it'll only take a sheet 7.9 light years wide. Of course, the time to do the construction would be a bit daunting. – Rick Decker Aug 3 '12 at 21:27
@Silicon, that was a cruel joke... :) – J. M. Aug 3 '12 at 22:19

Start with a circle and a diameter. Bisect the diameter and extend the bisector to the circle to make a square. Bisect each right angle at the center of the circle $61$ times, extending the bisector to the circle. You have $2^{63}$ points, equally spaced, around the circle. As Dario says, you won't be able to tell it from the original circle.
The regular polygons constructible with straightedge and compass have the number of sides of the form $2^n$ times a product of zero or more of the Fermat primes: $3, 5, 17, 257, 65537$ (each to only the first power)
This will probably be indistinguishable from the way that I usually draw regular $2^{63}$-gons: place the point of the compass and draw a circle. – robjohn Aug 3 '12 at 20:42
I strongly doubt that you'll have $2^{63}$ equally spaced points after this procedure. Even if you just make an error of only 0.1% per step, you'll have a total error of more than 6% in the last constructed points. – celtschk Aug 3 '12 at 20:48
@celtschk: my errors are random, so they only build up as $\sqrt n$, making about $0.8\%$ at the end. As $2^{63} \approx 9.2\cdot 10^{18}$ this would be $7.4$ parts in $10^{20}$ of the original circle diameter. I challenge you to find it. – Ross Millikan Aug 3 '12 at 21:41