Kevin Ryde > Math-PlanePath-111 > Math::PlanePath::ComplexMinus

Math-PlanePath-111.tar.gz

Dependencies

Annotate this POD

Website

# CPAN RT

 Open 2
View/Report Bugs
Module Version: 111   Source   Latest Release: Math-PlanePath-114

# NAME

Math::PlanePath::ComplexMinus -- twindragon and other complex number base i-r

# SYNOPSIS

``` use Math::PlanePath::ComplexMinus;
my \$path = Math::PlanePath::ComplexMinus->new (realpart=>1);
my (\$x, \$y) = \$path->n_to_xy (123);```

# DESCRIPTION

This path traverses points by a complex number base i-r for given integer r. The default is base i-1 as per

Walter Penny, A "Binary" System for Complex Numbers, Journal of the ACM, volume 12, number 2, April 1965, pages 247-248.

When continued to a power-of-2 extent this has come to be called the "twindragon" shape.

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

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

A complex integer can be represented as a set of powers,

```    X+Yi = a[n]*b^n + ... + a[2]*b^2 + a[1]*b + a[0]
base b=i-1
digits a[n] to a[0] either 0 or 1

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

N is those a[i] digits as bits and X,Y is the resulting complex number. It can be shown that this is a one-to-one mapping so every integer X,Y of the plane is visited.

The shape of points N=0 to N=2^level-1 repeats as N=2^level to N=2^(level+1)-1. For example N=0 to N=7 is repeated as N=8 to N=15, but starting at X=2,Y=2 instead of the origin. That position 2,2 is because b^3 = 2+2i. There's no rotations or mirroring etc in this replication, just position offsets.

```    N=0 to N=7          N=8 to N=15 repeat shape

2   3                    10  11
0   1                     8   9
6   7                    14  15
4   5                    12  13```

For b=i-1 each N=2^level point starts at b^level. The powering of that b means the start position rotates around by +135 degrees each time and outward by a radius factor sqrt(2) each time. So for example b^3 = 2+2i is followed by b^4 = -4, which is 135 degrees around and radius |b^3|=sqrt(8) becoming |b^4|=sqrt(16).

## Real Part

The `realpart => \$r` option gives a complex base b=i-r for a given integer r>=1. For example `realpart => 2` is

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

N is broken into digits of base=norm=r*r+1, ie. digits 0 to r*r inclusive. This makes horizontal runs of r*r+1 many points, such as N=5 to N=9 etc above. In the default r=1 these runs are 2 long whereas for r=2 they're 2*2+1=5 long, or r=3 would be 3*3+1=10, etc.

The offset back for each run like N=5 shown is the r in i-r, then the next level is (i-r)^2 = (-2r*i + r^2-1) so N=25 begins at Y=-2*2=-4, X=2*2-1=3.

The successive replications tile the plane for any r, though the N values needed to rotate around and do so become large if norm=r*r+1 is large.

## X Axis Values

For base i-1, the X axis N=0,1,12,13,16,17,etc is integers using only digits 0,1,0xC,0xD in hexadecimal. Those on the positive X axis have an odd number of digits and on the X negative axis an even number of digits.

To be on the X axis the imaginary parts of the base powers b^k must cancel out to leave just a real part. The powers repeat in an 8-long cycle

```    k    b^k for b=i-1
0        +1
1      i -1
2    -2i +0   \ pair cancel
3     2i +2   /
4        -4
5    -4i +4
6     8i +0   \ pair cancel
7    -8i -8   /```

The k=0 and k=4 bits are always reals and can always be included. Bits k=2 and k=3 have imaginary parts -2i and 2i which cancel out, so they can be included together. Similarly k=6 and k=7 with 8i and -8i. The two blocks k=0to3 and k=4to7 differ only in a negation so the bits can be reckoned in groups of 4, which is hexadecimal. Bit 1 is digit value 1 and bits 2,3 together are digit value 0xC, so adding one or both of those gives combinations are 0,1,0xC,0xD.

The high hex digit determines the sign, positive or negative, of the total real part. Bits k=0 or k=2,3 are positive. Bits k=4 or k=6,7 are negative, so

```    N for X>0   N for X<0

0x01..     0x1_..     even number of hex 0,1,C,D following
0x0C..     0xC_..     "_" digit any of 0,1,C,D
0x0D..     0xD_..```

which is equivalent to X>0 is an odd number of hex digits or X<0 is an even number. For example N=28=0x1C is at X=-2 since that N is X<0 form "0x1_".

The order of the values on the positive X axis is obtained by taking the digits in reverse order on alternate positions

```    0,1,C,D   high digit
D,C,1,0
0,1,C,D
...
D,C,1,0
0,1,C,D   low digit```

For example in the following notice the first and third digit increases, but the middle digit decreases,

```    X=4to7     N=0x1D0,0x1D1,0x1DC,0x1DD
X=8to11    N=0x1C0,0x1C1,0x1CC,0x1CD
X=12to15   N=0x110,0x111,0x11C,0x11D
X=16to19   N=0x100,0x101,0x10C,0x10D
X=20to23   N=0xCD0,0xCD1,0xCDC,0xCDD```

For the negative X axis it's the same if reading by increasing X, ie. upwards toward +infinity, or the opposite way around if reading decreasing X, ie. more negative downwards toward -infinity.

## Fractal

The i-1 twindragon is usually conceived as taking fractional N like 0.abcde in binary and giving fractional complex X+iY. The twindragon is then all the points of the complex plane reached by such fractional N. This set of points can be shown to be connected and to fill a certain radius around the origin.

The code here might be pressed into use for that to some finite number of bits by multiplying up to make an integer N

```    Nint = Nfrac * 256^k
Xfrac = Xint / 16^k
Yfrac = Yint / 16^k```

256 is a good power because b^8=16 is a positive real and so there's no rotations to apply to the resulting X,Y, just a power-of-16 division (b^8)^k=16^k each. Using b^4=-4 for a multiplier 16^k and divisor (-4)^k would be almost as easy too, requiring just a sign change if k odd.

## Boundary Length

The length of the boundary of the first norm^k many points (N=0 to norm^k-1 inclusive) is calculated in

William J. Gilbert, "The Fractal Dimension of Sets Derived From Complex Bases", Canadian Math Bulletin, volume 29(4), 1986. http://www.math.uwaterloo.ca/~wgilbert/Research/GilbertFracDim.pdf

The result is a 3rd-order recurrence. For the twindragon it is

```    realpart=1
boundary[k] = boundary[k-1] + 2*boundary[k-3]

4, 6, 10, 18, 30, 50, 86, 146, 246, 418, 710, ...```

The first three boundaries are as follows. Then the recurrence gives the next boundary[3] = 10+2*4 = 18.

```     k      area     boundary[k]
---     ----     -----------
+---+
0     2^k = 1       4             | 0 |
+---+

+---+---+
1     2^k = 2       6             | 0   1 |
+---+---+

+---+---+
| 2   3 |
2     2^k = 4      10         +---+   +---+
| 0   1 |
+---+---+```

Gilbert calculates the boundary of any i-r by taking it in three parts A,B,C and showing how in the next replication level those parts transform into multiple copies of the preceding level parts. The replication is a little easier to visualize for a bigger "r" than for the twindragon. In bigger r it's clearer how the A, B and C parts differ.

```    A -> A * (2*realpart-1)             + C * 2*realpart
B -> A * (realpart^2-2*realpart+2)  + C * (realpart-1)^2
C -> B

starting from
A = 2*realpart
B = 2
C = 2 - 2*realpart

total boundary = A+B+C```

For the twindragon realpart=1 these A,B,C are already in the form of a recurrence A->A+2*C, B->A, C->B, per the formula above. For other real parts a little matrix rearrangement gives the recurrence

```    boundary[k] = boundary[k-1] * (2*realpart - 1)
+ boundary[k-2] * (norm - 2*realpart)
+ boundary[k-3] * norm

starting from
boundary[0] = 4
boundary[1] = 2*norm + 2
boundary[2] = 2*(norm-1)*(realpart+2) + 4```

For example

```    realpart=2
boundary[k] = 3*boundary[k-1] + 1*boundary[k-2] + 5*boundary[k-1]

4, 12, 36, 140, 516, 1868, 6820, 24908, ...```

As with all such recurrences, for large k values can be calculated by powering up the matrix form.

# FUNCTIONS

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

`\$path = Math::PlanePath::ComplexMinus->new ()`
`\$path = Math::PlanePath::ComplexMinus->new (realpart => \$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` should be an integer, it's unspecified yet what will be done for a fraction.

# FORMULAS

## X,Y to N

A given X,Y representing X+Yi can be turned into digits of N by successive complex divisions by i-r. Each digit of N is a real remainder 0 to r*r inclusive from that division.

As per the base formula above

`    X+Yi = a[n]*b^n + ... + a[2]*b^2 + a[1]*b + a[0]`

and we will want the a[0]=digit to be a real 0 to r*r. Subtracting a[0] and dividing by b will give

```    (X+Yi - digit) / (i-r)
= - (X-digit + Y*i) * (i+r) / norm
= (Y - (X-digit)*r)/norm
+ i * - ((X-digit) + Y*r)/norm```

which is

```    X   <-   Y - (X-digit)*r)/norm
Y   <-   -((X-digit) + Y*r)/norm```

The a[0] digit must make both X and Y parts integers. The easiest to calculate from is the imaginary part,

`    - ((X-digit) + Y*r) == 0 mod norm`

so

`    digit = X + Y*r mod norm`

This digit value makes the real part a multiple of norm too, as can be seen from

```    Y - (X-digit)*r
= Y - X*r - (X+Y*r)*r
= Y - X*r - X*r + Y*r*r
= Y*(r*r+1)
= Y*norm```

Notice the new Y is the quotient from (X+Y*r)/norm rounded towards negative infinity. Ie. in the division "X+Y*r mod norm" which calculates the digit, the quotient is the new Y and the remainder is the digit.

# OEIS

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

```    realpart=1 (the default)
A066321    N on X axis, being the base i-1 positive reals
A066323    N on X axis, in binary
A066322    diffs (N at X=16k+4) - (N at X=16k+3)

A003476    boundary length / 2
recurrence a(n) = a(n-1) + 2*a(n-3)
A203175    boundary length, starting from 4
if its conjectured recurrence is true
A052537    boundary length part A, B or C per Gilbert's paper```

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