* 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