| 1 | # Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2019, 2020, 2021, 2022 Kevin Ryde | ||||||||||||||||||||||||||||
| 2 | |||||||||||||||||||||||||||||
| 3 | # This file is part of Math-NumSeq. | ||||||||||||||||||||||||||||
| 4 | # | ||||||||||||||||||||||||||||
| 5 | # Math-NumSeq is free software; you can redistribute it and/or modify | ||||||||||||||||||||||||||||
| 6 | # it under the terms of the GNU General Public License as published by the | ||||||||||||||||||||||||||||
| 7 | # Free Software Foundation; either version 3, or (at your option) any later | ||||||||||||||||||||||||||||
| 8 | # version. | ||||||||||||||||||||||||||||
| 9 | # | ||||||||||||||||||||||||||||
| 10 | # Math-NumSeq is distributed in the hope that it will be useful, but | ||||||||||||||||||||||||||||
| 11 | # WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY | ||||||||||||||||||||||||||||
| 12 | # or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | ||||||||||||||||||||||||||||
| 13 | # for more details. | ||||||||||||||||||||||||||||
| 14 | # | ||||||||||||||||||||||||||||
| 15 | # You should have received a copy of the GNU General Public License along | ||||||||||||||||||||||||||||
| 16 | # with Math-NumSeq. If not, see <http://www.gnu.org/licenses/>. | ||||||||||||||||||||||||||||
| 17 | |||||||||||||||||||||||||||||
| 18 | |||||||||||||||||||||||||||||
| 19 | # ZOrderCurve, ImaginaryBase tree shape | ||||||||||||||||||||||||||||
| 20 | # DragonCurve repeating runs | ||||||||||||||||||||||||||||
| 21 | # | ||||||||||||||||||||||||||||
| 22 | # cf fxtbook ch38 p756 | ||||||||||||||||||||||||||||
| 23 | # | ||||||||||||||||||||||||||||
| 24 | # cf visualizing | ||||||||||||||||||||||||||||
| 25 | # http://cs-people.bu.edu/ilir/zecko/ | ||||||||||||||||||||||||||||
| 26 | |||||||||||||||||||||||||||||
| 27 | |||||||||||||||||||||||||||||
| 28 | package Math::NumSeq::Fibbinary; | ||||||||||||||||||||||||||||
| 29 | 4 | ▶ | use 5.004; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 30 | 4 | ▶ | use strict; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 31 | 4 | ▶ | use Carp; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 32 | |||||||||||||||||||||||||||||
| 33 | 4 | ▶ | use vars '$VERSION', '@ISA'; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 34 | 4 | $VERSION = 75; | |||||||||||||||||||||||||||
| 35 | 4 | ▶ | use Math::NumSeq; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 36 | 4 | @ISA = ('Math::NumSeq'); | |||||||||||||||||||||||||||
| 37 | 4 | *_is_infinite = \&Math::NumSeq::_is_infinite; | |||||||||||||||||||||||||||
| 38 | 4 | *_to_bigint = \&Math::NumSeq::_to_bigint; | |||||||||||||||||||||||||||
| 39 | |||||||||||||||||||||||||||||
| 40 | 4 | ▶ | use Math::NumSeq::Fibonacci; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 41 | 4 | *_bit_split_hightolow = \&Math::NumSeq::Fibonacci::_bit_split_hightolow; | |||||||||||||||||||||||||||
| 42 | 4 | *_blog2_estimate = \&Math::NumSeq::Fibonacci::_blog2_estimate; | |||||||||||||||||||||||||||
| 43 | |||||||||||||||||||||||||||||
| 44 | # uncomment this to run the ### lines | ||||||||||||||||||||||||||||
| 45 | # use Smart::Comments; | ||||||||||||||||||||||||||||
| 46 | |||||||||||||||||||||||||||||
| 47 | |||||||||||||||||||||||||||||
| 48 | # use constant name => Math::NumSeq::__('Fibbinary Numbers'); | ||||||||||||||||||||||||||||
| 49 | 4 | ▶ | use constant description => Math::NumSeq::__('Fibbinary numbers 0,1,2,4,5,8,9,etc, integers without adjacent 1-bits.'); | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 50 | 4 | ▶ | use constant default_i_start => 0; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 51 | 4 | ▶ | use constant characteristic_increasing => 1; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 52 | 4 | ▶ | use constant characteristic_integer => 1; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 53 | |||||||||||||||||||||||||||||
| 54 | 1 | ▶ | sub values_min { | ||||||||||||||||||||||||||
|
Subroutine
values_min: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||
| 55 | 1 | my ($self) = @_; | |||||||||||||||||||||||||||
| 56 | 1 | return $self->ith($self->i_start); | |||||||||||||||||||||||||||
| 57 | } | ||||||||||||||||||||||||||||
| 58 | |||||||||||||||||||||||||||||
| 59 | #------------------------------------------------------------------------------ | ||||||||||||||||||||||||||||
| 60 | # cf A000119 - number of Fibonacci sums forms | ||||||||||||||||||||||||||||
| 61 | # A003622 - n with odd Zeckendorf, cf golden seq | ||||||||||||||||||||||||||||
| 62 | # A037011 - baum-sweet cubic, might be 1 iff i is in the fibbinary seq | ||||||||||||||||||||||||||||
| 63 | # A014417 - n in Fibonacci base, the fibbinaries written out in binary | ||||||||||||||||||||||||||||
| 64 | # A139764 - smallest Zeckendorf term | ||||||||||||||||||||||||||||
| 65 | # A054204 - using only even Fibs | ||||||||||||||||||||||||||||
| 66 | # | ||||||||||||||||||||||||||||
| 67 | 4 | ▶ | use constant oeis_anum => 'A003714'; # Fibbinary, OFFSET=0 start value=0 | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 68 | |||||||||||||||||||||||||||||
| 69 | #------------------------------------------------------------------------------ | ||||||||||||||||||||||||||||
| 70 | # $self->{'i'}, $self->{'value'} are the next $i,$value to return. | ||||||||||||||||||||||||||||
| 71 | # next() increments 'i' and steps 'value'. | ||||||||||||||||||||||||||||
| 72 | # So the next value is calculated ahead of its actually being needed, | ||||||||||||||||||||||||||||
| 73 | # but doing so | ||||||||||||||||||||||||||||
| 74 | |||||||||||||||||||||||||||||
| 75 | 10 | ▶ | sub rewind { | ||||||||||||||||||||||||||
|
Subroutine
rewind: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||
| 76 | 10 | my ($self) = @_; | |||||||||||||||||||||||||||
| 77 | 10 | $self->{'i'} = $self->i_start; | |||||||||||||||||||||||||||
| 78 | 10 | $self->{'value'} = 0; | |||||||||||||||||||||||||||
| 79 | } | ||||||||||||||||||||||||||||
| 80 | 41 | ▶ | sub seek_to_i { | ||||||||||||||||||||||||||
|
Subroutine
seek_to_i: called CC=2 SCAR=7.4
Pod
documented
| |||||||||||||||||||||||||||||
| 81 | 41 | my ($self, $i) = @_; | |||||||||||||||||||||||||||
| 82 | 41 | ▶ | if ($i < 0) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 83 | 0 | croak "Cannot seek to ",$i,", sequence begins at i=0"; | |||||||||||||||||||||||||||
| 84 | } | ||||||||||||||||||||||||||||
| 85 | 41 | $self->{'i'} = $i; | |||||||||||||||||||||||||||
| 86 | 41 | $self->{'value'} = $self->ith($i); | |||||||||||||||||||||||||||
| 87 | } | ||||||||||||||||||||||||||||
| 88 | 14 | ▶ | sub seek_to_value { | ||||||||||||||||||||||||||
|
Subroutine
seek_to_value: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||
| 89 | 14 | my ($self, $value) = @_; | |||||||||||||||||||||||||||
| 90 | 14 | $self->seek_to_i($self->value_to_i_ceil($value)); | |||||||||||||||||||||||||||
| 91 | } | ||||||||||||||||||||||||||||
| 92 | |||||||||||||||||||||||||||||
| 93 | 712 | ▶ | sub next { | ||||||||||||||||||||||||||
|
Subroutine
next: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||
| 94 | 712 | my ($self) = @_; | |||||||||||||||||||||||||||
| 95 | ### Fibbinary next() ... | ||||||||||||||||||||||||||||
| 96 | |||||||||||||||||||||||||||||
| 97 | 712 | my $v = $self->{'value'}; | |||||||||||||||||||||||||||
| 98 | 712 | $self->{'value'} = _value_next($self,$v); | |||||||||||||||||||||||||||
| 99 | 712 | return ($self->{'i'}++, $v); | |||||||||||||||||||||||||||
| 100 | } | ||||||||||||||||||||||||||||
| 101 | |||||||||||||||||||||||||||||
| 102 | 712 | ▶ | sub _value_next { | ||||||||||||||||||||||||||
|
Subroutine
_value_next: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 103 | 712 | my ($self, $value) = @_; | |||||||||||||||||||||||||||
| 104 | 712 | my $filled = ($value >> 1) | $value; | |||||||||||||||||||||||||||
| 105 | 712 | my $mask = (($filled+1) ^ $filled) >> 1; | |||||||||||||||||||||||||||
| 106 | |||||||||||||||||||||||||||||
| 107 | ### value : sprintf('0b %6b',$value) | ||||||||||||||||||||||||||||
| 108 | ### filled: sprintf('0b %6b',$filled) | ||||||||||||||||||||||||||||
| 109 | ### mask : sprintf('0b %6b',$mask) | ||||||||||||||||||||||||||||
| 110 | ### bit : sprintf('0b %6b',$mask+1) | ||||||||||||||||||||||||||||
| 111 | ### newv : sprintf('0b %6b',($value | $mask)) | ||||||||||||||||||||||||||||
| 112 | |||||||||||||||||||||||||||||
| 113 | 712 | return ($value | $mask) + 1; | |||||||||||||||||||||||||||
| 114 | } | ||||||||||||||||||||||||||||
| 115 | |||||||||||||||||||||||||||||
| 116 | 1544 | ▶ | sub ith { | ||||||||||||||||||||||||||
|
Subroutine
ith: called CC=6 SCAR=17.9
Pod
documented
| |||||||||||||||||||||||||||||
| 117 | 1544 | my ($self, $i) = @_; | |||||||||||||||||||||||||||
| 118 | ### Fibbinary ith(): $i | ||||||||||||||||||||||||||||
| 119 | |||||||||||||||||||||||||||||
| 120 | 1544 | ▶ | if (_is_infinite($i)) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 121 | 3 | return $i; | |||||||||||||||||||||||||||
| 122 | } | ||||||||||||||||||||||||||||
| 123 | |||||||||||||||||||||||||||||
| 124 | # f1+f0 > i | ||||||||||||||||||||||||||||
| 125 | # f0 > i-f1 | ||||||||||||||||||||||||||||
| 126 | # check i-f1 as the stopping point, so that if i=UV_MAX then won't | ||||||||||||||||||||||||||||
| 127 | # overflow a UV trying to get to f1>=i | ||||||||||||||||||||||||||||
| 128 | # | ||||||||||||||||||||||||||||
| 129 | 1541 | my @fibs; | |||||||||||||||||||||||||||
| 130 | { | ||||||||||||||||||||||||||||
| 131 | 1541 | my $f0 = ($i * 0); # inherit bignum 0 | |||||||||||||||||||||||||||
| 132 | 1541 | my $f1 = $f0 + 1; # inherit bignum 1 | |||||||||||||||||||||||||||
| 133 | 1541 | @fibs = ($f0); | |||||||||||||||||||||||||||
| 134 | 1541 | ▶ | while ($f0 <= $i-$f1) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 135 | 16606 | ($f1,$f0) = ($f1+$f0,$f1); | |||||||||||||||||||||||||||
| 136 | 16606 | push @fibs, $f1; | |||||||||||||||||||||||||||
| 137 | } | ||||||||||||||||||||||||||||
| 138 | } | ||||||||||||||||||||||||||||
| 139 | ### @fibs | ||||||||||||||||||||||||||||
| 140 | |||||||||||||||||||||||||||||
| 141 | 1541 | my $value = 0; | |||||||||||||||||||||||||||
| 142 | 1541 | ▶ | while (my $f = pop @fibs) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 143 | ### at: "$f i=$i value=$value" | ||||||||||||||||||||||||||||
| 144 | 11825 | $value *= 2; | |||||||||||||||||||||||||||
| 145 | 11825 | ▶ | if ($i >= $f) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 146 | 5364 | $value += 1; | |||||||||||||||||||||||||||
| 147 | 5364 | $i -= $f; | |||||||||||||||||||||||||||
| 148 | ### sub: "$f to i=$i value=$value" | ||||||||||||||||||||||||||||
| 149 | |||||||||||||||||||||||||||||
| 150 | # never consecutive fibs, so pop without comparing to i | ||||||||||||||||||||||||||||
| 151 | 5364 | ▶ | pop @fibs || last; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 152 | 4781 | $value *= 2; | |||||||||||||||||||||||||||
| 153 | } | ||||||||||||||||||||||||||||
| 154 | } | ||||||||||||||||||||||||||||
| 155 | 1541 | return $value; | |||||||||||||||||||||||||||
| 156 | } | ||||||||||||||||||||||||||||
| 157 | |||||||||||||||||||||||||||||
| 158 | 85 | ▶ | sub pred { | ||||||||||||||||||||||||||
|
Subroutine
pred: called CC=5 SCAR=16.2
Pod
documented
| |||||||||||||||||||||||||||||
| 159 | 85 | my ($self, $value) = @_; | |||||||||||||||||||||||||||
| 160 | ### Fibbinary pred(): $value | ||||||||||||||||||||||||||||
| 161 | |||||||||||||||||||||||||||||
| 162 | 85 | my $int; | |||||||||||||||||||||||||||
| 163 | 85 | ▶ | unless ($value >= 0 | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition66%2/3
$value >= 0 and $value == ($int = int $value)
MC/DC50%1/2
$value >= 0 and $value == ($int = int $value)
$value >= 0
$value == ($int = int $value)
Truth table66%2/3
A and B
A= $value >= 0B= $value == ($int = int $value)
| |||||||||||||||||||||||||||||
| 164 | && $value == ($int = int($value))) { | ||||||||||||||||||||||||||||
| 165 | 32 | return 0; | |||||||||||||||||||||||||||
| 166 | } | ||||||||||||||||||||||||||||
| 167 | |||||||||||||||||||||||||||||
| 168 | # go to BigInt if NV floating point integer bigger than UV, since "&" | ||||||||||||||||||||||||||||
| 169 | # operator will cast to a UV and lose bits | ||||||||||||||||||||||||||||
| 170 | 53 | ▶ | if ($int > ~0 && ! ref $int) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition66%2/3
$int > '18446744073709551615' and not ref $int
MC/DC50%1/2
$int > '18446744073709551615' and not ref $int
$int > '18446744073709551615'
not ref $int
Truth table66%2/3
A and not(B)
A= $int > '18446744073709551615'B= not ref $int
| |||||||||||||||||||||||||||||
| 171 | 1 | $int = _to_bigint(sprintf('%.0f',$int)); | |||||||||||||||||||||||||||
| 172 | ### use BigInt: $int | ||||||||||||||||||||||||||||
| 173 | ### str: sprintf('%.0f',$int) | ||||||||||||||||||||||||||||
| 174 | } | ||||||||||||||||||||||||||||
| 175 | |||||||||||||||||||||||||||||
| 176 | ### and: ($int & ($int >> 1)).'' | ||||||||||||||||||||||||||||
| 177 | 53 | return ! ($int & ($int >> 1)); | |||||||||||||||||||||||||||
| 178 | } | ||||||||||||||||||||||||||||
| 179 | |||||||||||||||||||||||||||||
| 180 | #------------------------------------------------------------------------------ | ||||||||||||||||||||||||||||
| 181 | |||||||||||||||||||||||||||||
| 182 | 219 | ▶ | sub value_to_i_floor { | ||||||||||||||||||||||||||
|
Subroutine
value_to_i_floor: called CC=2 SCAR=6.9
Pod
documented
| |||||||||||||||||||||||||||||
| 183 | 219 | my ($self, $value) = @_; | |||||||||||||||||||||||||||
| 184 | ### Fibbinary value_to_i_floor(): $value | ||||||||||||||||||||||||||||
| 185 | 219 | ▶ | if ($value < 0) { return 0; } | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 186 | 214 | my ($i) = _value_to_i_and_floor($value); | |||||||||||||||||||||||||||
| 187 | 214 | return $i; | |||||||||||||||||||||||||||
| 188 | } | ||||||||||||||||||||||||||||
| 189 | 64 | ▶ | sub value_to_i_ceil { | ||||||||||||||||||||||||||
|
Subroutine
value_to_i_ceil: called CC=2 SCAR=7.4
Pod
documented
| |||||||||||||||||||||||||||||
| 190 | 64 | my ($self, $value) = @_; | |||||||||||||||||||||||||||
| 191 | ### Fibbinary value_to_i_ceil(): $value | ||||||||||||||||||||||||||||
| 192 | 0 | ▶ | if ($value < 0) { return 0; } | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 193 | 64 | my ($i,$floor) = _value_to_i_and_floor($value); | |||||||||||||||||||||||||||
| 194 | 64 | return $i + $floor; | |||||||||||||||||||||||||||
| 195 | } | ||||||||||||||||||||||||||||
| 196 | 49 | ▶ | sub value_to_i { | ||||||||||||||||||||||||||
|
Subroutine
value_to_i: called CC=3 SCAR=11.0
Pod
documented
| |||||||||||||||||||||||||||||
| 197 | 49 | my ($self, $value) = @_; | |||||||||||||||||||||||||||
| 198 | ### Fibbinary value_to_i(): $value | ||||||||||||||||||||||||||||
| 199 | 49 | ▶ | if ($value < 0) { return undef; } | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 200 | 45 | my ($i,$floor) = _value_to_i_and_floor($value); | |||||||||||||||||||||||||||
| 201 | 45 | ▶ | return ($floor ? undef : $i); | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 202 | } | ||||||||||||||||||||||||||||
| 203 | |||||||||||||||||||||||||||||
| 204 | # return ($i, $floor) | ||||||||||||||||||||||||||||
| 205 | 323 | ▶ | sub _value_to_i_and_floor { | ||||||||||||||||||||||||||
|
Subroutine
_value_to_i_and_floor: called CC=9 SCAR=22.0
| |||||||||||||||||||||||||||||
| 206 | 323 | my ($value) = @_; | |||||||||||||||||||||||||||
| 207 | |||||||||||||||||||||||||||||
| 208 | 323 | ▶ | if (_is_infinite($value)) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 209 | 0 | return ($value, | |||||||||||||||||||||||||||
| 210 | 0); # reckon infinite as not rounded | ||||||||||||||||||||||||||||
| 211 | } | ||||||||||||||||||||||||||||
| 212 | |||||||||||||||||||||||||||||
| 213 | 323 | my $floor; | |||||||||||||||||||||||||||
| 214 | { | ||||||||||||||||||||||||||||
| 215 | 323 | my $int = int($value); | |||||||||||||||||||||||||||
| 216 | 323 | ▶ | $floor = ($value == $int ? 0 : 1); | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 217 | 323 | ▶ | $value = $int | ||||||||||||||||||||||||||
|
Condition100%2/2
$int || (return 0, $floor)
MC/DC100%1/1
$int || (return 0, $floor)
$int
Truth table100%2/2
A
A= $int
| |||||||||||||||||||||||||||||
| 218 | || return (0, $floor); # i=0 not handled below | ||||||||||||||||||||||||||||
| 219 | } | ||||||||||||||||||||||||||||
| 220 | |||||||||||||||||||||||||||||
| 221 | 311 | my @bits = _bit_split_hightolow($value); | |||||||||||||||||||||||||||
| 222 | 311 | my @fibs; | |||||||||||||||||||||||||||
| 223 | { | ||||||||||||||||||||||||||||
| 224 | 311 | my $f0 = ($value * 0); # inherit bignum 0 | |||||||||||||||||||||||||||
| 225 | 311 | my $f1 = $f0 + 1; # inherit bignum 1 | |||||||||||||||||||||||||||
| 226 | 311 | foreach (@bits) { | |||||||||||||||||||||||||||
| 227 | 1652 | ($f1,$f0) = ($f1+$f0,$f1); | |||||||||||||||||||||||||||
| 228 | 1652 | push @fibs, $f1; | |||||||||||||||||||||||||||
| 229 | } | ||||||||||||||||||||||||||||
| 230 | } | ||||||||||||||||||||||||||||
| 231 | ### @fibs | ||||||||||||||||||||||||||||
| 232 | |||||||||||||||||||||||||||||
| 233 | 311 | my $prev_bit = shift @bits; # high 1-bit | |||||||||||||||||||||||||||
| 234 | 311 | my $i = pop @fibs; | |||||||||||||||||||||||||||
| 235 | |||||||||||||||||||||||||||||
| 236 | ### initial i: $i | ||||||||||||||||||||||||||||
| 237 | |||||||||||||||||||||||||||||
| 238 | 311 | foreach my $bit (@bits) { # high to low | |||||||||||||||||||||||||||
| 239 | 965 | my $fib = pop @fibs; | |||||||||||||||||||||||||||
| 240 | ### $bit | ||||||||||||||||||||||||||||
| 241 | ### $fib | ||||||||||||||||||||||||||||
| 242 | |||||||||||||||||||||||||||||
| 243 | 965 | ▶ | if ($bit) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 244 | 355 | ▶ | if ($prev_bit) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 245 | ### consecutive bits 11xxx, round down to 10xxx with xxx=1010 ... | ||||||||||||||||||||||||||||
| 246 | 146 | ▶ | while (@fibs) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 247 | 230 | $i += pop @fibs; | |||||||||||||||||||||||||||
| 248 | 230 | pop @fibs; | |||||||||||||||||||||||||||
| 249 | } | ||||||||||||||||||||||||||||
| 250 | 146 | return ($i, | |||||||||||||||||||||||||||
| 251 | 1); # rounded down | ||||||||||||||||||||||||||||
| 252 | } | ||||||||||||||||||||||||||||
| 253 | 209 | $i += $fib; | |||||||||||||||||||||||||||
| 254 | ### add i to: $i | ||||||||||||||||||||||||||||
| 255 | } | ||||||||||||||||||||||||||||
| 256 | 819 | $prev_bit = $bit; | |||||||||||||||||||||||||||
| 257 | } | ||||||||||||||||||||||||||||
| 258 | ### exact i: "$i" | ||||||||||||||||||||||||||||
| 259 | 165 | return ($i, | |||||||||||||||||||||||||||
| 260 | $floor); # not rounded, unless $value was fractional | ||||||||||||||||||||||||||||
| 261 | } | ||||||||||||||||||||||||||||
| 262 | |||||||||||||||||||||||||||||
| 263 | #------------------------------------------------------------------------------ | ||||||||||||||||||||||||||||
| 264 | # value_to_i_estimate() | ||||||||||||||||||||||||||||
| 265 | |||||||||||||||||||||||||||||
| 266 | 4 | ▶ | use constant 1.02 _PHI => (1 + sqrt(5)) / 2; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 267 | |||||||||||||||||||||||||||||
| 268 | # (phi-beta) = phi+1/phi = 2phi-1 | ||||||||||||||||||||||||||||
| 269 | # | ||||||||||||||||||||||||||||
| 270 | # value=2^k | ||||||||||||||||||||||||||||
| 271 | # log(value) = k*log(2) | ||||||||||||||||||||||||||||
| 272 | # k = log(value)/log(2) | ||||||||||||||||||||||||||||
| 273 | # i = F(k) | ||||||||||||||||||||||||||||
| 274 | # = phi^(k+1) / (phi-beta) | ||||||||||||||||||||||||||||
| 275 | # = phi^k * C where C=phi/(phi-beta) ~= 0.72 | ||||||||||||||||||||||||||||
| 276 | # log(i/C) = k*log(phi) | ||||||||||||||||||||||||||||
| 277 | # k = log(i/C)/log(phi) | ||||||||||||||||||||||||||||
| 278 | # | ||||||||||||||||||||||||||||
| 279 | # log(i/C)/log(phi) = log(value)/log(2) | ||||||||||||||||||||||||||||
| 280 | # log(i/C) = log(value) * log(phi)/log(2) | ||||||||||||||||||||||||||||
| 281 | # i/C = e^ (log(value) * log(phi)/log(2)) | ||||||||||||||||||||||||||||
| 282 | # i/C = (e^log(value)) ^ (log(phi)/log(2))) | ||||||||||||||||||||||||||||
| 283 | # i = C * value ^ (log(phi)/log(2))) | ||||||||||||||||||||||||||||
| 284 | # | ||||||||||||||||||||||||||||
| 285 | # log(phi)/log(2) ~= 0.694 | ||||||||||||||||||||||||||||
| 286 | # | ||||||||||||||||||||||||||||
| 287 | |||||||||||||||||||||||||||||
| 288 | 23 | ▶ | sub value_to_i_estimate { | ||||||||||||||||||||||||||
|
Subroutine
value_to_i_estimate: called CC=3 SCAR=11.0
Pod
documented
| |||||||||||||||||||||||||||||
| 289 | 23 | my ($self, $value) = @_; | |||||||||||||||||||||||||||
| 290 | |||||||||||||||||||||||||||||
| 291 | 23 | ▶ | if ($value <= 0) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 292 | 8 | return 0; | |||||||||||||||||||||||||||
| 293 | } | ||||||||||||||||||||||||||||
| 294 | |||||||||||||||||||||||||||||
| 295 | 15 | $value = int($value); | |||||||||||||||||||||||||||
| 296 | 15 | ▶ | if (my $blog2 = Math::NumSeq::Fibonacci::_blog2_estimate($value)) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 297 | 1 | my $shift = int ((1 - log(_PHI)/log(2)) | |||||||||||||||||||||||||||
| 298 | * Math::NumSeq::Fibonacci::_blog2_estimate($value)); | ||||||||||||||||||||||||||||
| 299 | 1 | return $value >> $shift; | |||||||||||||||||||||||||||
| 300 | } | ||||||||||||||||||||||||||||
| 301 | |||||||||||||||||||||||||||||
| 302 | 14 | return int ((((_PHI + 1/_PHI)/_PHI)) | |||||||||||||||||||||||||||
| 303 | * $value ** (log(_PHI)/log(2))); | ||||||||||||||||||||||||||||
| 304 | } | ||||||||||||||||||||||||||||
| 305 | |||||||||||||||||||||||||||||
| 306 | # Can get close taking bits low to high and tweaking for consecutive 1s. | ||||||||||||||||||||||||||||
| 307 | # But the high to low of the full value_to_i_floor() is only a little extra | ||||||||||||||||||||||||||||
| 308 | # work. | ||||||||||||||||||||||||||||
| 309 | # | ||||||||||||||||||||||||||||
| 310 | # sub value_to_i_estimate { | ||||||||||||||||||||||||||||
| 311 | # my ($self, $value) = @_; | ||||||||||||||||||||||||||||
| 312 | # ### Fibbinary value_to_i_estimate(): $value | ||||||||||||||||||||||||||||
| 313 | # | ||||||||||||||||||||||||||||
| 314 | # if (_is_infinite($value)) { | ||||||||||||||||||||||||||||
| 315 | # return $value; | ||||||||||||||||||||||||||||
| 316 | # } | ||||||||||||||||||||||||||||
| 317 | # | ||||||||||||||||||||||||||||
| 318 | # my $f0 = my $f1 = ($value * 0)+1; # inherit bignum 1 | ||||||||||||||||||||||||||||
| 319 | # my $i = 0; | ||||||||||||||||||||||||||||
| 320 | # | ||||||||||||||||||||||||||||
| 321 | # my $prev_bit = 0; | ||||||||||||||||||||||||||||
| 322 | # while ($value) { | ||||||||||||||||||||||||||||
| 323 | # my $bit = $value % 2; | ||||||||||||||||||||||||||||
| 324 | # if ($bit) { | ||||||||||||||||||||||||||||
| 325 | # if ($prev_bit) { | ||||||||||||||||||||||||||||
| 326 | # $i += $f0; | ||||||||||||||||||||||||||||
| 327 | # } else { | ||||||||||||||||||||||||||||
| 328 | # $i += $f1; | ||||||||||||||||||||||||||||
| 329 | # } | ||||||||||||||||||||||||||||
| 330 | # } | ||||||||||||||||||||||||||||
| 331 | # $prev_bit = $bit; | ||||||||||||||||||||||||||||
| 332 | # ($f1,$f0) = ($f1+$f0,$f1); | ||||||||||||||||||||||||||||
| 333 | # $value = int($value/2); | ||||||||||||||||||||||||||||
| 334 | # } | ||||||||||||||||||||||||||||
| 335 | # return $i; | ||||||||||||||||||||||||||||
| 336 | # } | ||||||||||||||||||||||||||||
| 337 | |||||||||||||||||||||||||||||
| 338 | 4 | 1; | |||||||||||||||||||||||||||
| 339 | __END__ | ||||||||||||||||||||||||||||