5 ms·

Fibonacci Coding

61 points by cinquemb 5y ago

lucb1e 5y ago
I found the section above the linked one (Comparison with other universal codes) most interesting: > Fibonacci coding has a useful property that sometimes makes it attractive in comparison to other universal codes: it is an example of a self-synchronizing code, making it easier to recover data from a damaged stream.
- rbanffy 5y ago
  Cool. It’s like it has its own embedded clock pulses. Very nice.
- Sharlin 5y ago
  A more familiar example of a self-synchronizing (but non-universal) code is UTF-8, which guarantees that if you start decoding a bytestream in the middle of a codepoint, it's trivial to find the next codepoint boundary because initial bytes always start with either 0 or 11, and continuation bytes always start with 10.
  - gautamcgoel 5y ago
    Just to make sure I understand, this assumes that you start decoding at the beginning of a byte, not halfway through a byte, correct?
    - not2b 5y ago
      Yes, the structure could still help resync if you have a bitstream and not a bytestream (you could identify the MSBs of bytes from their very different statistical behavior), but it isn't as trivial as skipping continuation bytes, those with '10' in the most significant position. You'd need to track all 8 shift positions until you find the one that looks like UTF-8.
  - lucb1e 5y ago
    Holy crap I did not know that and always thought it must be such a pain to decode variable-length text! How did I go so long without knowing this, that's such a neat feature.
tyingq 5y ago
A card trick based on this, and I also find the high level explanation more clear than Wikipedia's: http://teachersofindia.org/en/article/fibonacci-coding-and-card-trick http://teachersofindia.org/en/article/fibonacci-coding-and-c...
teeray 5y ago
Is there a similar scheme using primes?
- swregert 5y ago
  Similar but not totally analogous https://oeis.org/wiki/Primorial_numeral_system https://oeis.org/wiki/Primorial_numeral_system
- pacaro 5y ago
  This made me think of Gödel Numbering¹, which was used in the plot of "The Gold at the Starbow's End" by Frederick Pohl² 1) https://en.wikipedia.org/wiki/G%C3%B6del_numbering https://en.wikipedia.org/wiki/G%C3%B6del_numbering 2) https://en.wikipedia.org/wiki/The_Gold_at_the_Starbow's_End https://en.wikipedia.org/wiki/The_Gold_at_the_Starbow's_End
- evanb 5y ago
  If the Goldbach conjecture is true, such a scheme would be all zeros except in up two places, as long as the integer you want to encode is even. Even if the conjecture is true, the code must be ternary: to encode 6 you need to indicate 3 twice, as 6 = 3 + 3. However, very many even integers are the total of more than one pair of primes. So, the encoding of a number using this scheme is not unique. In contrast, because of the property F_n = F_{n-1} + F_{n-2} you never need more any Fibonacci number more than once in the code, so the code is binary (and the encoding unique).
gyrgtyn 5y ago
I think past me would have thought this was cool. Now I'm just annoyed about having to think about this.
- scubbo 5y ago
  Good news! You don't have to think about this.
- leetrout 5y ago
  I know how you feel. Burnout is a real thing. I hope you heal and find the energy to enjoy things like this again.
k__ 5y ago
I know mathematicians don't like this question, but: Why?
- swregert 5y ago
  It's a binary comma code (https://en.wikipedia.org/wiki/Comma_code https://en.wikipedia.org/wiki/Comma_code) for integers. If it didn't exist someone would invent it. The implication of Fibonacci numbers isn't arbitrary, it's because Zeckendorf representation is the neatest way to do the job.
- cinquemb 5y ago
  I'm looking at different ways to compress a list of integers, came across [0] and this seems to work best [1] for small ints that I'm working with. [0] https://github.com/invertedtomato/integer-compression https://github.com/invertedtomato/integer-compression [1] https://raw.githubusercontent.com/invertedtomato/integer-compression/master/images/comparison-1.png https://raw.githubusercontent.com/invertedtomato/integer-com...
  - user-the-name 5y ago
    You can improve on this by quite a bit by not writing literal bits to the file, but instead feeding them through an arithmetic or range coder, with some reasonable statistical model. The statistical model can be very simple, even just an exponential moving average per digit will help.
    - cinquemb 5y ago
      Yeah, it seems like going with some of solutions listed here[0][1] work pretty well after passing the binary through (better when not passing through fib coding, but mapping most of the ints to characters and compressing them). Still trying to explore though. [0] https://en.wikipedia.org/wiki/Dynamic_Markov_compression https://en.wikipedia.org/wiki/Dynamic_Markov_compression [1] http://mattmahoney.net/dc/text.html#1263 http://mattmahoney.net/dc/text.html#1263
imvetri 5y ago
Yes,! this was in my mind and I'm trying to apply the same technique. Here is a backstory. I'm a UI developer and I code to build UI, question that came to me, why not build an UI that builds the UI? It's an IDE or a design tool. I tried it, built it, https://github.com/imvetri/ui-editor https://github.com/imvetri/ui-editor. but I wasn't really not convinced. why? A problem is solved only when solved recursively. I did solve it recursively - I built an UI to build an UI, however I wanted to take to next step. I'm trying to reduce code and include more interactions. I'm really not sure how to build a true UI that can build UI, but Fibonacci series or other growing functions that is solved recursively is my inspiration. How to apply that to building User interfaces ? Everything is a rectangle. A rectangle can have children rectangles. A rectangle can have sibling rectangle. A parent rectangle can create children rectangle. A parent can delete child rectangle. A rectangle can edit itself. hahaha A parent rectangle can edit itself to create more children. So I need one rectangle hardcoded that can create more children, and can edit itself And I have solved that too - https://vimeo.com/464104903 https://vimeo.com/464104903. TDLR: I work on a side project to bring all frameworks under one hood (by targeted code generation to different framework with single source of truth. It is tested well for reactJS). I still want to work on it on everyday basis, but couldn't find the time I had 3 years back. However I'll be glad to set some time to guide someone if they are interested to contribute.

61 points by cinquemb 5y ago

I found the section above the linked one (Comparison with other universal codes) most interesting: > Fibonacci coding has a useful property that sometimes makes it attractive in comparison to other universal codes: it is an example of a self-synchronizing code, making it easier to recover data from a damaged stream.

rbanffy 5y ago
Cool. It’s like it has its own embedded clock pulses. Very nice.
Sharlin 5y ago
A more familiar example of a self-synchronizing (but non-universal) code is UTF-8, which guarantees that if you start decoding a bytestream in the middle of a codepoint, it's trivial to find the next codepoint boundary because initial bytes always start with either 0 or 11, and continuation bytes always start with 10.
- gautamcgoel 5y ago
  Just to make sure I understand, this assumes that you start decoding at the beginning of a byte, not halfway through a byte, correct?
  - not2b 5y ago
    Yes, the structure could still help resync if you have a bitstream and not a bytestream (you could identify the MSBs of bytes from their very different statistical behavior), but it isn't as trivial as skipping continuation bytes, those with '10' in the most significant position. You'd need to track all 8 shift positions until you find the one that looks like UTF-8.
- lucb1e 5y ago
  Holy crap I did not know that and always thought it must be such a pain to decode variable-length text! How did I go so long without knowing this, that's such a neat feature.

tyingq 5y ago

A card trick based on this, and I also find the high level explanation more clear than Wikipedia's: http://teachersofindia.org/en/article/fibonacci-coding-and-card-trick http://teachersofindia.org/en/article/fibonacci-coding-and-c...

teeray 5y ago

Is there a similar scheme using primes?

swregert 5y ago
Similar but not totally analogous https://oeis.org/wiki/Primorial_numeral_system https://oeis.org/wiki/Primorial_numeral_system
pacaro 5y ago
This made me think of Gödel Numbering¹, which was used in the plot of "The Gold at the Starbow's End" by Frederick Pohl² 1) https://en.wikipedia.org/wiki/G%C3%B6del_numbering https://en.wikipedia.org/wiki/G%C3%B6del_numbering 2) https://en.wikipedia.org/wiki/The_Gold_at_the_Starbow's_End https://en.wikipedia.org/wiki/The_Gold_at_the_Starbow's_End
evanb 5y ago
If the Goldbach conjecture is true, such a scheme would be all zeros except in up two places, as long as the integer you want to encode is even. Even if the conjecture is true, the code must be ternary: to encode 6 you need to indicate 3 twice, as 6 = 3 + 3. However, very many even integers are the total of more than one pair of primes. So, the encoding of a number using this scheme is not unique. In contrast, because of the property F_n = F_{n-1} + F_{n-2} you never need more any Fibonacci number more than once in the code, so the code is binary (and the encoding unique).

gyrgtyn 5y ago

I think past me would have thought this was cool. Now I'm just annoyed about having to think about this.

scubbo 5y ago
Good news! You don't have to think about this.
leetrout 5y ago
I know how you feel. Burnout is a real thing. I hope you heal and find the energy to enjoy things like this again.

k__ 5y ago

I know mathematicians don't like this question, but: Why?

swregert 5y ago
It's a binary comma code (https://en.wikipedia.org/wiki/Comma_code https://en.wikipedia.org/wiki/Comma_code) for integers. If it didn't exist someone would invent it. The implication of Fibonacci numbers isn't arbitrary, it's because Zeckendorf representation is the neatest way to do the job.
cinquemb 5y ago
I'm looking at different ways to compress a list of integers, came across [0] and this seems to work best [1] for small ints that I'm working with. [0] https://github.com/invertedtomato/integer-compression https://github.com/invertedtomato/integer-compression [1] https://raw.githubusercontent.com/invertedtomato/integer-compression/master/images/comparison-1.png https://raw.githubusercontent.com/invertedtomato/integer-com...
- user-the-name 5y ago
  You can improve on this by quite a bit by not writing literal bits to the file, but instead feeding them through an arithmetic or range coder, with some reasonable statistical model. The statistical model can be very simple, even just an exponential moving average per digit will help.
  - cinquemb 5y ago
    Yeah, it seems like going with some of solutions listed here[0][1] work pretty well after passing the binary through (better when not passing through fib coding, but mapping most of the ints to characters and compressing them). Still trying to explore though. [0] https://en.wikipedia.org/wiki/Dynamic_Markov_compression https://en.wikipedia.org/wiki/Dynamic_Markov_compression [1] http://mattmahoney.net/dc/text.html#1263 http://mattmahoney.net/dc/text.html#1263

imvetri 5y ago

Yes,! this was in my mind and I'm trying to apply the same technique. Here is a backstory. I'm a UI developer and I code to build UI, question that came to me, why not build an UI that builds the UI? It's an IDE or a design tool. I tried it, built it, https://github.com/imvetri/ui-editor https://github.com/imvetri/ui-editor. but I wasn't really not convinced. why? A problem is solved only when solved recursively. I did solve it recursively - I built an UI to build an UI, however I wanted to take to next step. I'm trying to reduce code and include more interactions. I'm really not sure how to build a true UI that can build UI, but Fibonacci series or other growing functions that is solved recursively is my inspiration. How to apply that to building User interfaces ? Everything is a rectangle. A rectangle can have children rectangles. A rectangle can have sibling rectangle. A parent rectangle can create children rectangle. A parent can delete child rectangle. A rectangle can edit itself. hahaha A parent rectangle can edit itself to create more children. So I need one rectangle hardcoded that can create more children, and can edit itself And I have solved that too - https://vimeo.com/464104903 https://vimeo.com/464104903. TDLR: I work on a side project to bring all frameworks under one hood (by targeted code generation to different framework with single source of truth. It is tested well for reactJS). I still want to work on it on everyday basis, but couldn't find the time I had 3 years back. However I'll be glad to set some time to guide someone if they are interested to contribute.