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