1Math::NumSeq::FibbinaryU(s3e)r Contributed Perl DocumentaMtaitohn::NumSeq::Fibbinary(3)
2
3
4

NAME

6       Math::NumSeq::Fibbinary -- without consecutive 1-bits
7

SYNOPSIS

9        use Math::NumSeq::Fibbinary;
10        my $seq = Math::NumSeq::Fibbinary->new;
11        my ($i, $value) = $seq->next;
12

DESCRIPTION

14       This sequence is the Fibbinary numbers
15
16            0, 1, 2, 4, 5, 8, 9, 10, 16, 17, 18, 20, 21, 32, 33, 34, ...
17            starting i=0       (A003714)
18
19       They have no adjacent 1-bits when written in binary,
20
21           i     Fibbinary    Fibbinary
22                 (decimal)    (binary)
23          ---    ---------    --------
24           0         0             0
25           1         1             1
26           2         2            10
27           3         4           100
28           4         5           101
29           5         8          1000
30           6         9          1001
31           7        10          1010
32           8        16         10000
33           9        17         10001
34
35       For example at i=4 Fibbinary is 5.  The next Fibbinary is not 6 or 7
36       because they have adjacent 1-bits (110 and 111), the next without
37       adjacent 1s is 8 (100).
38
39       The two highest bits must be "10...", they cannot be "11...".  So
40       there's effectively a block of 2^k values (not all used) followed by a
41       gap of 2^k values, etc.
42
43       The least significant bit of each Fibbinary is the Fibonacci word
44       sequence, per Math::NumSeq::FibonacciWord.
45
46       All numbers without adjacent 1-bits can also be generated simply by
47       taking the binary expansion and changing each "1" to "01", but that
48       doesn't given them in ascending order the way the Fibbinary here does.
49
50   Zeckendorf Base
51       The bits of the Fibbinary values encode Fibonacci numbers used to
52       represent i in Zeckendorf style Fibonacci base.  In the Zeckendorf base
53       system, an integer i is a sum of Fibonacci numbers,
54
55           i = F[k1] + F[k2] + ... F[kn]         k1 > k2 > ... > kn
56
57       Each k is chosen as the highest Fibonacci less than the remainder at
58       that point.  For example, reckoning the Fibonaccis as F[0]=1, F[2]=2,
59       etc
60
61           19 = 13+5+1 = F[5] + F[3] + F[0]
62
63       The k's are then assembled as 1-bits in binary to encode this sum in an
64       integer,
65
66           Fibbinary(19) = 2^5 + 2^3 + 2^0 = 41
67
68       The gaps between Fibonacci numbers mean that after subtracting F(k)
69       from i, the next cannot be F(k-1), it must be F(k-2) or less.  For that
70       reason there's no adjacent 1-bits in the Fibbinary numbers.
71
72       The connection between no adjacent 1s and the Fibonacci sequence can be
73       seen by considering values with high bit 2^k.  The further bits in it
74       cannot have 2^(k-1) but only 2^(k-2), so effectively the number of new
75       values are not from the previous k-1 but the second previous k-2, the
76       same way as the Fibonacci sequence adds not the previous term (which
77       would by double) but the one before instead.
78

FUNCTIONS

80       See "FUNCTIONS" in Math::NumSeq for behaviour common to all sequence
81       classes.
82
83       "$seq = Math::NumSeq::Fibbinary->new ()"
84           Create and return a new sequence object.
85
86   Iterating
87       "$seq->seek_to_i($i)"
88       "$seq->seek_to_value($value)"
89           Move the current i so next() will return $i or $value on the next
90           call.  If $value is not in the sequence then move so as to return
91           the next higher value which is.
92
93   Random Access
94       "$value = $seq->ith($i)"
95           Return the $i'th Fibbinary number.
96
97       "$bool = $seq->pred($value)"
98           Return true if $value is a Fibbinary number, which means that in
99           binary it doesn't have any consecutive 1-bits.
100
101       "$i = $seq->value_to_i($value)"
102       "$i = $seq->value_to_i_ceil($value)"
103       "$i = $seq->value_to_i_floor($value)"
104           Return the index i of $value.  If $value is not in the sequence
105           then value_to_i() returns "undef", or value_to_i_ceil() returns the
106           i of the next higher value which is, or value_to_i_floor() the i of
107           the next lower value.
108
109       "$i = $seq->value_to_i_estimate($value)"
110           Return an estimate of the i corresponding to $value.
111

FORMULAS

113   Next Value
114       For a given Fibbinary number, the next Fibbinary is +1 if the lowest
115       bit is 2^2=4 or more.  If however the low bit is 2^1=2 or 2^0=1 then
116       the run of low alternating ...101 or ...1010 must be cleared and the
117       bit above set.  For example 1001010 becomes 1010000.  All cases can be
118       handled by some bit twiddling
119
120           # value=Fibbinary
121           filled = (value >> 1) | value
122           mask = ((filled+1) ^ filled) >> 1
123           next value = (value | mask) + 1
124
125       For example
126
127           value  = 1001010
128           filled = 1101111
129           mask   =    1111
130           next   = 1010000
131
132       "filled" means trailing ...01010 has the zeros filled in to ...01111.
133       Then those low ones can be extracted with +1 and XOR (the usual trick
134       for getting low ones).  +1 means the bit above the filled part is
135       included so 11111, but a shift drops back to "mask" just 01111.  OR-ing
136       and incrementing then clears those low bits and sets the next higher
137       bit to make ...10000.
138
139       This works for any Fibbinary input, both odd "...10101" and even
140       "...1010" endings and also zeros "...0000".  In the zeros case the
141       result is just a +1 for "...0001", and that includes input value=0
142       giving next=1.
143
144   Ith Value
145       The i'th Fibbinary number can be calculated as per "Zeckendorf Base"
146       above.  Reckoning the Fibonacci numbers as F(0)=1, F(1)=2, F(2)=3,
147       F(3)=5, etc,
148
149           find the biggest F(k) <= i
150           subtract i -= F(k)
151           Fibbinary result += 2^k
152           repeat until i=0
153
154       To find each F(k)<=i either just work downwards through the Fibonacci
155       numbers, or the Fibonaccis grow as (phi^k)/sqrt(5) with
156       phi=(sqrt(5)+1)/2 the golden ratio, so an F(k) could be found by a log
157       base phi of i.  Or taking log2 of i (the bit length of i) might give 2
158       or 3 candidates for k.  Calculating log base phi is unlikely to be
159       faster, but log 2 high bit should quickly go to a nearly-correct place
160       in a table.
161
162   Predicate
163       Testing for a Fibbinary value can be done by a shift and AND,
164
165           is_Fibbinary = ((value & (value >> 1)) == 0)
166
167       Any adjacent 1-bits overlap in the shift+AND and come through as non-
168       zero.
169
170       Perl "&" operator converts NV float to UV integer.  If an NV value is
171       an integer but bigger than a UV then bits will be lost to the "&".
172       Conversion to "Math::BigInt" or similar is necessary to preserve the
173       full value.
174
175       Floats which are integers but bigger than an UV might be of interest,
176       or it might be thought any float means rounded-off and therefore
177       inaccurate and not of interest.  The current code has some experimental
178       automatic BigInt conversion which works for floats and for BigFloat or
179       BigRat integers too, but don't rely on this quite yet.  (A BigInt input
180       directly is fine of course.)
181
182   Value to i Floor
183       In a Fibbinary value each bit becomes a Fibonacci F[i] to add to make
184       i, as per "Zeckendorf Base" above.
185
186       If a number is not a Fibbinary then the next lower Fibbinary can be had
187       by finding the highest 11 pair and changing it and all the bits below
188       to 101010...etc.  For example 10011001 is not a Fibbinary and must
189       change down to 10010101, ie. the 11001 reduces to 10101, that being the
190       biggest Fibbinary no-adjacent-1s which is 10xxx.
191
192           bits 2^k from high to low
193             if bit set
194               if prev bit set too
195               then treat remainder as 010101...
196               else i += F[k]
197
198       If working downwards adding F[k] values then it's easy enough to notice
199       an adjacent 11 pair.  An alternative would be to find all 11 pairs by
200       bit-twiddling per "Predicate" above and the highest 1-bit (if any) of
201       those is the place to mangle.
202
203   Value to i Estimate
204       In general i grows as a power of phi=1.618 and the values grow as a
205       power of 2.  So an estimate can be had from
206
207           value = 2^k
208           i = F[k+1]
209             ~= phi^(k+1) / (phi + 1/phi)
210             ~= C * phi^k
211           where C=phi/(phi + 1/phi)
212
213           log(i/C)/log(phi) ~= log(value)/log(2)
214
215           i_estimate = C * value^(log(phi)/log(2))
216
217       The power log(phi)/log(2)=0.694 reduces the value to give an i
218       approximation.  That power can also be approximated by shifting off the
219       least significant 1-0.694=0.306 of the bits of the value.  This is fast
220       and may be enough accuracy for a bigint.
221
222           highbitpos of value
223           i_estimate = value >> floor(highbitpos * 0.306)
224

SEE ALSO

226       Math::NumSeq, Math::NumSeq::Fibonacci, Math::NumSeq::FibonacciWord,
227       Math::NumSeq::GolayRudinShapiro, Math::NumSeq::BaumSweet
228
229       Math::Fibonacci decompose()
230

HOME PAGE

232       <http://user42.tuxfamily.org/math-numseq/index.html>
233

LICENSE

235       Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2019, 2020, 2021, 2022
236       Kevin Ryde
237
238       Math-NumSeq is free software; you can redistribute it and/or modify it
239       under the terms of the GNU General Public License as published by the
240       Free Software Foundation; either version 3, or (at your option) any
241       later version.
242
243       Math-NumSeq is distributed in the hope that it will be useful, but
244       WITHOUT ANY WARRANTY; without even the implied warranty of
245       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
246       General Public License for more details.
247
248       You should have received a copy of the GNU General Public License along
249       with Math-NumSeq.  If not, see <http://www.gnu.org/licenses/>.
250
251
252
253perl v5.38.0                      2023-07-20        Math::NumSeq::Fibbinary(3)
Impressum