{"id":53,"date":"2022-04-02T13:11:44","date_gmt":"2022-04-02T13:11:44","guid":{"rendered":"https:\/\/jonhough.com\/blog\/?p=53"},"modified":"2023-04-18T12:41:44","modified_gmt":"2023-04-18T12:41:44","slug":"fibonacci-coding","status":"publish","type":"post","link":"https:\/\/jonhough.com\/blog\/2022\/04\/02\/fibonacci-coding\/","title":{"rendered":"Fibonacci Coding"},"content":{"rendered":"\n

I have recently been looking into different encoding schemes, and just be chance, came across Fibonacci Encoding<\/em>. Although I think the usefulness of Fibonacci encoding is limited, it is – mathematically speaking – quite interesting.

Fibonacci encoding of positive integers is an interesting encoding method that uses the fact (theory) that any positive integer can be written uniquely<\/em> as the sum of fibonacci numbers where no two numbers in the summand are consecutive.
As an example, let’s consider the following integers 2,6,8,20.

Well, 2 is a fibonacci number itself, so we don’t need to do anything. We need to express the encoding as a binary string with zeros representing fibonacci numbers not in the summand, and 1 representing fibonacci number in the summand. So 2 can become

01<\/em>

Similarly,

6 = 1+5 = 1001;

8 = 8 = 00001;

20 = 2 + 5 + 13 = 010101.<\/em>


Notice, that no two 1’s are consecutive in any of the above encodings. This is important as we can use two consecutive 1’s to denote the end of one encoding and the beginning of another. That way, we can pack the integer encodings into a single byte stream, to more efficiently pack the bytes.


For instance, if we want to encode the number 7 and 11:
<\/p>\n\n\n\n

    \n
  1. First, note that 7 = 2 + 5 = 01011, and 11 = 3 + 8 = 001011;
    <\/li>\n\n\n\n
  2. So we can concatenat the encodings, using 5 +6 = 11 bits, to get 01011001011<\/em>;
    <\/li>\n\n\n\n
  3. As we want to put the encodings into bytes we pad with zeros up to the nearest multiple of 8, to get 0101100101100000.<\/li>\n<\/ol>\n\n\n\n

    <\/p>\n\n\n\n

    Here, we have encoded two integers using 2 bytes.
    Let’s have a look at one implementation of encoding and decoding, in the J language.
    First, we need to generate Fibonacci<\/em> numbers. This is an easy verb to write:<\/p>\n\n\n\n

    <\/p>\n\n\n\n

    genfibs=: 3 : 0\nr=. 1 2\ni1=. 1\ni2=. 2\nc=. 2\nwhile. y > c=. c+1 do.\n  t=. i1 + i2\n  i1=. i2\n  i2=. t\n  r=. r, x: t\nend.\n)\n\n\nFibs=: genfibs 1400<\/code><\/pre>\n\n\n\n
    With Fibs, we have a list of the first 1400 Fibonacci numbers, where we define the first two as “1, 2”. ie. we ignore the “1,1” first 1.<\/p>\n\n\n\n
    Let’s encode:<\/p>\n\n\n\n
    <\/p>\n\n\n\n
    encode=: 3 : 0\nd=. > (>@:,&:>)\/ (<@encode1)\"0 y\nr=. d,'0' #~ (#d) -~ 8 * >. 8 %~ # d\npack r\n)\n\nencode1=: 3 : 0\nn=. x: y\nr=. ''\nk=: ''\nfl=. x: Fibs{~ I. Fibs <: y\ni=. <:#fl\nwhile. n do.\n\u00a0\u00a0r=. r,'1'\n\u00a0\u00a0n=. n - i{fl\n\u00a0\u00a0k=: k,i{fl\n\u00a0\u00a0i=. i-1\n\u00a0\u00a0while. (i >: 0) *. (n<i{fl) do.\n\u00a0\u00a0 \u00a0r=. r,'0'\n\u00a0\u00a0 \u00a0i=. i-1\n\u00a0\u00a0end.\nend.\n(|.r),'1'\n)\n\npack=: 3 : 0\na.{~ #. _8 ] \\\".\"0 y\n)<\/code><\/pre>\n\n\n\n



    Here we have 3 verbs:

    <\/strong>1. encode
    2. encode1
    3. pack

    encode1<\/em> will encode a single positive integer into the Fibonacci representation. Example:
    <\/p>\n\n\n\n
    encode 3452\n101000100001010011<\/code><\/pre>\n\n\n\n
    Here, the result ing representation is a string literal, for the sake of readability. The encoding is “101000100001010011”. Note the final “11”, denoting the delimitation of this encoding.


    The verb “encode” and “pack” are used to encode multiple integers to a single output.<\/p>\n\n\n\n
    #: a.i. encode 10 11 12 13 14\nL\ufffd\ufffd\ufffd<\/code><\/pre>\n\n\n\n
    The result is not readable just 4 bytes. We can read the bits:<\/p>\n\n\n\n
    #: a.i. encode 10 11 12 13 14\n0 1 0 0 1 1 0 0\n1 0 1 1 1 0 1 0\n1 1 0 0 0 0 0 1\n1 1 0 0 0 0 1 1\n<\/code><\/pre>\n\n\n\n
    As you can see, this encoding of 4 integers results in a 4 byte encoding. Not bad, compression.


    What about decoding? Once encoded, we would like to get the original integer(s) back again. Here is the “decode” verb which operates an a single byte array.<\/p>\n\n\n\n
    decode=: 3 : 0\ni=. , #: a.i. y\nn=. ''\nwhile. 1 e. 1 1 E. i do.\n  idx=. {. I. 1 1 E. i\n  n=. n, +\/ Fibs {~ I. i {~ i. >: idx\n  i=. (2+idx) }. i\nend.\nn\n)\n<\/code><\/pre>\n\n\n\n
    An example:<\/p>\n\n\n\n
    decode encode 10 11 12 13 14
    10 11 12 13 14
    <\/code><\/pre>\n\n\n\n
    The encoding and decoding works perfectly, as long as the input are positive integers.

    We now have our encoded integer array, but would want to represent as a string, so we can encode the bytes further using (for example) base-64 encoding. Note that base-64 encoding will increase the byte count by 1.33.<\/p>\n\n\n\n
    load 'convert\/misc\/base64'\n]str=: tobase64 encode 10 100 300\nTKHUTA==\n\n]nums=: decode frombase64 str\n10 100 300\n<\/code><\/pre>\n\n\n\n

    That worked very well. Note that we can this for very large integers too.<\/p>\n\n\n\n
    require 'convert\/misc\/base64'\nenc =: encode 22338938348348348357675630030349235752291183838232x\n# enc\n30  NB. encoded a 164-bit (~ 20 bytes) integer with 30 bytes\nstr=: tobase64 enc\ndecode frombase64 str \n22338938348348348357675630030349235752291183838232 NB. get the original input.\n<\/code><\/pre>\n\n\n\n
    This was an interesting exercise and might be worth rewriting in other languages.
    The encoder and decoder were very easy to write (especially in J), so this probably wouldn’t take too long in another language. I will put it on my to-do list.<\/p>\n\n\n\n
    The entirety of the source code: <\/p>\n\n\n\n
    <\/p>\n\n\n\n
    genfibs=: 3 : 0\nr=. 1 2\ni1=. 1\ni2=. 2\nc=. 2\nwhile. y > c=. c+1 do.\n  t=. i1 + i2\n  i1=. i2\n  i2=. t\n  r=. r, x: t\nend.\n)\n\n\nFibs=: genfibs 1400\n\nencode=: 3 : 0\nd=. > (>@:,&:>)\/ (<@encode1)\"0 y\nr=. d,'0' #~ (#d) -~ 8 * >. 8 %~ # d\npack r\n)\n\nencode1=: 3 : 0\nn=. x: y\nr=. ''\nk=: ''\nfl=. x: Fibs{~ I. Fibs <: y\ni=. <:#fl\nwhile. n do.\n  r=. r,'1'\n  n=. n - i{fl\n  k=: k,i{fl\n  i=. i-1\n  while. (i >: 0) *. (n<i{fl) do.\n    r=. r,'0'\n    i=. i-1\n  end.\nend.\n(|.r),'1'\n)\n\n\n\npack=: 3 : 0\na.{~ #. _8 ] \\\".\"0 y\n)\n\ndecode=: 3 : 0\ni=. , #: a.i. y\nn=. ''\nwhile. 1 e. 1 1 E. i do.\n  idx=. {. I. 1 1 E. i\n  n=. n, +\/ Fibs {~ I. i {~ i. >: idx\n  i=. (2+idx) }. i\nend.\nn\n)<\/code><\/pre>\n\n\n\n
    Useful links:
    Fibonacci coding<\/a>
    Zeckendorf’s theorem<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
    I have recently been looking into different encoding schemes, and just be chance, came across Fibonacci Encoding. Although I think the usefulness of Fibonacci encoding is limited, it is – mathematically speaking – quite interesting. Fibonacci encoding of positive inteRead More <\/span><\/i><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"nf_dc_page":"","om_disable_all_campaigns":false,"_import_markdown_pro_load_document_selector":0,"_import_markdown_pro_submit_text_textarea":"","footnotes":""},"categories":[21,3],"tags":[23,22,9],"class_list":["post-53","post","type-post","status-publish","format-standard","hentry","category-j","category-tech","tag-coding","tag-j","tag-programming"],"yoast_head":"\nFibonacci Coding - Technology Blog<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/jonhough.com\/blog\/2022\/04\/02\/fibonacci-coding\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Fibonacci Coding - Technology Blog\" \/>\n<meta property=\"og:description\" content=\"I have recently been looking into different encoding schemes, and just be chance, came across Fibonacci Encoding. Although I think the usefulness of Fibonacci encoding is limited, it is – mathematically speaking – quite interesting. Fibonacci encoding of positive inteRead More\" \/>\n<meta property=\"og:url\" content=\"https:\/\/jonhough.com\/blog\/2022\/04\/02\/fibonacci-coding\/\" \/>\n<meta property=\"og:site_name\" content=\"Technology Blog\" \/>\n<meta property=\"article:published_time\" content=\"2022-04-02T13:11:44+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2023-04-18T12:41:44+00:00\" \/>\n<meta name=\"author\" content=\"Jonathan Hough\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Jonathan Hough\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"5 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/jonhough.com\\\/blog\\\/2022\\\/04\\\/02\\\/fibonacci-coding\\\/#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/jonhough.com\\\/blog\\\/2022\\\/04\\\/02\\\/fibonacci-coding\\\/\"},\"author\":{\"name\":\"Jonathan Hough\",\"@id\":\"https:\\\/\\\/jonhough.com\\\/blog\\\/#\\\/schema\\\/person\\\/403f6a6e3cafff3ecd77fff3a5febcf2\"},\"headline\":\"Fibonacci Coding\",\"datePublished\":\"2022-04-02T13:11:44+00:00\",\"dateModified\":\"2023-04-18T12:41:44+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/jonhough.com\\\/blog\\\/2022\\\/04\\\/02\\\/fibonacci-coding\\\/\"},\"wordCount\":531,\"commentCount\":0,\"keywords\":[\"coding\",\"j\",\"programming\"],\"articleSection\":[\"J\",\"technology\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\\\/\\\/jonhough.com\\\/blog\\\/2022\\\/04\\\/02\\\/fibonacci-coding\\\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/jonhough.com\\\/blog\\\/2022\\\/04\\\/02\\\/fibonacci-coding\\\/\",\"url\":\"https:\\\/\\\/jonhough.com\\\/blog\\\/2022\\\/04\\\/02\\\/fibonacci-coding\\\/\",\"name\":\"Fibonacci Coding - Technology Blog\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/jonhough.com\\\/blog\\\/#website\"},\"datePublished\":\"2022-04-02T13:11:44+00:00\",\"dateModified\":\"2023-04-18T12:41:44+00:00\",\"author\":{\"@id\":\"https:\\\/\\\/jonhough.com\\\/blog\\\/#\\\/schema\\\/person\\\/403f6a6e3cafff3ecd77fff3a5febcf2\"},\"breadcrumb\":{\"@id\":\"https:\\\/\\\/jonhough.com\\\/blog\\\/2022\\\/04\\\/02\\\/fibonacci-coding\\\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/jonhough.com\\\/blog\\\/2022\\\/04\\\/02\\\/fibonacci-coding\\\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/jonhough.com\\\/blog\\\/2022\\\/04\\\/02\\\/fibonacci-coding\\\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\\\/\\\/jonhough.com\\\/blog\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Fibonacci Coding\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/jonhough.com\\\/blog\\\/#website\",\"url\":\"https:\\\/\\\/jonhough.com\\\/blog\\\/\",\"name\":\"Technology Blog\",\"description\":\"Technology and other things\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/jonhough.com\\\/blog\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Person\",\"@id\":\"https:\\\/\\\/jonhough.com\\\/blog\\\/#\\\/schema\\\/person\\\/403f6a6e3cafff3ecd77fff3a5febcf2\",\"name\":\"Jonathan Hough\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/4cf2d3b1fd3887f472fd54e08d0ede13a4cceb1d74fa63290542e7b090b55d15?s=96&d=mm&r=g\",\"url\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/4cf2d3b1fd3887f472fd54e08d0ede13a4cceb1d74fa63290542e7b090b55d15?s=96&d=mm&r=g\",\"contentUrl\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/4cf2d3b1fd3887f472fd54e08d0ede13a4cceb1d74fa63290542e7b090b55d15?s=96&d=mm&r=g\",\"caption\":\"Jonathan Hough\"},\"url\":\"https:\\\/\\\/jonhough.com\\\/blog\\\/author\\\/jon\\\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Fibonacci Coding - Technology Blog","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/jonhough.com\/blog\/2022\/04\/02\/fibonacci-coding\/","og_locale":"en_US","og_type":"article","og_title":"Fibonacci Coding - Technology Blog","og_description":"I have recently been looking into different encoding schemes, and just be chance, came across Fibonacci Encoding. Although I think the usefulness of Fibonacci encoding is limited, it is – mathematically speaking – quite interesting. Fibonacci encoding of positive inteRead More","og_url":"https:\/\/jonhough.com\/blog\/2022\/04\/02\/fibonacci-coding\/","og_site_name":"Technology Blog","article_published_time":"2022-04-02T13:11:44+00:00","article_modified_time":"2023-04-18T12:41:44+00:00","author":"Jonathan Hough","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Jonathan Hough","Est. reading time":"5 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/jonhough.com\/blog\/2022\/04\/02\/fibonacci-coding\/#article","isPartOf":{"@id":"https:\/\/jonhough.com\/blog\/2022\/04\/02\/fibonacci-coding\/"},"author":{"name":"Jonathan Hough","@id":"https:\/\/jonhough.com\/blog\/#\/schema\/person\/403f6a6e3cafff3ecd77fff3a5febcf2"},"headline":"Fibonacci Coding","datePublished":"2022-04-02T13:11:44+00:00","dateModified":"2023-04-18T12:41:44+00:00","mainEntityOfPage":{"@id":"https:\/\/jonhough.com\/blog\/2022\/04\/02\/fibonacci-coding\/"},"wordCount":531,"commentCount":0,"keywords":["coding","j","programming"],"articleSection":["J","technology"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/jonhough.com\/blog\/2022\/04\/02\/fibonacci-coding\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/jonhough.com\/blog\/2022\/04\/02\/fibonacci-coding\/","url":"https:\/\/jonhough.com\/blog\/2022\/04\/02\/fibonacci-coding\/","name":"Fibonacci Coding - Technology Blog","isPartOf":{"@id":"https:\/\/jonhough.com\/blog\/#website"},"datePublished":"2022-04-02T13:11:44+00:00","dateModified":"2023-04-18T12:41:44+00:00","author":{"@id":"https:\/\/jonhough.com\/blog\/#\/schema\/person\/403f6a6e3cafff3ecd77fff3a5febcf2"},"breadcrumb":{"@id":"https:\/\/jonhough.com\/blog\/2022\/04\/02\/fibonacci-coding\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/jonhough.com\/blog\/2022\/04\/02\/fibonacci-coding\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/jonhough.com\/blog\/2022\/04\/02\/fibonacci-coding\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/jonhough.com\/blog\/"},{"@type":"ListItem","position":2,"name":"Fibonacci Coding"}]},{"@type":"WebSite","@id":"https:\/\/jonhough.com\/blog\/#website","url":"https:\/\/jonhough.com\/blog\/","name":"Technology Blog","description":"Technology and other things","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/jonhough.com\/blog\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Person","@id":"https:\/\/jonhough.com\/blog\/#\/schema\/person\/403f6a6e3cafff3ecd77fff3a5febcf2","name":"Jonathan Hough","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/secure.gravatar.com\/avatar\/4cf2d3b1fd3887f472fd54e08d0ede13a4cceb1d74fa63290542e7b090b55d15?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/4cf2d3b1fd3887f472fd54e08d0ede13a4cceb1d74fa63290542e7b090b55d15?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/4cf2d3b1fd3887f472fd54e08d0ede13a4cceb1d74fa63290542e7b090b55d15?s=96&d=mm&r=g","caption":"Jonathan Hough"},"url":"https:\/\/jonhough.com\/blog\/author\/jon\/"}]}},"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/jonhough.com\/blog\/wp-json\/wp\/v2\/posts\/53","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/jonhough.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/jonhough.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/jonhough.com\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/jonhough.com\/blog\/wp-json\/wp\/v2\/comments?post=53"}],"version-history":[{"count":4,"href":"https:\/\/jonhough.com\/blog\/wp-json\/wp\/v2\/posts\/53\/revisions"}],"predecessor-version":[{"id":61,"href":"https:\/\/jonhough.com\/blog\/wp-json\/wp\/v2\/posts\/53\/revisions\/61"}],"wp:attachment":[{"href":"https:\/\/jonhough.com\/blog\/wp-json\/wp\/v2\/media?parent=53"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/jonhough.com\/blog\/wp-json\/wp\/v2\/categories?post=53"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/jonhough.com\/blog\/wp-json\/wp\/v2\/tags?post=53"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}