---
name: "Math::PlanePath::ComplexRevolving"
section: "3pm"
platform: "linux"
package: "libmath-planepath-perl"
version: "129-1"
release: "Debian 13 (Trixie)"
platforms: ["linux"]
url: "https://new.carta.tech/Math::PlanePath::ComplexRevolving"
---

# Math::PlanePath::ComplexRevolving(3pm)

## 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 1-bits 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 one-to-one 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.

### Level Methods

- "($n\_lo, $n\_hi) = $path-\>level\_to\_n\_range($level)"

  Return `"(0, 2**$level - 1)"`.

## 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/math-planepath/index.html\>

## LICENSE

Copyright 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020 Kevin Ryde

This file is part of Math-PlanePath.

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/\>.