blob: ac1743c805fb30ecc70134416a3e073105dcb2c6 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
|
@code{(require 'hilbert-fill)}
@ftindex hilbert-fill
@noindent
@cindex Hilbert
@cindex Space-Filling
The @dfn{Hilbert Space-Filling Curve} is a one-to-one mapping
@cindex Hilbert Space-Filling Curve
between a unit line segment and an @var{n}-dimensional unit cube.
This implementation treats the nonnegative integers either as
fractional bits of a given width or as nonnegative integers.
@noindent
The integer procedures map the non-negative integers to an
arbitrarily large @var{n}-dimensional cube with its corner at the
origin and all coordinates are non-negative.
@noindent
For any exact nonnegative integer @var{scalar} and exact integer
@var{rank} > 2,
@example
(= @var{scalar} (hilbert-coordinates->integer
(integer->hilbert-coordinates @var{scalar} @var{rank})))
@result{} #t
@end example
When treating integers as @var{k} fractional bits,
@example
(= @var{scalar} (hilbert-coordinates->integer
(integer->hilbert-coordinates @var{scalar} @var{rank} @var{k})) @var{k})
@result{} #t
@end example
@defun integer->hilbert-coordinates scalar rank
Returns a list of @var{rank} integer coordinates corresponding to exact
non-negative integer @var{scalar}. The lists returned by @code{integer->hilbert-coordinates} for @var{scalar} arguments
0 and 1 will differ in the first element.
@defunx integer->hilbert-coordinates scalar rank k
@var{scalar} must be a nonnegative integer of no more than
@code{@var{rank}*@var{k}} bits.
@code{integer->hilbert-coordinates} Returns a list of @var{rank} @var{k}-bit nonnegative integer
coordinates corresponding to exact non-negative integer @var{scalar}. The
curves generated by @code{integer->hilbert-coordinates} have the same alignment independent of
@var{k}.
@end defun
@defun hilbert-coordinates->integer coords
@defunx hilbert-coordinates->integer coords k
Returns an exact non-negative integer corresponding to @var{coords}, a list
of non-negative integer coordinates.
@end defun
@subsubsection Gray code
@cindex Gray code
@noindent
A @dfn{Gray code} is an ordering of non-negative integers in which
@cindex Gray code
exactly one bit differs between each pair of successive elements. There
are multiple Gray codings. An n-bit Gray code corresponds to a
Hamiltonian cycle on an n-dimensional hypercube.
@noindent
Gray codes find use communicating incrementally changing values between
asynchronous agents. De-laminated Gray codes comprise the coordinates
of Hilbert space-filling curves.
@defun integer->gray-code k
Converts @var{k} to a Gray code of the same @code{integer-length} as
@var{k}.
@defunx gray-code->integer k
Converts the Gray code @var{k} to an integer of the same
@code{integer-length} as @var{k}.
For any non-negative integer @var{k},
@example
(eqv? k (gray-code->integer (integer->gray-code k)))
@end example
@end defun
@defun = k1 k2
@defunx gray-code<? k1 k2
@defunx gray-code>? k1 k2
@defunx gray-code<=? k1 k2
@defunx gray-code>=? k1 k2
These procedures return #t if their Gray code arguments are
(respectively): equal, monotonically increasing, monotonically
decreasing, monotonically nondecreasing, or monotonically nonincreasing.
For any non-negative integers @var{k1} and @var{k2}, the Gray code
predicate of @code{(integer->gray-code k1)} and
@code{(integer->gray-code k2)} will return the same value as the
corresponding predicate of @var{k1} and @var{k2}.
@end defun
@subsubsection Bitwise Lamination
@cindex lamination
@defun bitwise-laminate k1 @dots{}
@defunx bitwise-delaminate count k
Returns an integer composed of the bits of @var{k1} @dots{} interlaced
in argument order. Given @var{k1}, @dots{} @var{kn}, the n low-order
bits of the returned value will be the lowest-order bit of each
argument.
@defunx bitwise-laminate count k
Returns a list of @var{count} integers comprised of every @var{count}h
bit of the integer @var{k}.
@example
(map (lambda (k) (number->string k 2))
(bitwise-delaminate 4 #x7654))
@result{} ("0" "1111" "1100" "1010")
(number->string (bitwise-laminate 0 #b1111 #b1100 #b1010) 16)
@result{} "7654"
@end example
For any non-negative integers @var{k} and @var{count}:
@example
(eqv? k (bitwise-laminate (bitwise-delaminate count k)))
@end example
@end defun
@defun delaminate-list count ks
Returns a list of @var{count} integers comprised of the @var{j}th
bit of the integers @var{ks} where @var{j} ranges from @var{count}-1
to 0.
@example
(map (lambda (k) (number->string k 2))
(delaminate-list 4 '(7 6 5 4 0 0 0 0)))
@result{} ("0" "11110000" "11000000" "10100000")
@end example
@code{delaminate-list} is its own inverse:
@example
(delaminate-list 8 (delaminate-list 4 '(7 6 5 4 0 0 0 0)))
@result{} (7 6 5 4 0 0 0 0)
@end example
@end defun
|
