1Math::PlanePath::ImaginUasreyrBaCsoen(t3r)ibuted Perl DoMcautmhe:n:tPaltainoenPath::ImaginaryBase(3)
2
3
4

NAME

6       Math::PlanePath::ImaginaryBase -- replications in four directions
7

SYNOPSIS

9        use Math::PlanePath::ImaginaryBase;
10        my $path = Math::PlanePath::ImaginaryBase->new (radix => 4);
11        my ($x, $y) = $path->n_to_xy (123);
12

DESCRIPTION

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
18           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
29       The pattern can be seen by dividing into blocks as follows,
30
31           +---------------------------------------+
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
49       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
56   Complex Base
57       This pattern arises from representing a complex number in "base"
58       i*sqrt(r).  For an integer X,Y,
59
60           base b = i*sqrt(r)
61           a[j] = digit 0 to r-1
62
63           X + Y*i*sqrt(r) = a[k]*b^k + ... + a[2]*b^2 + a[1]*b + a[0]
64
65       and N is the a[j] digits in base r
66
67           N = a[k]*r^k + ... + a[2]*r^2 + a[1]*r + a[0]
68
69       The sum has imaginary part with a factor sqrt(r).  Dividing that out
70       gives an integer Y.  For actual use as a number base, that factor can
71       be omitted and instead fractional digits a[-1]*r^-1 etc used to reach
72       smaller Y values, as for example in Knuth's "quater-imaginary" system
73       of base 2*i, being i*sqrt(4), with digits 0,1,2,3.  (Knuth
74       Seminumerical Algorithms section 4.1 and CACM 1960 pp245-247.)
75
76       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.  Two steps
79       repeat horizontally and sqrt(r)^2=r hence the doubling of 1x1 to the
80       right, 2x2 to the left, 4x4 to the right, etc, and similarly
81       vertically.
82
83   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
87           X = x[k]*(-2)^k + ... + x[2]*(-2)^2 + x[1]*(-2) + x[0]
88
89       The effect is to represent any positive or negative X by a positive
90       integer index NX.
91
92           X, negabinary: ... -1 -2  0  1  2  3  4  5 ...
93           index NX:           2  3  0  1  6  7  4  5
94
95       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
101       "ImaginaryBase" takes the indexes NX and NY of these negabinary forms
102       and forms N by interleaving the digits (bits) of NX and NY.  That
103       interleaving is in the style of the "ZOrderCurve".
104
105           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
110       The "ZOrderCurve" replicates blocks alternately right and up, whereas
111       for "ImaginaryBase" here it's right,up,left,down, and so on repeating.
112
113   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
118           radix => 3
119
120           +------------------------+-----------+
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
142       X,Y are "negaternary" in this case, and similar negaradix base=-radix
143       for higher values.
144

FUNCTIONS

146       See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
147       classes.
148
149       "$path = Math::PlanePath::ImaginaryBase->new ()"
150       "$path = Math::PlanePath::ImaginaryBase->new (radix => $r)"
151           Create and return a new path object.
152
153       "($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
157       "($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
161   Level Methods
162       "($n_lo, $n_hi) = $path->level_to_n_range($level)"
163           Return "(0, $radix**$level - 1)".
164

FORMULAS

166   Rectangle to N Range
167       The X and Y ranges can be treated separately and then interleaved,
168
169           NXmin,NXmax = negaradix range to cover x1..x2
170           NYmin,NYmax = negaradix range to cover y1..y2
171
172           Nmin = interleave digits NXmin, NYmin
173           Nmax = interleave digits NXmax, NYmax
174
175       If the NX,NY ranges are exact then the resulting Nmin,Nmax range is
176       exact.
177
178       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
182           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
190       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

OEIS

195       Entries in Sloane's Online Encyclopedia of Integer Sequences related to
196       this path include,
197
198           <http://oeis.org/A057300> (etc)
199
200           radix=2
201             A057300    permutation N at transpose Y,X (swap bit pairs)
202
203           radix=3
204             A163327    permutation N at transpose Y,X (swap trit pairs)
205
206           radix=4
207             A126006    permutation N at transpose Y,X (swap digit pairs)
208
209           radix=16
210             A217558    permutation N at transpose Y,X (swap digit pairs)
211

SEE ALSO

213       Math::PlanePath, Math::PlanePath::ImaginaryHalf,
214       Math::PlanePath::CubicBase, Math::PlanePath::ZOrderCurve
215

HOME PAGE

217       <http://user42.tuxfamily.org/math-planepath/index.html>
218

LICENSE

220       Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020
221       Kevin Ryde
222
223       Math-PlanePath is free software; you can redistribute it and/or modify
224       it under the terms of the GNU General Public License as published by
225       the Free Software Foundation; either version 3, or (at your option) any
226       later version.
227
228       Math-PlanePath is distributed in the hope that it will be useful, but
229       WITHOUT ANY WARRANTY; without even the implied warranty of
230       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
231       General Public License for more details.
232
233       You should have received a copy of the GNU General Public License along
234       with Math-PlanePath.  If not, see <http://www.gnu.org/licenses/>.
235
236
237
238perl v5.36.0                      2023-01-20 Math::PlanePath::ImaginaryBase(3)
Impressum