1Math::PlanePath::CompleUxsReervoClovnitnrgi(b3u)ted PerlMaDtohc:u:mPelnatnaetPiaotnh::ComplexRevolving(3)
2
6 Math::PlanePath::ComplexRevolving -- points in revolving complex base
7 i+1
8
10 use Math::PlanePath::ComplexRevolving;
11 my $path = Math::PlanePath::ComplexRevolving->new;
12 my ($x, $y) = $path->n_to_xy (123);
13
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 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 ^
32 -4 -3 -2 -1 X=0 1 2 3 4 5
33 The 1 bits in N are exponents e0 to et, in increasing order,
35 N = 2^e0 + 2^e1 + ... + 2^et e0 < e1 < ... < et
37 and are applied to a base b=i+1 as
39 X+iY = b^e0 + i * b^e1 + i^2 * b^e2 + ... + i^t * b^et
41 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 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 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
60 See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
61 classes.
62 "$path = Math::PlanePath::ComplexRevolving->new ()"
64 Create and return a new path object.
65 "($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 Level Methods
71 "($n_lo, $n_hi) = $path->level_to_n_range($level)"
72 Return "(0, 2**$level - 1)".
73
75 Math::PlanePath, Math::PlanePath::ComplexMinus,
76 Math::PlanePath::ComplexPlus, Math::PlanePath::DragonCurve
77 Donald Knuth, "The Art of Computer Programming", volume 2
79 "Seminumerical Algorithms", section 4.1 exercise 28.
80
82 <http://user42.tuxfamily.org/math-planepath/index.html>
83
85 Copyright 2012, 2013, 2014, 2015, 2016, 2017 Kevin Ryde
86 This file is part of Math-PlanePath.
88 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 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 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/>.
101perl v5.28.1 2017-12-0M3ath::PlanePath::ComplexRevolving(3)