The Shed
Check-in [ffb139e305]
Login
HomeTimelineFilesBranchesTagsTicketsWiki
Overview
Comment:Dropped the Nth method and return a populated slice by fibonacci.New(size). Changed all access to direct indexing. CC at 100%
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: ffb139e305ddf74bb722ba46665ea7520d9c8daa
User & Date: spaskalev on 2014-12-30 22:59:23
Other Links: manifest | tags
Context
2015-01-01
04:58
Added fibonacci.Writer(io.Writer) io.Writer that encodes bytes. check-in: 93fcb281a1 user: spaskalev tags: trunk
2014-12-30
22:59
Dropped the Nth method and return a populated slice by fibonacci.New(size). Changed all access to direct indexing. CC at 100% check-in: ffb139e305 user: spaskalev tags: trunk
15:01
Minor opmitization to fibonacci's decoding. Changed plaindiff to show line numbers starting from 1. check-in: 9f5054e305 user: spaskalev tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Modified src/0dev.org/encoding/fibonacci/fib.go from [36b31aa589] to [5db8094e9b]. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

// Package provides a shifted, reversed fibonacci encoding of bytes
//
// http://en.wikipedia.org/wiki/Fibonacci_coding maps positive integers as
// 1 - 11, 2 - 011, 3 - 0011, 4 - 1011, 5 - 00011
//
// Incrementing input bytes by one to allow for zero gives
// 0 - 11, 1 - 011, 2 - 0011, 3 - 1011, 4 - 00011
//
// The codes are then reversed so that they are easily stored in uints
// 0 - 11, 1 - 110, 2 - 1100, 3 - 1101, 4 - 11000
package fibonacci

type Numbers []uint64

// Returns the n-th fibonacci number
// The result is stored after calculation
func (f Numbers) Nth(index int) uint64 {
	switch {
	case index <= 1:
		return 1
	case f[index] > 0:
		break
	default:
		f[index] = f.Nth(index-1) + f.Nth(index-2)
	}
	return f[index]
}

// Returns a fibonacci code for an integer as specified in the package doc.
func (f Numbers) Code(value uint64) (result uint64) {
	// Increment to encode zero as one
	value++

	// Find the nearest fibonacci number
	i := 0
	for f.Nth(i+1) <= value {
		i++
	}

	// Leading bit that signals the start of a fibonacci-encoded integer
	result |= 1

	// Find the Zeckendorf's representation by raising a bit for each
	// fibonacci number that is less or equal to the difference
	// between the value and the previous such number
	for ; i >= 1; i-- {
		result <<= 1
		if f.Nth(i) <= value {
			result |= 1
			value -= f.Nth(i)
		}
	}
	return
}

// Returns an integer from a fibonacci code as specified in the package doc.
func (f Numbers) Decode(value uint64) (result uint64) {
	i := 1

	for (value & 3) != 3 {
		// Add the fibonacci number for the current bit if it is raised
		if (value & 1) == 1 {
			result += f.Nth(i)

			// We know that the next bit cannot be raised by Zeckendorf's theorem
			value >>= 2
			i += 2
			continue
		}

		value >>= 1
		i++
	}
	result += f.Nth(i) - 1
	return
}

|




|








|
|
|
|
|
<
<
<
<
|

|


|






|











|

|





|


>



|










|



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19




20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

// Package provides a shifted, reversed fibonacci encoding of unsigned integers.
//
// http://en.wikipedia.org/wiki/Fibonacci_coding maps positive integers as
// 1 - 11, 2 - 011, 3 - 0011, 4 - 1011, 5 - 00011
//
// Incrementing input by one to allow for zero gives
// 0 - 11, 1 - 011, 2 - 0011, 3 - 1011, 4 - 00011
//
// The codes are then reversed so that they are easily stored in uints
// 0 - 11, 1 - 110, 2 - 1100, 3 - 1101, 4 - 11000
package fibonacci

type Numbers []uint64

// Returns a slice with fibonacci numbers up to the given length
func New(size int) Numbers {
	var fibs Numbers = make(Numbers, size)
	copy(fibs, []uint64{1, 1})
	for i := 2; i < size; i++ {




		fibs[i] = fibs[i-1] + fibs[i-2]
	}
	return fibs
}

// Returns a fibonacci code for an integer as specified in the package's doc.
func (f Numbers) Code(value uint64) (result uint64) {
	// Increment to encode zero as one
	value++

	// Find the nearest fibonacci number
	i := 0
	for f[i+1] <= value {
		i++
	}

	// Leading bit that signals the start of a fibonacci-encoded integer
	result |= 1

	// Find the Zeckendorf's representation by raising a bit for each
	// fibonacci number that is less or equal to the difference
	// between the value and the previous such number
	for ; i >= 1; i-- {
		result <<= 1
		if f[i] <= value {
			result |= 1
			value -= f[i]
		}
	}
	return
}

// Returns an integer from a fibonacci code as specified in the package's doc.
func (f Numbers) Decode(value uint64) (result uint64) {
	i := 1
	// Loop until the lowest two bits are both raised
	for (value & 3) != 3 {
		// Add the fibonacci number for the current bit if it is raised
		if (value & 1) == 1 {
			result += f[i]

			// We know that the next bit cannot be raised by Zeckendorf's theorem
			value >>= 2
			i += 2
			continue
		}

		value >>= 1
		i++
	}
	result += f[i] - 1
	return
}

Modified src/0dev.org/encoding/fibonacci/fib_test.go from [5949178ed8] to [ecd601a44e]. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

package fibonacci

import (
	"testing"
)

func TestNumbers(t *testing.T) {
	n := make(Numbers, 32)

	expected := []uint64{1, 1, 2, 3, 5, 8, 13, 21}

	for i, v := range expected {

		if f := n.Nth(i); f != v {
			t.Error("Unexpected value for", i, f, "expected", v)
		}
	}
}

func TestCoding(t *testing.T) {
	n := make(Numbers, 32)

	for i := uint64(0); i < 1024; i++ {
		enc := n.Code(i)
		dec := n.Decode(enc)
		if i != dec {
			t.Errorf("Unexpected value for %d - enc is %b, dec is %d\n", i, enc, dec)
		}








|





|






|








1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

package fibonacci

import (
	"testing"
)

func TestNumbers(t *testing.T) {
	n := New(32)

	expected := []uint64{1, 1, 2, 3, 5, 8, 13, 21}

	for i, v := range expected {

		if f := n[i]; f != v {
			t.Error("Unexpected value for", i, f, "expected", v)
		}
	}
}

func TestCoding(t *testing.T) {
	n := New(32)

	for i := uint64(0); i < 1024; i++ {
		enc := n.Code(i)
		dec := n.Decode(enc)
		if i != dec {
			t.Errorf("Unexpected value for %d - enc is %b, dec is %d\n", i, enc, dec)
		}
︙︙

Powered by Fossil · RSS