Math::...volving(3pm)

✨ NAME ✨

Math::PlanePath::ComplexRevolving — points in revolving complex base i+1 🌀

okay so real quick, this page is from the User Contributed Perl Documentation manual, and the header up top is short for the full name above (the man page title is <rainbow>Math::...volving(3pm)</rainbow> because man pages love to abbreviate and leave you guessing 💀). Anyway. Bestie. Let's talk about a path that spins.

---

🦋 SYNOPSIS 🦋

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

---

💖 DESCRIPTION 💖

So this path walks points using a complex number base i+1, and here's the twist (literally): there's a turn factor of i (that's +90 degrees, bestie) every time you hit a 1 bit. This whole thing is the "revolving binary representation" from Knuth's Seminumerical Algorithms, section 4.1, exercise 28. Iconic behavior honestly.

Here's the map, look at her go 👑:

            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

So the 1 bits in N are exponents e0 to et, in increasing order, like:

N = 2^e0 + 2^e1 + ... + 2^et        e0 < e1 < ... < et

and those get applied to a base b=i+1 like this:

X+iY = b^e0 + i * b^e1 + i^2 * b^e2 + ... + i^t * b^et

Each 2^ek has become b^ek with base b=i+1. And that i^k? It's an extra factor of i at each 1 bit of N, and it causes a rotation by +90 degrees for all the bits above it. And not me pointing out the sneaky detail: the factor is i^k, NOT i^ek — it only increments with the 1-bits of N, not the whole exponent. iykyk 💅

A single bit N=2^k is the simplest case and it's just X+iY=(i+1)^k. Those N=1,2,4,8,16,etc sit at successive angles 45, 90, 135, etc degrees (same as in "ComplexPlus"). But points N=2^k+1 with two bits mean 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 land in the next quadrant around from their preceding 2,4,8,16,32. rotating queen 🌀👑

And 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. no cap. ✨

---

🎀 FUNCTIONS 🎀

Peep "FUNCTIONS" in Math::PlanePath for the behaviour that's common to all path classes, bestie 🫶

• $path = Math::PlanePath::ComplexRevolving->new () — make a brand new path object and hand it back to you.
• ($x,$y) = $path->n_to_xy ($n) — give it a point number $n and it returns the X,Y coordinates of that point on the path. Points start at 0, and if "$n < 0" then you get back an empty list — that's it, nothing, nada 🙈

💜 Level Methods 💜

• ($n_lo, $n_hi) = $path->level_to_n_range($level) — returns (0, 2**$level - 1). that's the whole thing. slay. 💅

---

🌈 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. (yes bestie we're citing the man himself 📚)

---

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

---

⚠️ okay one last vibe check: this is perl v5.32.0, dated 2021-01-23, and the page header calls itself Math::...volving(3pm). 💖 thanks for reading bestie, go plot some points 🦋✨