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

```            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  +}

```

```            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  +}

```