1Math::PlanePath::ImaginUasreyrBaCsoen(t3r)ibuted Perl DoMcautmhe:n:tPaltainoenPath::ImaginaryBase(3)
2
6 Math::PlanePath::ImaginaryBase -- replications in four directions
7
9 use Math::PlanePath::ImaginaryBase;
10 my $path = Math::PlanePath::ImaginaryBase->new (radix => 4);
11 my ($x, $y) = $path->n_to_xy (123);
12
14 This is a simple pattern arising from complex numbers expressed in a
15 base i*sqrt(2) or other i*sqrt(r) base. Or equivalently by negabinary
16 encoded X,Y digits interleaved. The default radix=2 is
17 38 39 34 35 54 55 50 51 5
19 36 37 32 33 52 53 48 49 4
20 46 47 42 43 62 63 58 59 3
21 44 45 40 41 60 61 56 57 2
22 6 7 2 3 22 23 18 19 1
23 4 5 0 1 20 21 16 17 <- Y=0
24 14 15 10 11 30 31 26 27 -1
25 12 13 8 9 28 29 24 25 -2
26 ^
27 -2 -1 X=0 1 2 3 4 5
28 The pattern can be seen by dividing into blocks as follows,
30 +---------------------------------------+
32 | 38 39 34 35 54 55 50 51 |
33 | |
34 | 36 37 32 33 52 53 48 49 |
35 | |
36 | 46 47 42 43 62 63 58 59 |
37 | |
38 | 44 45 40 41 60 61 56 57 |
39 +---------+---------+-------------------+
40 | 6 7 | 2 3 | 22 23 18 19 |
41 | +----+----+ |
42 | 4 5 | 0 | 1 | 20 21 16 17 |
43 +---------+----+----+ |
44 | 14 15 10 11 | 30 31 26 27 |
45 | | |
46 | 12 13 8 9 | 28 29 24 25 |
47 +-------------------+-------------------+
48 After N=0 at the origin, N=1 replicates that single point to the right.
50 Then that pair repeats above as N=2 and N=3. Then that 2x2 block
51 repeats to the left as N=4 to N=7, then 4x2 repeated below as N=8 to
52 N=16. Then 4x4 to the right as N=16 to N=31, etc. Each repeat is 90
53 degrees further around. The relative layout and orientation of a sub-
54 part is unchanged when replicated.
55 Complex Base
57 This pattern arises from representing a complex number in "base"
58 i*sqrt(r). For an integer X,Y,
59 b = i*sqrt(r)
61 a[i] = 0 to r-1 digits
62 X+Y*i*sqrt(r) = a[k]*b^k + ... + a[2]*b^2 + a[1]*b + a[0]
64 and N is the a[i] digits in base r
66 N = a[k]*r^k + ... + a[2]*r^2 + a[1]*r + a[0]
68 The factor sqrt(r) makes the generated Y an integer. For actual use as
70 a number base that factor can be omitted and instead fractional digits
71 a[-1]*r^-1 etc used to reach smaller Y values, as for example in
72 Knuth's "quater-imaginary" system of base 2*i, being i*sqrt(4), with
73 digits 0,1,2,3. (Knuth Seminumerical Algorithms section 4.1 and CACM
74 1960 pp245-247.)
75 The powers of i in the base give the replication direction, so i^0=1
77 right, i^1=i up, i^2=-1 right, i^3=-i down, etc. The power of sqrt(r)
78 then spreads the replication in the respective direction. It takes two
79 steps to repeat horizontally and sqrt(r)^2=r hence the doubling of 1x1
80 to the right, 2x2 to the left, 4x4 to the right, etc, and similarly
81 vertically.
82 Negabinary
84 The way blocks repeat horizontally first to the right and then to the
85 left is per the negabinary system base b=-2.
86 X = x[k]*(-2)^k + ... + x[2]*(-2)^2 + x[1]*(-2) + x[0]
88 The effect is to represent any positive or negative X by a positive
90 integer index NX.
91 X, negabinary: ... -1 -2 0 1 2 3 4 5 ...
93 index NX: 2 3 0 1 6 7 4 5
94 Notice how the 0 point replicates to the right as 1 and then that pair
96 0,1 replicates to the left as 2,3. Then the block 2,3,0,1 repeats to
97 the right as 6,7,4,5 which the same order with 4 added to each. Then
98 the resulting block of eight repeats to the left similarly, in the same
99 order with 8 added to each.
100 The "ImaginaryBase" takes the indexes NX and NY of these negabinary
102 forms and forms N by interleaving the digits (bits) of NX and NY. That
103 interleaving is in the style of the "ZOrderCurve".
104 zX,zY = ZOrderCurve n_to_xy(N)
106 X = to_negabinary(zX)
107 Y = to_negabinary(zY)
108 X,Y equals ImaginaryBase n_to_xy(N)
109 The "ZOrderCurve" replicates blocks alternately right and up, whereas
111 for "ImaginaryBase" here it's right,up,left,down repeating.
112 Radix
114 The "radix" parameter controls the radix used to break N into X,Y. For
115 example radix 3 replicates to make 3x1, 3x3, 9x3, 9x9, etc blocks. The
116 replications are radix-1=2 copies of the preceding level at each stage,
117 radix => 3
119 +------------------------+-----------+
121 | 24 25 26 15 16 17 | 6 7 8 | 2
122 | | |
123 | 21 22 23 12 13 14 | 3 4 5 | 1
124 | +-----------+
125 | 18 19 20 9 10 11 | 0 1 2 | <- Y=0
126 +------------------------+-----------+
127 | 51 52 53 42 43 44 33 34 35 | -1
128 | |
129 | 48 49 50 39 40 41 30 31 32 | -2
130 | |
131 | 45 46 47 36 37 38 27 28 29 | -3
132 | |
133 | 78 79 80 69 70 71 60 61 62 | -4
134 | |
135 | 75 76 77 66 67 68 57 58 59 | -5
136 | |
137 | 72 73 74 63 64 65 54 55 56 | -6
138 +------------------------------------+
139 ^
140 -6 -5 -4 -3 -2 -1 X=0 1 2
141 X,Y are "negaternary" in this case, and similar negaradix base=-radix
143 for higher values.
144
146 See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
147 classes.
148 "$path = Math::PlanePath::ImaginaryBase->new ()"
150 "$path = Math::PlanePath::ImaginaryBase->new (radix => $r)"
151 Create and return a new path object.
152 "($x,$y) = $path->n_to_xy ($n)"
154 Return the X,Y coordinates of point number $n on the path. Points
155 begin at 0 and if "$n < 0" then the return is an empty list.
156 "($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)"
158 The returned range is exact, meaning $n_lo and $n_hi are the
159 smallest and biggest in the rectangle.
160 Level Methods
162 "($n_lo, $n_hi) = $path->level_to_n_range($level)"
163 Return "(0, $radix**$level - 1)".
164
166 Rectangle to N Range
167 The X and Y ranges can be treated separately and then interleaved,
168 NXmin,NXmax = negaradix range to cover x1..x2
170 NYmin,NYmax = negaradix range to cover y1..y2
171 Nmin = interleave digits NXmin, NYmin
173 Nmax = interleave digits NXmax, NYmax
174 If the NX,NY ranges are exact then the resulting Nmin,Nmax range is
176 exact.
177 An exact negaradix range can be calculated by digits high to low by
179 considering the range taken by the negaradix form. For example two
180 negaternary digits,
181 N digit 2 1 0
183 +---------+---------+---------+
184 N index | 6 7 8 | 3 4 5 | 0 1 2 |
185 +---------+---------+---------+
186 X negaternary -6 -5 -4 -3 -2 -1 0 1 2
187 ^
188 base
189 Taking the base=-90909...90 which is the lowest taken (where 9 is the
191 radix digit R-1), then the next digit of N is the position from X-base,
192 taken alternately reverse 2,1,0 as shown here or forward 0,1,2.
193
195 Entries in Sloane's Online Encyclopedia of Integer Sequences related to
196 this path include,
197 <http://oeis.org/A057300> (etc)
199 radix=2
201 A057300 permutation N at transpose Y,X (swap bit pairs)
202 radix=3
204 A163327 permutation N at transpose Y,X (swap trit pairs)
205 radix=4
207 A126006 permutation N at transpose Y,X (swap digit pairs)
208 radix=16
210 A217558 permutation N at transpose Y,X (swap digit pairs)
211
213 Math::PlanePath, Math::PlanePath::ImaginaryHalf,
214 Math::PlanePath::CubicBase, Math::PlanePath::ZOrderCurve
215
217 <http://user42.tuxfamily.org/math-planepath/index.html>
218
220 Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018 Kevin Ryde
221 Math-PlanePath is free software; you can redistribute it and/or modify
223 it under the terms of the GNU General Public License as published by
224 the Free Software Foundation; either version 3, or (at your option) any
225 later version.
226 Math-PlanePath is distributed in the hope that it will be useful, but
228 WITHOUT ANY WARRANTY; without even the implied warranty of
229 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
230 General Public License for more details.
231 You should have received a copy of the GNU General Public License along
233 with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
234perl v5.30.0 2019-08-17 Math::PlanePath::ImaginaryBase(3)