fibonacci_encoding.sf

#!/usr/bin/ruby

# Daniel "Trizen" Șuteu
# Date: 24 April 2019
# https://github.com/trizen

# Encode positive integers in binary format, using the Fibonacci numbers.

# Example:
#   30 = "10100010" = 1×21 + 0×13 + 1×8 + 0×5 + 0×3 + 0×2 + 1×1 + 0×1

# See also:
#   https://projecteuler.net/problem=473
#   https://en.wikipedia.org/wiki/Fibonacci_coding
#   https://en.wikipedia.org/wiki/Zeckendorf%27s_theorem
#   https://en.wikipedia.org/wiki/Golden_ratio_base

func fibonacci_encoding(n) {

    return '0' if (n == 0)

    var phi = (sqrt(1.25) + 0.5)
    var idx = int((log(n) + log(5)/2) / log(phi))

    var (f1, f2) = (fib(idx), fib(idx-1))

    if (f1+f2 <= n) {
        (f1, f2) = (f1+f2, f1)
    }

    var enc = ''

    while (f1 > 0) {

        if (n >= f1) {
            n -= f1
            enc += '1'
        }
        else {
            enc += '0'
        }

        (f1, f2) = (f2, f1-f2)
    }

    return enc
}

func fibonacci_decoding(enc) {

    var len = enc.len
    var (f1, f2) = (fib(len), fib(len - 1))

    var dec = 0

    enc.each {|bit|
        dec += f1 if bit
        (f1, f2) = (f2, f1-f2)
    }

    return dec
}

say fibonacci_encoding(30)            #=> 10100010
say fibonacci_decoding('10100010')    #=> 30

say fibonacci_decoding(fibonacci_encoding(144))        #=> 144
say fibonacci_decoding(fibonacci_encoding(144 - 1))    #=> 143
say fibonacci_decoding(fibonacci_encoding(144 + 1))    #=> 145

# Verify the encoding/decoding algorithm
for n in (0..100) {
    if (fibonacci_decoding(fibonacci_encoding(n)) != n) {
        die "Error for #{n}";
    }
}

with (81923489126412312421758612841248123) {|n|
    assert_eq(fibonacci_decoding(fibonacci_encoding(n)), n)
}