Only in v6: .copied
diff rc v4/Makefile v6/Makefile
*** v4/Makefile Tue Nov 11 08:06:26 2008
 v6/Makefile Sun Nov 16 19:27:53 2008
***************
*** 1,14 ****
! all: Pub/Done
! PUBFILES=index.html makeindex.php.txt hilbert.py hilbert_test.py \
! hilbert_thumb.gif
! Pub/Done: ${PUBFILES}
cp ${PUBFILES} Pub
! touch Pub/Done
! index.html: makeindex.php.txt
rm f index.html
touch datefile
php makeindex.php.txt >index.html
chmod aw index.html
 1,33 
! all: Pub/.copied
! VER=v6
! SOURCES=makeindex.php.txt hilbert.py hilbert_test.py hilbert_pic.py \
! Makefile
!
! DIFFS=v4_${VER}_diff.txt v5_${VER}_diff.txt
!
! PUBFILES=${SOURCES} ${DIFFS} index.html hilbert_thumb.gif hilbert_pic.pdf
!
! v4_${VER}_diff.txt: old/${VER}/.copied
! (cd old; diff rc v4 ${VER} >../v4_${VER}_diff.txt; true)
!
! v5_${VER}_diff.txt: old/${VER}/.copied
! (cd old; diff rc v5 ${VER} >../v5_${VER}_diff.txt; true)
!
! old/${VER}/.copied: ${SOURCES}
! cp ${SOURCES} old/${VER}
! touch old/${VER}/.copied
!
! Pub/.copied: ${PUBFILES}
cp ${PUBFILES} Pub
! touch Pub/.copied
! index.html: ${SOURCES} ${DIFFS}
rm f index.html
touch datefile
php makeindex.php.txt >index.html
chmod aw index.html
+
+ hilbert_pic.pdf: hilbert.py hilbert_pic.py
+ hilbert_pic.py >hilbert_pic.pdf
diff rc v4/hilbert.py v6/hilbert.py
*** v4/hilbert.py Sat Nov 8 16:19:26 2008
 v6/hilbert.py Sun Nov 16 19:27:53 2008
***************
*** 4,9 ****
 4,11 
# int_to_Hilbert( 0, nD ) ==> ( 0, 0, 0, ... 0 ) Start at origin.
# int_to_Hilbert( 1, nD ) ==> ( 1, 0, 0, ... 0 ) 1st step is along x.
# Hilbert_to_int( ( x, y, z ) ) ==> i
+ # Steve Witham ess doubleyou at tiac removethis dot net.
+ # http://www.tiac.net/~sw/2008/10/Hilbert
from sys import argv
***************
*** 39,62 ****
def initial_start_end( nChunks, nD ):
# This orients the largest cube so that
# the first step is along the x axis, regardless of nD and nChunks:
return 0, 2**( ( nChunks  1 ) % nD ) # in Python 0 <= a % b < b.
# Unpacking arguments and packing results of int <> Hilbert functions.
# nD == # of dimensions.
! # A "chunk" is an nDbit int (or Python long, i.e. bignum).
! # Arrays of chunks are highestorder first.
# Bits within "coord chunks" are x highestorder, y next, etc.,
# i.e., the same order as coordinates input to Hilbert_to_int()
# and output from int_to_Hilbert().
! ## unpack_index( int, nD ) > array of index chunks.
#
def unpack_index( i, nD ):
! p = 2**nD # Chunks are digits mod 2**nD.
! nChunks = max( 1, int( ceil( log( i + 1, p ) ) ) ) # # of digits
chunks = [ 0 ] * nChunks
for j in range( nChunks  1, 1, 1 ):
chunks[ j ] = i % p
 41,65 
def initial_start_end( nChunks, nD ):
# This orients the largest cube so that
+ # its start is the origin (0 corner), and
# the first step is along the x axis, regardless of nD and nChunks:
return 0, 2**( ( nChunks  1 ) % nD ) # in Python 0 <= a % b < b.
# Unpacking arguments and packing results of int <> Hilbert functions.
# nD == # of dimensions.
! # A "chunk" is an nDbit int (or Python long, aka bignum).
! # Lists of chunks are highestorder first.
# Bits within "coord chunks" are x highestorder, y next, etc.,
# i.e., the same order as coordinates input to Hilbert_to_int()
# and output from int_to_Hilbert().
! ## unpack_index( int index, nD ) > list of index chunks.
#
def unpack_index( i, nD ):
! p = 2**nD # Chunks are like digits in base 2**nD.
! nChunks = max( 1, int( ceil( log( i + 1, p ) ) ) ) # # of digits
chunks = [ 0 ] * nChunks
for j in range( nChunks  1, 1, 1 ):
chunks[ j ] = i % p
***************
*** 68,74 ****
return reduce( lambda n, chunk: n * p + chunk, chunks )
! ## unpack_coords( array of nD coords ) > array of coord chunks each nD bits.
def unpack_coords( coords ):
nD = len( coords )
biggest = reduce( max, coords ) # the max of all coords
 71,77 
return reduce( lambda n, chunk: n * p + chunk, chunks )
! ## unpack_coords( list of nD coords ) > list of coord chunks each nD bits.
def unpack_coords( coords ):
nD = len( coords )
biggest = reduce( max, coords ) # the max of all coords
***************
*** 79,89 ****
return transpose_bits( chunks, nD )
! ## transpose_bits  Given nSrcs source ints each nDests bits long,
! # return nDests ints each nSrcs bits long.
! # Like a matrix transpose where ints are rows and bits are columns.
! # Earlier srcs become higher bits in dests;
! # earlier dests come from higher bits of srcs.
def transpose_bits( srcs, nDests ):
srcs = list( srcs ) # Make a copy we can modify safely.
nSrcs = len( srcs )
 82,93 
return transpose_bits( chunks, nD )
! ## transpose_bits 
! # Given nSrcs source ints each nDests bits long,
! # return nDests ints each nSrcs bits long.
! # Like a matrix transpose where ints are rows and bits are columns.
! # Earlier srcs become higher bits in dests;
! # earlier dests come from higher bits of srcs.
def transpose_bits( srcs, nDests ):
srcs = list( srcs ) # Make a copy we can modify safely.
nSrcs = len( srcs )
Only in v6: hilbert_pic.py
diff rc v4/hilbert_test.py v6/hilbert_test.py
*** v4/hilbert_test.py Sat Nov 8 16:19:27 2008
 v6/hilbert_test.py Sun Nov 16 19:27:53 2008
***************
*** 117,153 ****
child_start_end_test( nbits )
! def check_visited( visited, prefix, size, nD ):
if nD > 0:
! for i in range( size ):
! check_visited( visited, prefix + [i], size, nD  1 )
else:
if not tuple( prefix ) in visited:
print "missing", prefix
! def int_to_Hilbert_test( n, nD ):
! ld = int( n ** (1./nD) )
! assert ld ** nD == n
visited = {}
for i in range( n ):
pt = tuple( int_to_Hilbert( i, nD ) )
! print pt,
! visited[ pt ] = True
j = Hilbert_to_int( pt )
if j != i:
print "BZZT, decodes to", j,
! if i > 0:
nDiffs = sum( [ pt[k] != prev_pt[k] for k in range( nD ) ] )
if nDiffs != 1:
print "BZZT, different along", nDiffs, "dimensions",
maxDiff = max( [ abs(pt[k]  prev_pt[k]) for k in range( nD ) ] )
if maxDiff != 1:
print "BZZT, max difference is", maxDiff,
prev_pt = pt
! if ( i + 1 ) % 8 == 0:
! print
! check_visited( visited, [], ld, nD )
if argv[0].endswith( "/hilbert_test.py" ) or argv[0] == "hilbert.py":
 117,173 
child_start_end_test( nbits )
! ## check_visited  Check that every point in the cube was visited.
! #
! # visited is a dictionary (or "hash" or associative array) whose key
! # is a tuple representing the point coordinates. Prefix is a list
! # of coordinates that's built up by recursion to the right number of
! # dimensions. "tuple(prefix) in visited" converts the list to a tuple
! # and asks whether an entry with that key is in the dictionary.
! def check_visited( visited, prefix, linear_size, nD ):
if nD > 0:
! for i in range( linear_size ):
! check_visited( visited, prefix + [i], linear_size, nD  1 )
else:
if not tuple( prefix ) in visited:
print "missing", prefix
! def tuple_print_width( n ): # tuple with n 1digit numbers and trailing sp
! if n == 0: return 3 # ()_
! if n == 1: return 5 # (1,)_ special case
! else: return n * 3 + 1
!
!
! def int_to_Hilbert_test( n, nD, doPrint=True ):
! tups_per_line = 2**( int( log( 80 / tuple_print_width( nD ), 2 ) ) )
! linear_size = int( ( n + .5 ) ** (1./nD) )
! isCube = linear_size ** nD == n
! if not isCube:
! print "(This is not a complete cube:)"
visited = {}
for i in range( n ):
pt = tuple( int_to_Hilbert( i, nD ) )
! if doPrint: print pt,
! visited[ pt ] = True # Add pt to "visited" dictionary.
j = Hilbert_to_int( pt )
if j != i:
print "BZZT, decodes to", j,
!
! if i > 0: # Check that we have stepped one unit, along one dim:
nDiffs = sum( [ pt[k] != prev_pt[k] for k in range( nD ) ] )
if nDiffs != 1:
print "BZZT, different along", nDiffs, "dimensions",
maxDiff = max( [ abs(pt[k]  prev_pt[k]) for k in range( nD ) ] )
if maxDiff != 1:
print "BZZT, max difference is", maxDiff,
+
prev_pt = pt
! if ( i + 1 ) % tups_per_line == 0:
! if doPrint: print
!
! if isCube:
! check_visited( visited, [], linear_size, nD )
if argv[0].endswith( "/hilbert_test.py" ) or argv[0] == "hilbert.py":
***************
*** 159,168 ****
print
int_to_Hilbert_test( 64, 3 )
print
for nD in [ 2, 3, 4, 5 ]:
pt = [ 0 ] * nD
! pt[0] = 1000000
x = Hilbert_to_int( pt )
print x, log( x, 10 )
! print int_to_Hilbert( 1000000, nD )
 179,205 
print
int_to_Hilbert_test( 64, 3 )
print
+ int_to_Hilbert_test( 4096, 3, doPrint=False ) # nChunks > nD
+ print
+ int_to_Hilbert_test( 4096, 4, doPrint=False )
+ print
+ k = 10**12 # definitely a long
for nD in [ 2, 3, 4, 5 ]:
+ # Decode point ( k, 0, 0... ) to an int...how many digits?:
pt = [ 0 ] * nD
! pt[0] = k
x = Hilbert_to_int( pt )
print x, log( x, 10 )
! # Doublecheck:
! pt2 = list( int_to_Hilbert( x, nD ) )
! if pt2 != pt:
! print "BZZT! Encodes to ", pt2
!
! # Encode k to an nD point:
! pt = int_to_Hilbert( k, nD )
! print pt
! # Doublecheck:
! y = Hilbert_to_int( pt )
! if y != k:
! print "BZZT! Decodes to", y
diff rc v4/makeindex.php.txt v6/makeindex.php.txt
*** v4/makeindex.php.txt Sat Nov 8 16:19:28 2008
 v6/makeindex.php.txt Sun Nov 16 19:27:53 2008
***************
*** 23,30 ****
Hilbert Curves in More (or fewer) than Two Dimensions
! version 0.4
Let's develop Python functions to map between a point on a
 23,42 
+
+
+
+
+
!
!
+ 
+
Hilbert Curves in More (or fewer) than Two Dimensions
! version 0.6
! 
!
Let's develop Python functions to map between a point on a
***************
*** 77,87 ****
most significant bit x, the next (if any) y, and so forth
(punting on what the bits after z are called).
In this walk,
! 12
!  
! 0 3
! the first step is along the y axis, but we'll say the walk
! as a whole travels along the x axis.
"Travel," here, means the difference between
the beginning and end of the walk of a cube (here a 2cube).
When D>1, the travel of a unit Dcube walk is always along a different
 89,99 
most significant bit x, the next (if any) y, and so forth
(punting on what the bits after z are called).
In this walk,! 32
! 
! 01
! the first step is along the x axis, but we'll say the walk
! as a whole travels along the y axis.
"Travel," here, means the difference between
the beginning and end of the walk of a cube (here a 2cube).
When D>1, the travel of a unit Dcube walk is always along a different
***************
*** 126,134 ****
For D=2 (and D=1), there is only one Gray code for a given travel,
and only one way to orient the subsquares within the larger walk.
! For D>2, there are many
! possible walks of a unit cube, and many combinations of subcube
! orientations that are compatible with a given parent walk.
We won't go into all these possibilities except to point out that
the code being described here effectively represents a set of
arbitrary choices about the shape of the walk.
 138,146 
For D=2 (and D=1), there is only one Gray code for a given travel,
and only one way to orient the subsquares within the larger walk.
! For D>2, there is more than one
! possible walk of a unit cube, and some (all?) parent walks are compatible
! with multiple combinations of subcube orientations.
We won't go into all these possibilities except to point out that
the code being described here effectively represents a set of
arbitrary choices about the shape of the walk.
***************
*** 154,174 ****
coordinates:
!  "Unpack" the index into a list of h Dbit ints.
!  h is the number of levels of
recursion (in our case the number of times to loop); from this
calculate the orientation of the overall cube.
! Then, for each number in the list, starting at the most
significant,
!  Use a modified Gray code to convert the D bits of index into
! a Dbit output int with one bit destined for each of the D
! coordinates,
 Calculate the start and end corners for the child cube
! to which the indexed point belongs,
 Loop to do the child cube.
 166,188 
coordinates:
!  "Unpack" the index into a list of h Dbit ints
! (called "index chunks").
!  h will be the number of levels of
recursion (in our case the number of times to loop); from this
calculate the orientation of the overall cube.
! Then, for each index chunk, starting at the most
significant,
!  Use a modified Gray code to convert the index chunk into
! a Dbit "coordinate chunk" with one bit destined for each of
! the D
! coordinates;
 Calculate the start and end corners for the child cube
! to which the indexed point belongs;
 Loop to do the child cube.
***************
*** 176,182 ****
 "Pack" the output coordinates by redistributing the D bits from
! each of h output ints into D ints, each with h bits.
 190,197 
 "Pack" the output coordinates by redistributing the D bits from
! each of h coordinate chunks into D ints,
! each with h bits.
***************
*** 320,328 ****
the bottomlevel cube at the origin has a fixed orientation.
! We pin the problem down by saying that the point with index zero is
the origin point,
! and that the first step is in the x direction.
With our modified Gray code, that means the first level zero unit cube
travels the y dimension.
Our child orientation method always makes the first child of a parent
 335,343 
the bottomlevel cube at the origin has a fixed orientation.
! We decree that the point with index zero is
the origin point,
! and that the first step shall be in the x direction.
With our modified Gray code, that means the first level zero unit cube
travels the y dimension.
Our child orientation method always makes the first child of a parent
***************
*** 337,342 ****
 352,358 
def initial_start_end( nChunks, nD ):
# This orients the largest cube so that
+ # it's start is the origin (0 corner), and
# the first step is along the x axis, regardless of nD and nChunks:
return 0, 2**( ( nChunks  1 ) % nD ) # in Python 0 <= a % b < b.
***************
*** 347,360 ****
$cmt = array(
"hilbert.py" => "index <==> Hilbert and support functions.",
"hilbert_test.py" => "Tests hilbert.py functions for 1 to 3 dimensions.",
! "makeindex.php.txt" => "PHP script that inserts this listing."
);
$subst_url = array(
);
echo "\n";
! exec( "/bin/ls ld hilbert.py hilbert_test.py *.php.txt", $lines );
foreach( $lines as $line ) {
echo "\n";
$parts=explode( " ", $line );
 363,378 
$cmt = array(
"hilbert.py" => "index <==> Hilbert and support functions.",
"hilbert_test.py" => "Tests hilbert.py functions for 1 to 3 dimensions.",
! "makeindex.php.txt" => "PHP source for this page (inserts this listing).",
! "hilbert_pic.pdf" => "Exploded views of 3D Hilbert walks.",
! "hilbert_pic.py" => "Python/pdfgen code that generates hilbert_pic.pdf"
);
$subst_url = array(
);
echo "\n";
! exec( "/bin/ls ld hilbert.py hilbert_test.py makeindex.php.txt *diff.txt hilbert_pic.py hilbert_pic.pdf", $lines );
foreach( $lines as $line ) {
echo "\n";
$parts=explode( " ", $line );
***************
*** 390,398 ****
Python tuples, like
( x, y, z )
! are arrays that can't be modified once created. They can be
passed as arguments, returned from functions, and indexed like
! arrays. They are sometimes implicit in the syntax for multiple
assignment or returning multiple values from functions. E.g.
point = ( x, y, z )
 408,416 
Python tuples, like
( x, y, z )
! are lists that can't be modified once created. They can be
passed as arguments, returned from functions, and indexed like
! lists. They are sometimes implicit in the syntax for multiple
assignment or returning multiple values from functions. E.g.
point = ( x, y, z )
***************
*** 405,412 ****
x, y, z = f( point )
x = point[ 0 ]
number_of_dimensions = len( point )

"Lists" in Python are actually onedimensional packed arrays.
They are like tuples, but modifiable, so,
 423,433 
x, y, z = f( point )
x = point[ 0 ]
number_of_dimensions = len( point )
+ I use tuples for points where I can here just because they
+ look like points.
+
+
"Lists" in Python are actually onedimensional packed arrays.
They are like tuples, but modifiable, so,
***************
*** 414,421 ****
a[ 1 ] = a[ 0 ] + a[ 1]
x, y = a
! I use tuples for points where I can here just because they
! look like points.
In Python, the bitwise operations on ints and longs are:
 435,443 
a[ 1 ] = a[ 0 ] + a[ 1]
x, y = a
!
! The expression "[0] * n" means n copies of a list of one zero,
! concatenated together in other words a list of n zeroes.
In Python, the bitwise operations on ints and longs are: