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

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::ComplexMinus, Math::PlanePath::ComplexPlus, Math::PlanePath::DragonCurve
Donald Knuth, "The Art of Computer Programming", volume 2 "Seminumerical Algorithms", section 4.1 exercise 28.
HOME PAGE
http://user42.tuxfamily.org/mathplanepath/index.html
LICENSE
Copyright 2012, 2013, 2014 Kevin Ryde
This file is part of MathPlanePath.
MathPlanePath 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.
MathPlanePath 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 MathPlanePath. If not, see <http://www.gnu.org/licenses/>.