Only in v6.2: .copied diff -rc v4/Makefile v6.2/Makefile *** v4/Makefile Tue Nov 11 08:06:26 2008 --- v6.2/Makefile Wed Nov 19 21:12:25 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 a-w index.html --- 1,36 ---- ! all: Pub/.copied ! VERNUM=6.2 ! PREVNUM=6.1 ! VER=v${VERNUM} ! PREV=v${PREVNUM} ! SOURCES=makeindex.php.txt hilbert.py hilbert_test.py hilbert_pic.py \ ! Makefile ! ! DIFFS=v4_${VER}_diff.txt ${PREV}_${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) ! ! ${PREV}_${VER}_diff.txt: old/${VER}/.copied ! (cd old; diff -rc ${PREV} ${VER} >../${PREV}_${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 ${VERNUM} >index.html chmod a-w index.html + + hilbert_pic.pdf: hilbert.py hilbert_pic.py + hilbert_pic.py >hilbert_pic.pdf diff -rc v4/hilbert.py v6.2/hilbert.py *** v4/hilbert.py Sat Nov 8 16:19:26 2008 --- v6.2/hilbert.py Wed Nov 19 21:12:25 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 remove-this 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 nD-bit int (or Python long, i.e. bignum). ! # Arrays of chunks are highest-order first. # Bits within "coord chunks" are x highest-order, 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 nD-bit int (or Python long, aka bignum). ! # Lists of chunks are highest-order first. # Bits within "coord chunks" are x highest-order, 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.2: hilbert_pic.py diff -rc v4/hilbert_test.py v6.2/hilbert_test.py *** v4/hilbert_test.py Sat Nov 8 16:19:27 2008 --- v6.2/hilbert_test.py Wed Nov 19 21:12:25 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 1-digit 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 ) ! # Double-check: ! 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 ! # Double-check: ! y = Hilbert_to_int( pt ) ! if y != k: ! print "BZZT! Decodes to", y diff -rc v4/makeindex.php.txt v6.2/makeindex.php.txt *** v4/makeindex.php.txt Sat Nov 8 16:19:28 2008 --- v6.2/makeindex.php.txt Wed Nov 19 21:12:25 2008 *************** *** 1,5 **** index.html ?>