.\" Automatically generated by Pod::Man 4.14 (Pod::Simple 3.40) .\" .\" Standard preamble: .\" ======================================================================== .de Sp \" Vertical space (when we can't use .PP) .if t .sp .5v .if n .sp .. .de Vb \" Begin verbatim text .ft CW .nf .ne \\$1 .. .de Ve \" End verbatim text .ft R .fi .. .\" Set up some character translations and predefined strings. \*(-- will .\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left .\" double quote, and \*(R" will give a right double quote. \*(C+ will .\" give a nicer C++. Capital omega is used to do unbreakable dashes and .\" therefore won't be available. \*(C` and \*(C' expand to `' in nroff, .\" nothing in troff, for use with C<>. .tr \(*W- .ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p' .ie n \{\ . ds -- \(*W- . ds PI pi . if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch . if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\" diablo 12 pitch . ds L" "" . ds R" "" . ds C` "" . ds C' "" 'br\} .el\{\ . ds -- \|\(em\| . ds PI \(*p . ds L" `` . ds R" '' . ds C` . ds C' 'br\} .\" .\" Escape single quotes in literal strings from groff's Unicode transform. .ie \n(.g .ds Aq \(aq .el .ds Aq ' .\" .\" If the F register is >0, we'll generate index entries on stderr for .\" titles (.TH), headers (.SH), subsections (.SS), items (.Ip), and index .\" entries marked with X<> in POD. Of course, you'll have to process the .\" output yourself in some meaningful fashion. .\" .\" Avoid warning from groff about undefined register 'F'. .de IX .. .nr rF 0 .if \n(.g .if rF .nr rF 1 .if (\n(rF:(\n(.g==0)) \{\ . if \nF \{\ . de IX . tm Index:\\$1\t\\n%\t"\\$2" .. . if !\nF==2 \{\ . nr % 0 . nr F 2 . \} . \} .\} .rr rF .\" ======================================================================== .\" .IX Title "Math::PlanePath::ComplexRevolving 3pm" .TH Math::PlanePath::ComplexRevolving 3pm "2021-01-23" "perl v5.32.0" "User Contributed Perl Documentation" .\" For nroff, turn off justification. Always turn off hyphenation; it makes .\" way too many mistakes in technical documents. .if n .ad l .nh .SH "NAME" Math::PlanePath::ComplexRevolving \-\- points in revolving complex base i+1 .SH "SYNOPSIS" .IX Header "SYNOPSIS" .Vb 3 \& use Math::PlanePath::ComplexRevolving; \& my $path = Math::PlanePath::ComplexRevolving\->new; \& my ($x, $y) = $path\->n_to_xy (123); .Ve .SH "DESCRIPTION" .IX Header "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 \*(L"revolving binary representation\*(R" of Knuth's Seminumerical Algorithms section 4.1 exercise 28. .IX Xref "Knuth, Donald" .PP .Vb 10 \& 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 .Ve .PP The 1 bits in N are exponents e0 to et, in increasing order, .PP .Vb 1 \& N = 2^e0 + 2^e1 + ... + 2^et e0 < e1 < ... < et .Ve .PP and are applied to a base b=i+1 as .PP .Vb 1 \& X+iY = b^e0 + i * b^e1 + i^2 * b^e2 + ... + i^t * b^et .Ve .PP 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. .PP 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 \f(CW\*(C`ComplexPlus\*(C'\fR). But points N=2^k+1 with two bits means X+iY=(i+1) + i*(i+1)^k and that factor \*(L"i*\*(R" 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. .PP 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. .SH "FUNCTIONS" .IX Header "FUNCTIONS" See \*(L"\s-1FUNCTIONS\*(R"\s0 in Math::PlanePath for behaviour common to all path classes. .ie n .IP """$path = Math::PlanePath::ComplexRevolving\->new ()""" 4 .el .IP "\f(CW$path = Math::PlanePath::ComplexRevolving\->new ()\fR" 4 .IX Item "$path = Math::PlanePath::ComplexRevolving->new ()" Create and return a new path object. .ie n .IP """($x,$y) = $path\->n_to_xy ($n)""" 4 .el .IP "\f(CW($x,$y) = $path\->n_to_xy ($n)\fR" 4 .IX Item "($x,$y) = $path->n_to_xy ($n)" Return the X,Y coordinates of point number \f(CW$n\fR on the path. Points begin at 0 and if \f(CW\*(C`$n < 0\*(C'\fR then the return is an empty list. .SS "Level Methods" .IX Subsection "Level Methods" .ie n .IP """($n_lo, $n_hi) = $path\->level_to_n_range($level)""" 4 .el .IP "\f(CW($n_lo, $n_hi) = $path\->level_to_n_range($level)\fR" 4 .IX Item "($n_lo, $n_hi) = $path->level_to_n_range($level)" Return \f(CW\*(C`(0, 2**$level \- 1)\*(C'\fR. .SH "SEE ALSO" .IX Header "SEE ALSO" Math::PlanePath, Math::PlanePath::ComplexMinus, Math::PlanePath::ComplexPlus, Math::PlanePath::DragonCurve .PP Donald Knuth, \*(L"The Art of Computer Programming\*(R", volume 2 \*(L"Seminumerical Algorithms\*(R", section 4.1 exercise 28. .SH "HOME PAGE" .IX Header "HOME PAGE" .SH "LICENSE" .IX Header "LICENSE" Copyright 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020 Kevin Ryde .PP This file is part of Math-PlanePath. .PP Math-PlanePath is free software; you can redistribute it and/or modify it under the terms of the \s-1GNU\s0 General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version. .PP Math-PlanePath is distributed in the hope that it will be useful, but \&\s-1WITHOUT ANY WARRANTY\s0; without even the implied warranty of \s-1MERCHANTABILITY\s0 or \s-1FITNESS FOR A PARTICULAR PURPOSE.\s0 See the \s-1GNU\s0 General Public License for more details. .PP You should have received a copy of the \s-1GNU\s0 General Public License along with Math-PlanePath. If not, see .