[math-fun] gray code and hilbert curve connection
The D-hypercube has 2^D vertices that are the D-bit binary words. A "gray code" is a hamiltonian tour on those 2^D vertices using edges to nearest neighbors only, i.e. each gray word differs from predecessor at a single bit. There are many gray codes when D is large, but some are nicer and easier to deal with than others. A Hilbert curve is a space filling curve filling the D-hypercube at unit density i.e. maps the real interval [0,1] into the cube continuously. To do it, partition [0,1] into 2^D equal subintervals, each is mapped into one of the 2^D corner half-size subcubes via a re-scaled Hilbert curve. The subcubes are ordered in gray code order. The key is to rotate and/or flip each subcube appropriately (by permuting and/or negating the D coordinates) so all the little half hilberts stitch together to make a full hilbert. OK, understand now? Now to make good elegant efficient program for this, it would if we had a fast simple routine to compute the Nth gray-word and which bit changes to reach its successor (or predecessor). I'm rather ignorant about grayness, but google found the following brilliant: uint gray(uint N){ return( N ^ (N >> 1) ); } will return the Nth gray code word! To translate that C code into english: unsigned integer gray(unsigned integer N){ return( N XOR RightShift(N) ); } I believe in a recent mathfun post it was explained how to produce the inverse of this function in O(log(D)) runtime... The goal is good hilbert code that fits on 1 page or less. It is desirable to have inverse routine too, i.e. inputs D coordinates and outputs t. The Peano-Smith curve seems way simpler than Hilbert and also basically unique (unlike hilbert which because gray codes are very non-unique, are too). But Peano-Smith naturally lives in a hyper-rectangle with edge lengths 3^(k/D) for k=1..D, not a hypercube. Needless to say, the appropriate name for D-dimensional hilbert is "Dilbert." -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
On 11/14/13, Warren D Smith <warren.wds@gmail.com> wrote:
... The goal is good hilbert code that fits on 1 page or less. It is desirable to have inverse routine too, i.e. inputs D coordinates and outputs t.
There was extensive discussion of Hilbert walks in hyperspace on math-fun during Sep-Oct 2008, including contributions from Joerg Arndt, Steve Witham, Thomas Colthurst, and myself. The outcome was an efficient algorithm based on D0L systems, implemented in Maple and Java (by WFL) and translated to C (by JJA --- see his fxtbook?). Precompiling the state-change tables is an option, improving speed by 20% -- 25% over dynamic evaluation. Excluding comments, the program code for jumping to a given step and (inversely) to a given coordinate occupy together approximately 40 lines. A summary of the algorithm is available as a text file. Be warned that published accounts of similar algorithms, from Arthur Butz (1971) onwards, tend towards the incomprehensibly terse (including mine). See also http://people.csail.mit.edu/jaffer/Geometry/HSFC [Scheme program] http://web.archive.org/web/20050204100342/http://www.caam.rice.edu/~dougm/tw... [C program] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.9640 http://arxiv.org/pdf/1109.2323v1.pdf [Recent survey] Fred Lunnon
* Fred Lunnon <fred.lunnon@gmail.com> [Nov 15. 2013 18:28]:
On 11/14/13, Warren D Smith <warren.wds@gmail.com> wrote:
... The goal is good hilbert code that fits on 1 page or less. It is desirable to have inverse routine too, i.e. inputs D coordinates and outputs t.
There was extensive discussion of Hilbert walks in hyperspace on math-fun during Sep-Oct 2008, including contributions from Joerg Arndt, Steve Witham, Thomas Colthurst, and myself. The outcome was an efficient algorithm based on D0L systems, implemented in Maple and Java (by WFL) and translated to C (by JJA --- see his fxtbook?).
Sadly not in the fxtbook! But see http://jjj.de/fxt/demo/comb/index.html#wfl-hilbert (older routines are http://jjj.de/fxt/demo/comb/index.html#hilbert-ndim and http://jjj.de/fxt/demo/comb/index.html#hilbert-ndim-rec and http://jjj.de/fxt/demo/comb/index.html#stringsubst-hilbert3d ) Is there anyone on this planet who understands wfl-hilbert ?
[...]
@WDS: easy Peano mappings exist for all odd side-lengths of hypercubes. Best, jj
Joerg asked << Is there anyone on this planet who understands wfl-hilbert ? >> Well, I THINK I managed to figure out how it worked again, last time I tried to read my own documentation and realised the latter required extensive further clarification (supplied) ... But an earlier algorithm (jump_TOPDOWN), later discarded because it could not be inverted, has defied every subsequent attempt to decipher it. Incidentally, 5 years ago several people opined that Hilbert in hyperspace was straightforward. One other (Steve Witham) eventually managed to craft a testable solution, by which time his estimation of its difficulty had been substantially revised. Certainly it is one of the knottier algorithmic design problems I have ever been sufficiently fortunate to solve. Fred Lunnon On 11/15/13, Joerg Arndt <arndt@jjj.de> wrote:
* Fred Lunnon <fred.lunnon@gmail.com> [Nov 15. 2013 18:28]:
On 11/14/13, Warren D Smith <warren.wds@gmail.com> wrote:
... The goal is good hilbert code that fits on 1 page or less. It is desirable to have inverse routine too, i.e. inputs D coordinates and outputs t.
There was extensive discussion of Hilbert walks in hyperspace on math-fun during Sep-Oct 2008, including contributions from Joerg Arndt, Steve Witham, Thomas Colthurst, and myself. The outcome was an efficient algorithm based on D0L systems, implemented in Maple and Java (by WFL) and translated to C (by JJA --- see his fxtbook?).
Sadly not in the fxtbook!
But see http://jjj.de/fxt/demo/comb/index.html#wfl-hilbert
(older routines are http://jjj.de/fxt/demo/comb/index.html#hilbert-ndim and http://jjj.de/fxt/demo/comb/index.html#hilbert-ndim-rec and http://jjj.de/fxt/demo/comb/index.html#stringsubst-hilbert3d )
Is there anyone on this planet who understands wfl-hilbert ?
[...]
@WDS: easy Peano mappings exist for all odd side-lengths of hypercubes.
Best, jj
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
* Fred Lunnon <fred.lunnon@gmail.com> [Nov 15. 2013 18:28]:
On 11/14/13, Warren D Smith <warren.wds@gmail.com> wrote:
... The goal is good hilbert code that fits on 1 page or less. It is desirable to have inverse routine too, i.e. inputs D coordinates and outputs t.
There was extensive discussion of Hilbert walks in hyperspace on math-fun during Sep-Oct 2008, including contributions from Joerg Arndt, Steve Witham, Thomas Colthurst, and myself. The outcome was an efficient algorithm based on D0L systems, implemented in Maple and Java (by WFL) and translated to C (by JJA --- see his fxtbook?).
Precompiling the state-change tables is an option, improving speed by 20% -- 25% over dynamic evaluation. Excluding comments, the program code for jumping to a given step and (inversely) to a given coordinate occupy together approximately 40 lines. A summary of the algorithm is available as a text file.
Do you mean the file starting --------------------------- Notes on Multidimensional Hilbert Walk Algorithm ________________________________________________ Draft version 2 Fred Lunnon, Maynooth 01/05/13 Hilbert walks _____________ An "l-cell" is defined as graph whose nodes are integer lattice points in d-space, and whose edges join nearest neighbours; the Cartesian coordinate components [x_i] of its nodes are bounded by 2^l y_i <= x_i < 2^l(y_i + 1) , where node [2^l y_i] is the "base" of the cell, and l is its "level". When l > 0 the cell may be partitioned in a natural fashion into 1-cells: [...] --------------------------- ? If so (sorry I forgot about it and) shall I put it into the FXT lib with pointers in demo and corresponding header file? Best, jj
Be warned that published accounts of similar algorithms, from Arthur Butz (1971) onwards, tend towards the incomprehensibly terse (including mine). See also http://people.csail.mit.edu/jaffer/Geometry/HSFC [Scheme program] http://web.archive.org/web/20050204100342/http://www.caam.rice.edu/~dougm/tw... [C program] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.9640 http://arxiv.org/pdf/1109.2323v1.pdf [Recent survey]
Fred Lunnon
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 11/17/13, Joerg Arndt <arndt@jjj.de> wrote:
... A summary of the algorithm is available as a text file.
Do you mean the file starting
---------------------------
Notes on Multidimensional Hilbert Walk Algorithm ________________________________________________
Draft version 2 Fred Lunnon, Maynooth 01/05/13
That's the one. Since you are apparently not receiving email from me, I have reposted the current version at https://www.dropbox.com/s/7ufa37uhs80r6h2/hilbert_draft_2%20copy.txt --- some feedback about its usefulness (or otherwise) would be welcome! WFL
* Fred Lunnon <fred.lunnon@gmail.com> [Nov 18. 2013 08:16]:
On 11/17/13, Joerg Arndt <arndt@jjj.de> wrote:
... A summary of the algorithm is available as a text file.
Do you mean the file starting
---------------------------
Notes on Multidimensional Hilbert Walk Algorithm ________________________________________________
Draft version 2 Fred Lunnon, Maynooth 01/05/13
That's the one. Since you are apparently not receiving email from me,
I do receive your email, just answered here (because last time several people sent me emails "WFL wants to sent you an email"...).
I have reposted the current version at https://www.dropbox.com/s/7ufa37uhs80r6h2/hilbert_draft_2%20copy.txt
Web page says: "Nothing Here The file you're looking for has been deleted or moved."
--- some feedback about its usefulness (or otherwise) would be welcome!
I dearly hope somebody can jump in, the Hilbert curve turns out to be my nemesis. I meanwhile have good intuition about the curves of the "dragon" type (including making "kronecker products" of them, split them into halves, and some more tricks). The Hilbert curve is(?) of a quite different type, traversing the underlying grid (completely and) without even touching its own corners (similar to the Gosper island). The 2D case is deceptively "simple"! Best (well, fail), jj
WFL
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Apologies: try https://www.dropbox.com/s/fd6mzsbcq4emt3n/hilbert_draft_2.txt To JJA --- by all means repost this on your site if you think it useful (?!) WFL On 11/18/13, Joerg Arndt <arndt@jjj.de> wrote:
* Fred Lunnon <fred.lunnon@gmail.com> [Nov 18. 2013 08:16]:
On 11/17/13, Joerg Arndt <arndt@jjj.de> wrote:
... A summary of the algorithm is available as a text file.
Do you mean the file starting
---------------------------
Notes on Multidimensional Hilbert Walk Algorithm ________________________________________________
Draft version 2 Fred Lunnon, Maynooth 01/05/13
That's the one. Since you are apparently not receiving email from me,
I do receive your email, just answered here (because last time several people sent me emails "WFL wants to sent you an email"...).
I have reposted the current version at https://www.dropbox.com/s/7ufa37uhs80r6h2/hilbert_draft_2%20copy.txt
Web page says:
"Nothing Here The file you're looking for has been deleted or moved."
--- some feedback about its usefulness (or otherwise) would be welcome!
I dearly hope somebody can jump in, the Hilbert curve turns out to be my nemesis.
I meanwhile have good intuition about the curves of the "dragon" type (including making "kronecker products" of them, split them into halves, and some more tricks).
The Hilbert curve is(?) of a quite different type, traversing the underlying grid (completely and) without even touching its own corners (similar to the Gosper island).
The 2D case is deceptively "simple"!
Best (well, fail), jj
WFL
_______________________________________________ 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
* Fred Lunnon <fred.lunnon@gmail.com> [Nov 18. 2013 16:48]:
Apologies: try https://www.dropbox.com/s/fd6mzsbcq4emt3n/hilbert_draft_2.txt
To JJA --- by all means repost this on your site if you think it useful (?!) WFL
Done: http://jjj.de/fxt/doc/wfl-hilbert-doc.txt Explicitly mentioned in http://jjj.de/fxt/ and in the source file ( wfl-hilbert.h ). Thanks, jj
[...]
participants (3)
-
Fred Lunnon -
Joerg Arndt -
Warren D Smith