Provided by: libmath-planepath-perl_113-1_all bug

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) base.  Or equivalently by negabinary encoded X,Y digits interleaved.  The
       default radix=2 is

           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 replicates that single point to the right.  Then that pair
       repeats above as N=2 and N=3.  Then that 2x2 block repeats to the left as N=4 to N=7, then
       4x2 repeated below as N=8 to N=16.  Then 4x4 to the right as N=16 to N=31, etc.  Each
       repeat is 90 degrees further around.  The relative layout and orientation of a sub-part is
       unchanged when replicated.

   Complex Base
       This pattern arises from representing a complex number in "base" i*sqrt(r).  For an
       integer X,Y,

           b = i*sqrt(r)
           a[i] = 0 to r-1 digits

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

       and N is the a[i] digits in base r

           N = a[k]*r^k + ... + 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, being i*sqrt(4),
       with digits 0,1,2,3.  (Knuth Seminumerical Algorithms section 4.1 and CACM 1960
       pp245-247.)

       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 power of sqrt(r) 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.

   Negabinary
       The way blocks repeat horizontally first to the right and then to the left is per the
       negabinary system base b=-2.

           X = x[k]*(-2)^k + ... + x[2]*(-2)^2 + x[1]*(-2) + x[0]

       The effect is to represent any positive or negative X by a positive integer index NX.

           X, negabinary: ... -1 -2  0  1  2  3  4  5 ...
           index NX:           2  3  0  1  6  7  4  5

       Notice how the 0 point replicates to the right as 1 and then that pair 0,1 replicates to
       the left as 2,3.  Then the block 2,3,0,1 repeats to the right as 6,7,4,5 which the same
       order with 4 added to each.  Then the resulting block of eight repeats to the left
       similarly, in the same order with 8 added to each.

       The "ImaginaryBase" takes the indexes NX and NY of these negabinary forms and forms N by
       interleaving the digits (bits) of NX and NY.  That interleaving is in the style of the
       "ZOrderCurve".

           zX,zY = ZOrderCurve n_to_xy(N)
           X = to_negabinary(zX)
           Y = to_negabinary(zY)
           X,Y equals ImaginaryBase n_to_xy(N)

       The "ZOrderCurve" replicates blocks alternately right and up, whereas for "ImaginaryBase"
       here it's right,up,left,down repeating.

   Radix
       The "radix" parameter controls the radix used to break N into X,Y.  For example radix 3
       replicates to make 3x1, 3x3, 9x3, 9x9, etc blocks.  The replications are radix-1=2 copies
       of the preceding level at each stage,

           radix => 3

           +------------------------+-----------+
           | 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

       X,Y are "negaternary" in this case, and similar negaradix base=-radix for higher values.

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.

       "($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)"
           The returned range is exact, meaning $n_lo and $n_hi are the smallest and biggest in
           the rectangle.

FORMULAS

   Rectangle to N Range
       The X and Y ranges can be treated separately and then interleaved,

           NXmin,NXmax = negaradix range to cover x1..x2
           NYmin,NYmax = negaradix range to cover y1..y2

           Nmin = interleave digits NXmin, NYmin
           Nmax = interleave digits NXmax, NYmax

       If the NX,NY ranges are exact then the resulting Nmin,Nmax range is exact.

       An exact negaradix range can be calculated by digits high to low by considering the range
       taken by the negaradix form.  For example two negaternary digits,

           N digit              2         1         0
                          +---------+---------+---------+
           N index        | 6  7  8 | 3  4  5 | 0  1  2 |
                          +---------+---------+---------+
           X negaternary   -6 -5 -4  -3 -2 -1   0  1  2
                           ^
                          base

       Taking the base=-90909...90 which is the lowest taken (where 9 is the radix digit R-1),
       then the next digit of N is the position from X-base, taken alternately reverse 2,1,0 as
       shown here or forward 0,1,2.

OEIS

       Entries in Sloane's Online Encyclopedia of Integer Sequences related to this path include,

           <http://oeis.org/A057300> (etc)

           radix=2
             A057300    permutation N at transpose Y,X (swap bit pairs)

           radix=3
             A163327    permutation N at transpose Y,X (swap trit pairs)

           radix=4
             A126006    permutation N at transpose Y,X (swap digit pairs)

           radix=16
             A217558    permutation N at transpose Y,X (swap digit pairs)

SEE ALSO

       Math::PlanePath, Math::PlanePath::ImaginaryHalf, Math::PlanePath::CubicBase,
       Math::PlanePath::ZOrderCurve

HOME PAGE

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

LICENSE

       Copyright 2011, 2012, 2013 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/>.