Check-in [7a1684ea05]
Overview
SHA1:7a1684ea05c2226b8ed1c63840808e174fe5ff7c
Date: 2014-12-30 14:03:58
User: spaskalev
Comment:Added encoding/fibonacci (cc: 100%)
Timelines: family | ancestors | descendants | both | trunk
Downloads: Tarball | ZIP archive
Other Links: files | file ages | folders | manifest
Tags And Properties
Context
2014-12-30
15:01
[9f5054e305] Minor opmitization to fibonacci's decoding. Changed plaindiff to show line numbers starting from 1. (user: spaskalev, tags: trunk)
14:03
[7a1684ea05] Added encoding/fibonacci (cc: 100%) (user: spaskalev, tags: trunk)
2014-12-28
18:06
[c07658474d] [mtf] Removed :to indices from copy(..) destinations. (user: spaskalev, tags: trunk)
Changes

Added src/0dev.org/encoding/fibonacci/fib.go version [bab2f5c2b7].

            1  +// Package provides a shifted, reversed fibonacci encoding of bytes
            2  +//
            3  +// http://en.wikipedia.org/wiki/Fibonacci_coding maps positive integers as
            4  +// 1 - 11, 2 - 011, 3 - 0011, 4 - 1011, 5 - 00011
            5  +//
            6  +// Incrementing input bytes by one to allow for zero gives
            7  +// 0 - 11, 1 - 011, 2 - 0011, 3 - 1011, 4 - 00011
            8  +//
            9  +// The codes are then reversed so that they are easily stored in uints
           10  +// 0 - 11, 1 - 110, 2 - 1100, 3 - 1101, 4 - 11000
           11  +package fibonacci
           12  +
           13  +type Numbers []uint64
           14  +
           15  +// Returns the n-th fibonacci number
           16  +// The result is stored after calculation
           17  +func (f Numbers) Nth(index int) uint64 {
           18  +	switch {
           19  +	case index <= 1:
           20  +		return 1
           21  +	case f[index] > 0:
           22  +		break
           23  +	default:
           24  +		f[index] = f.Nth(index-1) + f.Nth(index-2)
           25  +	}
           26  +	return f[index]
           27  +}
           28  +
           29  +// Returns a fibonacci code for an integer as specified in the package doc.
           30  +func (f Numbers) Code(value uint64) (result uint64) {
           31  +	// Increment to encode zero as one
           32  +	value++
           33  +
           34  +	// Find the nearest fibonacci number
           35  +	i := 0
           36  +	for f.Nth(i+1) <= value {
           37  +		i++
           38  +	}
           39  +
           40  +	// Leading bit that signals the start of a fibonacci-encoded integer
           41  +	result |= 1
           42  +
           43  +	// Find the Zeckendorf's representation by raising a bit for each
           44  +	// fibonacci number that is less or equal to the difference
           45  +	// between the value and the previous such number
           46  +	for ; i >= 1; i-- {
           47  +		result <<= 1
           48  +		if f.Nth(i) <= value {
           49  +			result |= 1
           50  +			value -= f.Nth(i)
           51  +		}
           52  +	}
           53  +	return
           54  +}
           55  +
           56  +// Returns an integer from a fibonacci code as specified in the package doc.
           57  +func (f Numbers) Decode(value uint64) (result uint64) {
           58  +	i := 1
           59  +	for (value & 3) != 3 {
           60  +		if (value & 1) == 1 {
           61  +			result += f.Nth(i)
           62  +		}
           63  +		value >>= 1
           64  +		i++
           65  +	}
           66  +	result += f.Nth(i) - 1
           67  +	return
           68  +}

Added src/0dev.org/encoding/fibonacci/fib_test.go version [5949178ed8].

            1  +package fibonacci
            2  +
            3  +import (
            4  +	"testing"
            5  +)
            6  +
            7  +func TestNumbers(t *testing.T) {
            8  +	n := make(Numbers, 32)
            9  +
           10  +	expected := []uint64{1, 1, 2, 3, 5, 8, 13, 21}
           11  +
           12  +	for i, v := range expected {
           13  +
           14  +		if f := n.Nth(i); f != v {
           15  +			t.Error("Unexpected value for", i, f, "expected", v)
           16  +		}
           17  +	}
           18  +}
           19  +
           20  +func TestCoding(t *testing.T) {
           21  +	n := make(Numbers, 32)
           22  +
           23  +	for i := uint64(0); i < 1024; i++ {
           24  +		enc := n.Code(i)
           25  +		dec := n.Decode(enc)
           26  +		if i != dec {
           27  +			t.Errorf("Unexpected value for %d - enc is %b, dec is %d\n", i, enc, dec)
           28  +		}
           29  +	}
           30  +}