Re: [math-fun] Doin' the Hilbert walk
In late August Fred Lunnon asked some questions about Hilbert walks in more than 2D. One of the questions was just, how do you map between the index of a point along the walk, and the coordinates of that point, if possible in a log-time way? Some suggested it was simple, but as far as I know, none of the simple ideas actually generates a Hilbert-style walk. I wrote privately to Fred that it *must* be simple ("trivial" is what I said, actually). It's exactly two months from the date I wrote that, and I have working (though not at all optimized) code and a draft of a description of how it works up at http://www.tiac.net/~sw/2008/10/Hilbert I would appreciate critique. --humbled Steve
Btw. an implementation of Lunnon's algorithm is online at http://www.jjj.de/fxt/demo/comb/#hilbert-ndim I find that one, uhm, awesome. * Steve Witham <sw@tiac.net> [Nov 12. 2008 12:34]:
In late August Fred Lunnon asked some questions about Hilbert walks in more than 2D. One of the questions was just, how do you map between the index of a point along the walk, and the coordinates of that point, if possible in a log-time way?
Some suggested it was simple, but as far as I know, none of the simple ideas actually generates a Hilbert-style walk.
I wrote privately to Fred that it *must* be simple ("trivial" is what I said, actually).
It's exactly two months from the date I wrote that, and I have working (though not at all optimized) code and a draft of a description of how it works up at http://www.tiac.net/~sw/2008/10/Hilbert
I would appreciate critique.
--humbled Steve
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
It ought to be pointed out that these two are implementations of the "simple-minded" algorithm I developed first --- but then found impossible to convert to CAT operation (which requires that the recursion operate from the bottom upwards). The considerably more sophisticated D0L algorithm developed later does it all --- inversion, log time, etc. WFL On 11/12/08, Joerg Arndt <arndt@jjj.de> wrote:
Btw. an implementation of Lunnon's algorithm is online at http://www.jjj.de/fxt/demo/comb/#hilbert-ndim
I find that one, uhm, awesome.
* Steve Witham <sw@tiac.net> [Nov 12. 2008 12:34]:
In late August Fred Lunnon asked some questions about Hilbert walks in more than 2D. One of the questions was just, how do you map between the index of a point along the walk, and the coordinates of that point, if possible in a log-time way?
Some suggested it was simple, but as far as I know, none of the simple ideas actually generates a Hilbert-style walk.
I wrote privately to Fred that it *must* be simple ("trivial" is what I said, actually).
It's exactly two months from the date I wrote that, and I have working (though not at all optimized) code and a draft of a description of how it works up at http://www.tiac.net/~sw/2008/10/Hilbert
I would appreciate critique.
--humbled Steve
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 11/12/08, Joerg Arndt <arndt@jjj.de> wrote: Btw. an implementation of Lunnon's algorithm is online at http://www.jjj.de/fxt/demo/comb/#hilbert-ndim
I find that one, uhm, awesome.
wfl>It ought to be pointed out that these two are implementations
of the "simple-minded" algorithm I developed first --- but then found impossible to convert to CAT operation (which requires that the recursion operate from the bottom upwards).
The considerably more sophisticated D0L algorithm developed later does it all --- inversion, log time, etc. WFL
Not quite all. For the 3D case, (* Exactly and continuously map [0,1] onto [0,1]^3 (rationals). Treano redefines itself twice, calls itself in eight places, and has no discernable termination condition. *) I3=IdentityMatrix[3];$RecursionLimit = Infinity; Treano[t_, a1_:I3, a0_:{0,0,0}] := Treano[t, b1_:I3, b0_:{0,0,0}] = (Treano[t, s1_:I3, s0_:{0,0,0}] := (a0 - s0).Inverse[s1 - a1]; Module[{t8 = 8*t, n}, n = Floor[t8]; t8 -= n; Switch[n, 0, Treano[t8, a1[[{1,3,2}]]/2, a0][[{1,3,2}]]/2, 1, ({1,1,0}+{-1,1,1}Treano[t8,{1,-1,1}a1[[{2,1,3}]]/2,a0+{1,1,0}.a1/2][[{2,1,3}]])/2, 2, ({1,2,1}+{-1,-1,1}Treano[t8,{-1,-1,1}a1[[{2,1,3}]]/2,a0+{1,2,1}.a1/2][[{2,1,3}]])/2, 3, ({1,1,2}-Treano[t8,-a1[[{2,1,3}]]/2,a0+{1,1,2}.a1/2][[{2,1,3}]])/2, 4, ({1,0,1}+{1,1,-1}Treano[t8,{1,1,-1}a1[[{2,1,3}]]/2,a0+{1,0,1}.a1/2][[{2,1,3}]])/2, 5, ({1,1,0}+Treano[t8,a1[[{2,1,3}]]/2,a0+{1,1,0}.a1/2][[{2,1,3}]])/2, 6, ({1,2,1}+{1,-1,1}Treano[t8,{-1,1,1}a1[[{2,1,3}]]/2,a0+{1,2,1}.a1/2][[{2,1,3}]])/2, 7, ({1,1,2}+{1,-1,-1}Treano[t8,{-1,-1,1}a1[[{2,3,1}]]/2,a0+{1,1,2}.a1/2][[{3,1,2}]])/2, 8, {1,0,1}]]) Nevertheless, MatrixForm[Table[{t,Treano[t]}, {t, {0, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 2/5, 3/7, 1/2, 4/7, 3/5, 2/3, 3/4, 4/5, 5/6, 6/7, 1}}]] 0 {0, 0, 0} 1 1 3 - {-, -, 0} 7 5 5 1 1 3 1 - {-, -, -} 6 5 5 3 1 1 - {-, 1, 0} 5 3 1 1 1 - {-, 1, -} 4 2 2 2 - {0, 1, 1} 7 1 1 3 2 - {-, -, -} 3 5 5 3 2 1 - {0, -, 1} 5 3 3 1 1 2 - {-, -, -} 7 3 3 3 1 1 1 - {-, 0, -} 2 2 2 4 2 1 1 - {-, -, -} 7 3 3 3 3 1 - {1, -, 0} 5 3 2/3 {4/5, 3/5, 1/3} 3 1 1 - {-, 1, -} 4 2 2 4 2 - {-, 1, 1} 5 3 5 4 3 2 - {-, -, -} 6 5 5 3 6 4 3 - {-, -, 1} 7 5 5 1 {1, 0, 1} Treano[7/22] {444818/1048577, 637363/1048577, 564/1025} The next three "lines" prp[p_]:=Block[{q=If[p[[1]]^2>p[[2]]^2,{-p[[3]],0,p[[1]]},{0,p[[3]],-p[[2]]}]},q*Sqrt[(p.p)/(q.q)]] Stick[p_,q_]:=Block[{m=(p+q)/2,d=prp[q-p]/16,e},e=Cross[q-p,d]/Norm[q-p]; Table[Polygon[{r,m+Cos[2*(k-1)*Pi/3]*d+Sin[2*(k-1)*Pi/3]*e, m+Cos[2*k*Pi/3]*d+Sin[2*k*Pi/3]*e}],{r,{p,q}},{k,3}]] Graphics3D[ Table[Stick[Treano[(k + 1/3)/256], Treano[(k + 4/3)/256]], {k,0,254}]] produce the graphic at http://gosper.org/treano.png . So SW's intial assessment was correct: trivial. --rwg
* Steve Witham <sw@tiac.net> [Nov 12. 2008 12:34]:
In late August Fred Lunnon asked some questions about Hilbert walks in more than 2D. One of the questions was just, how do you map between the index of a point along the walk, and the coordinates of that point, if possible in a log-time way?
Some suggested it was simple, but as far as I know, none of the simple ideas actually generates a Hilbert-style walk.
I wrote privately to Fred that it *must* be simple ("trivial" is what I said, actually).
It's exactly two months from the date I wrote that, and I have working (though not at all optimized) code and a draft of a description of how it works up at http://www.tiac.net/~sw/2008/10/Hilbert
I would appreciate critique.
--humbled Steve
participants (4)
-
Fred lunnon -
Joerg Arndt -
rwg＠sdf.lonestar.org -
Steve Witham