1Math::NumSeq::FibbinaryU(s3e)r Contributed Perl DocumentaMtaitohn::NumSeq::Fibbinary(3)
2
6 Math::NumSeq::Fibbinary -- without consecutive 1-bits
7
9 use Math::NumSeq::Fibbinary;
10 my $seq = Math::NumSeq::Fibbinary->new;
11 my ($i, $value) = $seq->next;
12
14 This sequence is the fibbinary numbers
15 0, 1, 2, 4, 5, 8, 9, 10, 16, 17, 18, 20, 21, 32, 33, 34, ...
17 starting i=0
18 being integers which have no adjacent 1-bits when written in binary,
20 taken in ascending order.
21 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 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 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 The least significant bit of each fibbinary is the Fibonacci word
45 sequence, per Math::NumSeq::FibonacciWord.
46 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 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 i = F[k1] + F[k2] + ... F[kn] k1 > k2 > ... > kn
57 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 19 = 13+5+1 = F[5]+F[3]+F[0]
63 The k's are then assembled as 1-bits in binary to encode this sum in an
65 integer,
66 fibbinary(19) = 2^5 + 2^3 + 2^0 = 41
68 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 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
81 See "FUNCTIONS" in Math::NumSeq for behaviour common to all sequence
82 classes.
83 "$seq = Math::NumSeq::Fibbinary->new ()"
85 Create and return a new sequence object.
86 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 Random Access
95 "$value = $seq->ith($i)"
96 Return the $i'th fibbinary number.
97 "$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 "$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 "$i = $seq->value_to_i_estimate($value)"
111 Return an estimate of the i corresponding to $value.
112
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 # value=fibbinary
122 filled = (value >> 1) | value
123 mask = ((filled+1) ^ filled) >> 1
124 next value = (value | mask) + 1
125 For example
127 value = 1001010
129 filled = 1101111
130 mask = 1111
131 next = 1010000
132 "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 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 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 find the biggest F(k) <= i
151 subtract i -= F(k)
152 fibbinary result += 2^k
153 repeat until i=0
154 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 Predicate
164 Testing for a fibbinary value can be done by a shift and AND,
165 is_fibbinary = ((value & (value >> 1)) == 0)
167 Any adjacent 1-bits overlap in the shift+AND and come through as non-
169 zero.
170 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 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 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 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 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 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 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 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 log(i/C)/log(phi) ~= log(value)/log(2)
215 i_estimate = C * value^(log(phi)/log(2))
217 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 highbitpos of value
224 i_estimate = value >> floor(highbitpos * 0.306)
225
227 Math::NumSeq, Math::NumSeq::Fibonacci, Math::NumSeq::FibonacciWord,
228 Math::NumSeq::GolayRudinShapiro, Math::NumSeq::BaumSweet
229 Math::Fibonacci "decompose()"
231
233 <http://user42.tuxfamily.org/math-numseq/index.html>
234
236 Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2019 Kevin Ryde
237 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 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 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/>.
250perl v5.32.0 2020-07-28 Math::NumSeq::Fibbinary(3)