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

FUNCTIONS

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

FORMULAS

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

SEE ALSO

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

HOME PAGE

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

LICENSE

236       Copyright 2011, 2012, 2013, 2014, 2015, 2016 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.30.1                      2020-01-30        Math::NumSeq::Fibbinary(3)
Impressum