Talk:Fibonacci coding

The values of digits starting from left in fibonacci coding are 1,2,3,5,8,etc. Rightmost digit (which is always 1) does not have any value. There does not exist any such simple rule for tribonacci coding (I've tried to come up with one). There is also no citation. I don't think fibonacci coding can be easily generalised using n-bonacci numbers. I'm not able to add new secton in mobile version.

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)

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)

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)

Merge discussion

See Talk:Zeckendorf's theorem. --N Shar 18:18, 20 February 2007 (UTC)

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)

Original research is fine. In this case, it is easily verifiable - anyone having a java compiler can do it. However, I think it is too complicated, and agree that it does not seem to contribute to the clarity of the article. Instead of this I would add a much simpler, smaller code (if exists) in the article. --Hirak 99 (talk) 10:36, 18 March 2009 (UTC)

The code is not illuminating in the slightest. If I were a user with a login I would remove it. —Preceding unsigned comment added by 155.212.15.131 (talk) 13:29, 17 March 2010 (UTC)

Formula

I have added on the page the formula found here: http://wiki.tcl.tk/12324 The page also contains sample code to generate codes

Inventors?

Would it be benefitual to list the inventors of the Fibonacci Code and the patents that they hold? Kensavage 19:00, 28 September 2007 (UTC)

Confusing

well, perhaps a bit slow, but I do not understand the last part of the phrase "....All tokens end with "11" and have no "11" before the end...." can it be made more clear? is it just saying a coded stream cannot end with a number code ie xxx11 but some other padding or ? --Billymac00 (talk) 03:35, 27 January 2009 (UTC)

It means that the only place you see a "11" in a Fibonacci coding is at the end of a number token. So the string "101111011", for example, can be unambiguously parsed as "1011/11/011" i.e. 4 1 2. Gandalf61 (talk) 10:20, 27 January 2009 (UTC)

By the definition of Fibonacci numbers the sequence

...0110...=...0*F(n-1)+1*F(n)+1*F(n+1)+0*F(n+2)...=...0*F(n-1)+0*F(n)+0*F(n+1)+1*F(n+2)...

That is to say it can be rewritten as ...0001...Laelele (talk) 11:09, 8 November 2012 (UTC)

Heading

I added "It is one example of representations of integers based on Fibonacci numbers." in the heading since there is no common agreement that "this is the way to do it" when we use Fibonacci numbers to represent integers.Laelele (talk) 09:17, 13 November 2012 (UTC)

Misleading definition of Fibonacci sequence?

This seems clunky as it seems to introduce an "alternative" Fibonacci sequence:

where F(i) is the ith Fibonacci number, and so F(i+2) is the ith distinct Fibonacci number starting with $1,2,3,5,8,13,\ldots$

In my opinion, it's much better to point to the operative definition adopted (0-based indexes, sequence starting with 0):

where F(k) is the k-th number in the Fibonacci sequence $0,1,1,2,3,5,8,13,\ldots$, with index k≥0

If you prefer the 1-based indexes and the sequence starting with 1, of course:

where F(k) is the k-th number in the Fibonacci sequence $1,1,2,3,5,8,13,\ldots$, with index k≥1

213.203.132.119 (talk) 07:52, 20 December 2017 (UTC)