Talk:Fibonacci coding

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Big-endian and little-endian?[edit]

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[edit]

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[edit]

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[edit]

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

Sample Code[edit]

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[edit]

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?[edit]

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[edit]

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[edit]

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)