/ 
Math-PlanePath-76
River stage one • 3 direct dependents • 4 total dependents
/ Math::PlanePath::ImaginaryBase

NAME

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

SYNOPSIS

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

DESCRIPTION

This is a simple pattern arising from complex numbers expressed in a base i*sqrt(2) or other i*sqrt(r) bases. The default r=2 gives

38   39   34   35   54   55   50   51        5
36   37   32   33   52   53   48   49        4
46   47   42   43   62   63   58   59        3
44   45   40   41   60   61   56   57        2
 6    7    2    3   22   23   18   19        1
 4    5    0    1   20   21   16   17    <- Y=0
14   15   10   11   30   31   26   27       -1
12   13    8    9   28   29   24   25       -2
           ^
-2   -1   X=0   1    2    3    4    5

The pattern can be seen by dividing into blocks as follows,

+---------------------------------------+
| 38   39   34   35   54   55   50   51 |
|                                       |
| 36   37   32   33   52   53   48   49 |
|                                       |
| 46   47   42   43   62   63   58   59 |
|                                       |
| 44   45   40   41   60   61   56   57 |
+---------+---------+-------------------+
|  6    7 |  2    3 | 22   23   18   19 |
|         +----+----+                   |
|  4    5 |  0 |  1 | 20   21   16   17 |
+---------+----+----+                   |
| 14   15   10   11 | 30   31   26   27 |
|                   |                   |
| 12   13    8    9 | 28   29   24   25 |
+-------------------+-------------------+

After N=0 at the origin, N=1 is to the right. Then those two repeat above as N=2 and N=3. Then that 2x2 block repeats to the right as N=4 to N=7, then 4x2 repeated below as N=8 to N=16, and 4x4 to the right as N=16 to N=31, etc. Each repeat is 90 degrees further around. The orientation and relative layout is unchanged within each replicated part, there's no rotation etc.

Complex Base

This pattern arises from representing a complex number in "base" b=i*sqrt(r) with digits a[i] in the range 0 to r-1. For integer X,Y,

X+Y*i*sqrt(r) = a[n]*b^n + ... + a[2]*b^2 + a[1]*b + a[0]

and N is a base-r integer

N = a[n]*r^n + ... + a[2]*r^2 + a[1]*r + a[0]

The factor sqrt(r) makes the generated Y an integer. For actual use as a number base that factor can be omitted and instead fractional digits a[-1]*r^-1 etc used to reach smaller Y values, as for example in Knuth's "quater-imaginary" system of base 2*i, ie. i*sqrt(4), with digits 0,1,2,3.

The powers of i in the base give the replication direction, so i^0=1 right, i^1=i up, i^2=-1 right, i^3=-i down, etc. The sqrt(r) part then spreads the replication in the respective direction. It takes two steps to repeat horizontally and sqrt(r)^2=r hence the doubling of 1x1 to the right, 2x2 to the left, 4x4 to the right, etc, and similarly vertically.

Radix

The radix parameter controls the "r" used to break N into X,Y. For example radix => 3 gives 3x3 blocks, with r-1 copies of the preceding level at each stage,

24  25  26  15  16  17   6   7   8      2
21  22  23  12  13  14   3   4   5      1
18  19  20   9  10  11   0   1   2  <- Y=0
51  52  53  42  43  44  33  34  35     -1
48  49  50  39  40  41  30  31  32     -2
45  46  47  36  37  38  27  28  29     -3
78  79  80  69  70  71  60  61  62     -4
75  76  77  66  67  68  57  58  59     -5
72  73  74  63  64  65  54  55  56     -6

                         ^
-6  -5  -4  -3  -2  -1  X=0  1   2

Z Order and Negabinary

The pattern can be compared to the ZOrderCurve. In Z-Order the replications are alternately right and up, but here they progress through four directions right, up, left, down.

The alternate positive and negative X, and alternate positive and negative Y likewise, follow the negabinary system. If N is at X,Y on the ZOrderCurve then those coordinates converted to negabinary give the ImaginaryBase.

zX,zY = ZOrderCurve n_to_xy(N)
nX = to_negabinary(zX)
nY = to_negabinary(zX)
nX,nY equals ImaginaryBase n_to_xy(N)

For a radix other than binary the conversion is likewise, to negaternary or negadecimal etc.

FUNCTIONS

See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes.

$path = Math::PlanePath::ImaginaryBase->new ()
$path = Math::PlanePath::ImaginaryBase->new (radix => $r)

Create and return a new path object.

($x,$y) = $path->n_to_xy ($n)

Return the X,Y coordinates of point number $n on the path. Points begin at 0 and if $n < 0 then the return is an empty list.

SEE ALSO

Math::PlanePath, Math::PlanePath::ZOrderCurve

HOME PAGE

http://user42.tuxfamily.org/math-planepath/index.html

LICENSE

Copyright 2011, 2012 Kevin Ryde

Math-PlanePath is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.

Math-PlanePath is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.