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 (A003714)
18 They have no adjacent 1-bits when written in binary,
20 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 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 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 The least significant bit of each Fibbinary is the Fibonacci word
44 sequence, per Math::NumSeq::FibonacciWord.
45 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 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 i = F[k1] + F[k2] + ... F[kn] k1 > k2 > ... > kn
56 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 19 = 13+5+1 = F[5] + F[3] + F[0]
62 The k's are then assembled as 1-bits in binary to encode this sum in an
64 integer,
65 Fibbinary(19) = 2^5 + 2^3 + 2^0 = 41
67 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 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
80 See "FUNCTIONS" in Math::NumSeq for behaviour common to all sequence
81 classes.
82 "$seq = Math::NumSeq::Fibbinary->new ()"
84 Create and return a new sequence object.
85 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 Random Access
94 "$value = $seq->ith($i)"
95 Return the $i'th Fibbinary number.
96 "$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 "$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 "$i = $seq->value_to_i_estimate($value)"
110 Return an estimate of the i corresponding to $value.
111
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 # value=Fibbinary
121 filled = (value >> 1) | value
122 mask = ((filled+1) ^ filled) >> 1
123 next value = (value | mask) + 1
124 For example
126 value = 1001010
128 filled = 1101111
129 mask = 1111
130 next = 1010000
131 "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 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 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 find the biggest F(k) <= i
150 subtract i -= F(k)
151 Fibbinary result += 2^k
152 repeat until i=0
153 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 Predicate
163 Testing for a Fibbinary value can be done by a shift and AND,
164 is_Fibbinary = ((value & (value >> 1)) == 0)
166 Any adjacent 1-bits overlap in the shift+AND and come through as non-
168 zero.
169 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 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 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 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 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 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 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 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 log(i/C)/log(phi) ~= log(value)/log(2)
214 i_estimate = C * value^(log(phi)/log(2))
216 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 highbitpos of value
223 i_estimate = value >> floor(highbitpos * 0.306)
224
226 Math::NumSeq, Math::NumSeq::Fibonacci, Math::NumSeq::FibonacciWord,
227 Math::NumSeq::GolayRudinShapiro, Math::NumSeq::BaumSweet
228 Math::Fibonacci decompose()
230
232 <http://user42.tuxfamily.org/math-numseq/index.html>
233
235 Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2019, 2020, 2021, 2022
236 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.38.0 2023-07-20 Math::NumSeq::Fibbinary(3)