1Math::PlanePath::CompleUxsReervoClovnitnrgi(b3u)ted PerlMaDtohc:u:mPelnatnaetPiaotnh::ComplexRevolving(3)
2
3
4

NAME

6       Math::PlanePath::ComplexRevolving -- points in revolving complex base
7       i+1
8

SYNOPSIS

10        use Math::PlanePath::ComplexRevolving;
11        my $path = Math::PlanePath::ComplexRevolving->new;
12        my ($x, $y) = $path->n_to_xy (123);
13

DESCRIPTION

15       This path traverses points by a complex number base i+1 with turn
16       factor i (+90 degrees) at each 1 bit.  This is the "revolving binary
17       representation" of Knuth's Seminumerical Algorithms section 4.1
18       exercise 28.
19
20                    54 51       38 35            5
21                 60 53       44 37               4
22           39 46 43 58 23 30 27 42               3
23              45  8 57  4 29 56 41 52            2
24                 31  6  3  2 15 22 19 50         1
25           16    12  5  0  1 28 21    49     <- Y=0
26           55 62 59 10  7 14 11 26              -1
27              61 24  9 20 13 40 25 36           -2
28                 47       18 63       34        -3
29           32          48 17          33        -4
30
31                        ^
32           -4 -3 -2 -1 X=0 1  2  3  4  5
33
34       The 1 bits in N are exponents e0 to et, in increasing order,
35
36           N = 2^e0 + 2^e1 + ... + 2^et        e0 < e1 < ... < et
37
38       and are applied to a base b=i+1 as
39
40           X+iY = b^e0 + i * b^e1 + i^2 * b^e2 + ... + i^t * b^et
41
42       Each 2^ek has become b^ek base b=i+1.  The i^k is an extra factor i at
43       each 1 bit of N, causing a rotation by +90 degrees for the bits above
44       it.  Notice the factor is i^k not i^ek, ie. it increments only with the
45       1-bits of N, not the whole exponent.
46
47       A single bit N=2^k is the simplest and is X+iY=(i+1)^k.  These
48       N=1,2,4,8,16,etc are at successive angles 45, 90, 135, etc degrees (the
49       same as in "ComplexPlus").  But points N=2^k+1 with two bits means
50       X+iY=(i+1) + i*(i+1)^k and that factor "i*" is a rotation by 90 degrees
51       so points N=3,5,9,17,33,etc are in the next quadrant around from their
52       preceding 2,4,8,16,32.
53
54       As per the exercise in Knuth it's reasonably easy to show that this
55       calculation is a one-to-one mapping between integer N and complex
56       integer X+iY, so the path covers the plane and visits all points once
57       each.
58

FUNCTIONS

60       See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
61       classes.
62
63       "$path = Math::PlanePath::ComplexRevolving->new ()"
64           Create and return a new path object.
65
66       "($x,$y) = $path->n_to_xy ($n)"
67           Return the X,Y coordinates of point number $n on the path.  Points
68           begin at 0 and if "$n < 0" then the return is an empty list.
69
70   Level Methods
71       "($n_lo, $n_hi) = $path->level_to_n_range($level)"
72           Return "(0, 2**$level - 1)".
73

SEE ALSO

75       Math::PlanePath, Math::PlanePath::ComplexMinus,
76       Math::PlanePath::ComplexPlus, Math::PlanePath::DragonCurve
77
78       Donald Knuth, "The Art of Computer Programming", volume 2
79       "Seminumerical Algorithms", section 4.1 exercise 28.
80

HOME PAGE

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

LICENSE

85       Copyright 2012, 2013, 2014, 2015, 2016, 2017, 2018 Kevin Ryde
86
87       This file is part of Math-PlanePath.
88
89       Math-PlanePath is free software; you can redistribute it and/or modify
90       it under the terms of the GNU General Public License as published by
91       the Free Software Foundation; either version 3, or (at your option) any
92       later version.
93
94       Math-PlanePath is distributed in the hope that it will be useful, but
95       WITHOUT ANY WARRANTY; without even the implied warranty of
96       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
97       General Public License for more details.
98
99       You should have received a copy of the GNU General Public License along
100       with Math-PlanePath.  If not, see <http://www.gnu.org/licenses/>.
101
102
103
104perl v5.32.0                      2020-07-2M8ath::PlanePath::ComplexRevolving(3)
Impressum