.\" Automatically generated by Pod::Man 2.28 (Pod::Simple 3.28) .\" .\" 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 turned on, 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 .\" .\" Accent mark definitions (@(#)ms.acc 1.5 88/02/08 SMI; from UCB 4.2). .\" Fear. Run. Save yourself. No user-serviceable parts. . \" fudge factors for nroff and troff .if n \{\ . ds #H 0 . ds #V .8m . ds #F .3m . ds #[ \f1 . ds #] \fP .\} .if t \{\ . ds #H ((1u-(\\\\n(.fu%2u))*.13m) . ds #V .6m . ds #F 0 . ds #[ \& . ds #] \& .\} . \" simple accents for nroff and troff .if n \{\ . ds ' \& . ds ` \& . ds ^ \& . ds , \& . ds ~ ~ . ds / .\} .if t \{\ . ds ' \\k:\h'-(\\n(.wu*8/10-\*(#H)'\'\h"|\\n:u" . ds ` \\k:\h'-(\\n(.wu*8/10-\*(#H)'\`\h'|\\n:u' . ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'^\h'|\\n:u' . ds , \\k:\h'-(\\n(.wu*8/10)',\h'|\\n:u' . ds ~ \\k:\h'-(\\n(.wu-\*(#H-.1m)'~\h'|\\n:u' . ds / \\k:\h'-(\\n(.wu*8/10-\*(#H)'\z\(sl\h'|\\n:u' .\} . \" troff and (daisy-wheel) nroff accents .ds : \\k:\h'-(\\n(.wu*8/10-\*(#H+.1m+\*(#F)'\v'-\*(#V'\z.\h'.2m+\*(#F'.\h'|\\n:u'\v'\*(#V' .ds 8 \h'\*(#H'\(*b\h'-\*(#H' .ds o \\k:\h'-(\\n(.wu+\w'\(de'u-\*(#H)/2u'\v'-.3n'\*(#[\z\(de\v'.3n'\h'|\\n:u'\*(#] .ds d- \h'\*(#H'\(pd\h'-\w'~'u'\v'-.25m'\f2\(hy\fP\v'.25m'\h'-\*(#H' .ds D- D\\k:\h'-\w'D'u'\v'-.11m'\z\(hy\v'.11m'\h'|\\n:u' .ds th \*(#[\v'.3m'\s+1I\s-1\v'-.3m'\h'-(\w'I'u*2/3)'\s-1o\s+1\*(#] .ds Th \*(#[\s+2I\s-2\h'-\w'I'u*3/5'\v'-.3m'o\v'.3m'\*(#] .ds ae a\h'-(\w'a'u*4/10)'e .ds Ae A\h'-(\w'A'u*4/10)'E . \" corrections for vroff .if v .ds ~ \\k:\h'-(\\n(.wu*9/10-\*(#H)'\s-2\u~\d\s+2\h'|\\n:u' .if v .ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'\v'-.4m'^\v'.4m'\h'|\\n:u' . \" for low resolution devices (crt and lpr) .if \n(.H>23 .if \n(.V>19 \ \{\ . ds : e . ds 8 ss . ds o a . ds d- d\h'-1'\(ga . ds D- D\h'-1'\(hy . ds th \o'bp' . ds Th \o'LP' . ds ae ae . ds Ae AE .\} .rm #[ #] #H #V #F C .\" ======================================================================== .\" .IX Title "Math::PlanePath::ImaginaryBase 3pm" .TH Math::PlanePath::ImaginaryBase 3pm "2014-08-26" "perl v5.20.1" "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::ImaginaryBase \-\- replications in four directions .SH "SYNOPSIS" .IX Header "SYNOPSIS" .Vb 3 \& use Math::PlanePath::ImaginaryBase; \& my $path = Math::PlanePath::ImaginaryBase\->new (radix => 4); \& my ($x, $y) = $path\->n_to_xy (123); .Ve .SH "DESCRIPTION" .IX Header "DESCRIPTION" This is a simple pattern arising from complex numbers expressed in a base i*\fIsqrt\fR\|(2) or other i*sqrt(r) base. Or equivalently by negabinary encoded X,Y digits interleaved. The default radix=2 is .PP .Vb 10 \& 38 39 34 35 54 55 50 51 5 \& 36 37 32 33 52 53 48 49 4 \& 46 47 42 43 62 63 58 59 3 \& 44 45 40 41 60 61 56 57 2 \& 6 7 2 3 22 23 18 19 1 \& 4 5 0 1 20 21 16 17 <\- Y=0 \& 14 15 10 11 30 31 26 27 \-1 \& 12 13 8 9 28 29 24 25 \-2 \& ^ \& \-2 \-1 X=0 1 2 3 4 5 .Ve .PP The pattern can be seen by dividing into blocks as follows, .PP .Vb 10 \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-+ \& | 38 39 34 35 54 55 50 51 | \& | | \& | 36 37 32 33 52 53 48 49 | \& | | \& | 46 47 42 43 62 63 58 59 | \& | | \& | 44 45 40 41 60 61 56 57 | \& +\-\-\-\-\-\-\-\-\-+\-\-\-\-\-\-\-\-\-+\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-+ \& | 6 7 | 2 3 | 22 23 18 19 | \& | +\-\-\-\-+\-\-\-\-+ | \& | 4 5 | 0 | 1 | 20 21 16 17 | \& +\-\-\-\-\-\-\-\-\-+\-\-\-\-+\-\-\-\-+ | \& | 14 15 10 11 | 30 31 26 27 | \& | | | \& | 12 13 8 9 | 28 29 24 25 | \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-+\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-+ .Ve .PP After N=0 at the origin, N=1 replicates that single point to the right. Then that pair repeats above as N=2 and N=3. Then that 2x2 block repeats to the left as N=4 to N=7, then 4x2 repeated below as N=8 to N=16. Then 4x4 to the right as N=16 to N=31, etc. Each repeat is 90 degrees further around. The relative layout and orientation of a sub-part is unchanged when replicated. .SS "Complex Base" .IX Subsection "Complex Base" This pattern arises from representing a complex number in \*(L"base\*(R" i*sqrt(r). For an integer X,Y, .PP .Vb 2 \& b = i*sqrt(r) \& a[i] = 0 to r\-1 digits \& \& X+Y*i*sqrt(r) = a[k]*b^k + ... + a[2]*b^2 + a[1]*b + a[0] .Ve .PP and N is the a[i] digits in base r .PP .Vb 1 \& N = a[k]*r^k + ... + a[2]*r^2 + a[1]*r + a[0] .Ve .PP The factor sqrt(r) makes the generated Y an integer. For actual use as a number base that factor can be omitted and instead fractional digits a[\-1]*r^\-1 etc used to reach smaller Y values, as for example in Knuth's \*(L"quater-imaginary\*(R" system of base 2*i, being i*\fIsqrt\fR\|(4), with digits 0,1,2,3. (Knuth Seminumerical Algorithms section 4.1 and \s-1CACM 1960\s0 pp245\-247.) .IX Xref "Knuth, Donald" .PP The powers of i in the base give the replication direction, so i^0=1 right, i^1=i up, i^2=\-1 right, i^3=\-i down, etc. The power of sqrt(r) then spreads the replication in the respective direction. It takes two steps to repeat horizontally and sqrt(r)^2=r hence the doubling of 1x1 to the right, 2x2 to the left, 4x4 to the right, etc, and similarly vertically. .SS "Negabinary" .IX Subsection "Negabinary" The way blocks repeat horizontally first to the right and then to the left is per the negabinary system base b=\-2. .PP .Vb 1 \& X = x[k]*(\-2)^k + ... + x[2]*(\-2)^2 + x[1]*(\-2) + x[0] .Ve .PP The effect is to represent any positive or negative X by a positive integer index \s-1NX.\s0 .PP .Vb 2 \& X, negabinary: ... \-1 \-2 0 1 2 3 4 5 ... \& index NX: 2 3 0 1 6 7 4 5 .Ve .PP Notice how the 0 point replicates to the right as 1 and then that pair 0,1 replicates to the left as 2,3. Then the block 2,3,0,1 repeats to the right as 6,7,4,5 which the same order with 4 added to each. Then the resulting block of eight repeats to the left similarly, in the same order with 8 added to each. .PP The \f(CW\*(C`ImaginaryBase\*(C'\fR takes the indexes \s-1NX\s0 and \s-1NY\s0 of these negabinary forms and forms N by interleaving the digits (bits) of \s-1NX\s0 and \s-1NY. \s0 That interleaving is in the style of the \f(CW\*(C`ZOrderCurve\*(C'\fR. .PP .Vb 4 \& zX,zY = ZOrderCurve n_to_xy(N) \& X = to_negabinary(zX) \& Y = to_negabinary(zY) \& X,Y equals ImaginaryBase n_to_xy(N) .Ve .PP The \f(CW\*(C`ZOrderCurve\*(C'\fR replicates blocks alternately right and up, whereas for \&\f(CW\*(C`ImaginaryBase\*(C'\fR here it's right,up,left,down repeating. .SS "Radix" .IX Subsection "Radix" The \f(CW\*(C`radix\*(C'\fR parameter controls the radix used to break N into X,Y. For example radix 3 replicates to make 3x1, 3x3, 9x3, 9x9, etc blocks. The replications are radix\-1=2 copies of the preceding level at each stage, .PP .Vb 1 \& radix => 3 \& \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-+\-\-\-\-\-\-\-\-\-\-\-+ \& | 24 25 26 15 16 17 | 6 7 8 | 2 \& | | | \& | 21 22 23 12 13 14 | 3 4 5 | 1 \& | +\-\-\-\-\-\-\-\-\-\-\-+ \& | 18 19 20 9 10 11 | 0 1 2 | <\- Y=0 \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-+\-\-\-\-\-\-\-\-\-\-\-+ \& | 51 52 53 42 43 44 33 34 35 | \-1 \& | | \& | 48 49 50 39 40 41 30 31 32 | \-2 \& | | \& | 45 46 47 36 37 38 27 28 29 | \-3 \& | | \& | 78 79 80 69 70 71 60 61 62 | \-4 \& | | \& | 75 76 77 66 67 68 57 58 59 | \-5 \& | | \& | 72 73 74 63 64 65 54 55 56 | \-6 \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-+ \& ^ \& \-6 \-5 \-4 \-3 \-2 \-1 X=0 1 2 .Ve .PP X,Y are \*(L"negaternary\*(R" in this case, and similar negaradix base=\-radix for higher values. .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::ImaginaryBase\->new ()""" 4 .el .IP "\f(CW$path = Math::PlanePath::ImaginaryBase\->new ()\fR" 4 .IX Item "$path = Math::PlanePath::ImaginaryBase->new ()" .PD 0 .ie n .IP """$path = Math::PlanePath::ImaginaryBase\->new (radix => $r)""" 4 .el .IP "\f(CW$path = Math::PlanePath::ImaginaryBase\->new (radix => $r)\fR" 4 .IX Item "$path = Math::PlanePath::ImaginaryBase->new (radix => $r)" .PD 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. .ie n .IP """($n_lo, $n_hi) = $path\->rect_to_n_range ($x1,$y1, $x2,$y2)""" 4 .el .IP "\f(CW($n_lo, $n_hi) = $path\->rect_to_n_range ($x1,$y1, $x2,$y2)\fR" 4 .IX Item "($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)" The returned range is exact, meaning \f(CW$n_lo\fR and \f(CW$n_hi\fR are the smallest and biggest in the rectangle. .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, $radix**$level \- 1)\*(C'\fR. .SH "FORMULAS" .IX Header "FORMULAS" .SS "Rectangle to N Range" .IX Subsection "Rectangle to N Range" The X and Y ranges can be treated separately and then interleaved, .PP .Vb 2 \& NXmin,NXmax = negaradix range to cover x1..x2 \& NYmin,NYmax = negaradix range to cover y1..y2 \& \& Nmin = interleave digits NXmin, NYmin \& Nmax = interleave digits NXmax, NYmax .Ve .PP If the \s-1NX,NY\s0 ranges are exact then the resulting Nmin,Nmax range is exact. .PP An exact negaradix range can be calculated by digits high to low by considering the range taken by the negaradix form. For example two negaternary digits, .PP .Vb 7 \& N digit 2 1 0 \& +\-\-\-\-\-\-\-\-\-+\-\-\-\-\-\-\-\-\-+\-\-\-\-\-\-\-\-\-+ \& N index | 6 7 8 | 3 4 5 | 0 1 2 | \& +\-\-\-\-\-\-\-\-\-+\-\-\-\-\-\-\-\-\-+\-\-\-\-\-\-\-\-\-+ \& X negaternary \-6 \-5 \-4 \-3 \-2 \-1 0 1 2 \& ^ \& base .Ve .PP Taking the base=\-90909...90 which is the lowest taken (where 9 is the radix digit R\-1), then the next digit of N is the position from X\-base, taken alternately reverse 2,1,0 as shown here or forward 0,1,2. .SH "OEIS" .IX Header "OEIS" Entries in Sloane's Online Encyclopedia of Integer Sequences related to this path include, .Sp .RS 4 (etc) .RE .PP .Vb 2 \& radix=2 \& A057300 permutation N at transpose Y,X (swap bit pairs) \& \& radix=3 \& A163327 permutation N at transpose Y,X (swap trit pairs) \& \& radix=4 \& A126006 permutation N at transpose Y,X (swap digit pairs) \& \& radix=16 \& A217558 permutation N at transpose Y,X (swap digit pairs) .Ve .SH "SEE ALSO" .IX Header "SEE ALSO" Math::PlanePath, Math::PlanePath::ImaginaryHalf, Math::PlanePath::CubicBase, Math::PlanePath::ZOrderCurve .SH "HOME PAGE" .IX Header "HOME PAGE" .SH "LICENSE" .IX Header "LICENSE" Copyright 2011, 2012, 2013, 2014 Kevin Ryde .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 .