Talk:Fibonacci coding
From Wikipedia, the free encyclopedia
Contents |
[edit] Big-endian and little-endian?
Can anyone substantiate the premise that there are two separate incompatible systems, big-endian and little-endian, for encoding integers as the sum of Fibonacci numbers? I can find no verification of this and would like to see some before we change the page entirely to reflect this idea. -- Antaeus Feldspar 21:08, 3 Feb 2005 (UTC)
- Big-endian just means that the bits are arranged in least-to-most significant order. Little-endian means that they are sorted most-to-least. Given the description of the code here, I would assume that big-endian is the only possibility. Ravenswood 21:39, 28 Apr 2005 (UTC)
- Well, the "big-endian" system described is not actually impossible, but a) 1 cannot be encoded in it, since there is no leading "10" to remove, and b) it seems an unnecessary complication for no reward. -- Antaeus Feldspar 22:23, 28 Apr 2005 (UTC)
[edit] Ooph
How about this:
To find the Fibonacci code for a number x, start with the code for x-1 and remove the 011 at the end. Assuming the resulting number to be little-endian, add 1 repeatedly until the result does not include the sequence "11". If the result exceeds the number of digits in the previous result, start over with that number of zeroes plus one.
Of course it could be written better, but there's my idea :-) --67.172.99.160 23:53, 25 August 2005 (UTC)
[edit] Example
Fibonacci numbers: 0, 1, 1, 2, 3, 5, 8, 13... Nth unique FN: 1.,2.,..,3.,4.,5.,6.,7.,..
calculate Fibonacci coding for 11: 11 = 8 + 3 8 is the 6th unique FN, 3 is the 4th unique FN, therefore:
1 1
digits 123456
putting a 1 after the last 1 and filling up with 0's:
0001011
digits 1234567
but the article says
001011
digits 123456
(one digit less).
Did I assume the wrong Fibonacci numbers? (removing zero from the Fibonacci numbers works). --Abdull 17:15, 9 March 2006 (UTC)
I think you already figured it out, but for the benefit of others who might read this:
Unique, non-zero Fibonacci numbers: 1, 2, 3, 5, 8, 13, 21, ... Nth unique non-zero FN: 1, 2, 3, 4, 5, 6, 7, ...
calculate Fibonacci coding for 11: 11 = 8 + 3 8 is the 5th unique non-zero FN, 3 is the 3th unique non-zero FN, therefore:
1 1
digits 1 2 3 4 5
value 1 2 3 5 8
putting a 1 after the last 1 and filling up with 0's:
0 0 1 0 1 1 == fibonacci code for eleven.
digits 1 2 3 4 5
value 1 2 3 5 8
Is there some way to clarify the main article to make this obvious? --68.0.120.35 22:18, 16 January 2007 (UTC)
[edit] Merge discussion
See Talk:Zeckendorf's theorem. --N Shar 18:18, 20 February 2007 (UTC)
[edit] Sample Code
This is a piece of Java code that will output natural numbers, followed by its decomposition as a Fibonacci sum and its Fibonacci coding. That is:
16 = 3+13 > 0010011
17 = 1+3+13 > 1010011
18 = 5+13 > 0001011
19 = 1+5+13 > 1001011
I think this would be a good starting point for anyone that wants "put the hands" on Fibonacci coding, and could improve the corresponding article, but It would be good to hear more opinions on the matter.
public class Zeckendorf {
static int[] fibos;
static int maxBinaryDigits = 10;
public static void main(String[] args) {
int a = 0, b = 1, c = a;
fibos = new int[maxBinaryDigits + 1];
System.out.println("Fibos:");
for (int i = 0; i < maxBinaryDigits + 1; i++) {
c = a + b;
fibos[i] = a;
if (i > 1)
System.out.print(" " + a);
a = b;
b = c;
}
System.out.println("\nZecks:");
combination(0, maxBinaryDigits, 0);
}
private static void combination(int indx, int limit, int comb) {
if (indx == limit)
return;
int mask = 1 << indx;
// set comb[i] = 0
combination(indx + 1, limit, comb & ~mask);
if (indx + 1 == limit)
return;
// set comb[i] = 1 and comb[i+1] = 0
comb = comb | mask;
mask <<= 1;
comb = comb & ~mask;
printZack(comb, limit - 1);
combination(indx + 2, limit, comb);
}
private static void printZack(int n, int digits) {
int mask = 1 << digits, z = 0;
StringBuffer sbSum = new StringBuffer();
StringBuffer sbBin = new StringBuffer();
for (int i = digits - 1; i >= 0; i--) {
mask >>= 1;
if (n > 0)
sbBin.append((n & mask) >> i);
if ((n & mask) > 0) {
z += fibos[maxBinaryDigits - i];
sbSum.append(fibos[maxBinaryDigits - i] + "+");
n -= mask;
}
}
System.out.println(z + " = "
+ sbSum.toString().substring(0, sbSum.length() - 1) + " > "
+ sbBin + "1");
}
}
I made the code using only information I got from Wikipedia, and I have no restrictions on its usage or distribution. --150.162.0.162 19:53, 22 February 2007 (UTC)
- My opinion is that since you wrote this Java code yourself, it comes under the heading of "original research", which is not allowed in Wikipedia articles (see our policy document WP:NOR). Also, the Wikipedia computer science manual of style says "avoid writing sample code unless it contributes significantly to a fundamental understanding of the encyclopedic content". I don't think a code sample adds to the clarity of the Fibonacci coding article, so even if you found a published code sample that was not original research, I would still be against including it in the article. Gandalf61 10:26, 23 February 2007 (UTC)
