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
|
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 bytes
// 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 bytes by one to allow for zero gives
// 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 the n-th fibonacci number
// The result is stored after calculation
func (f Numbers) Nth(index int) uint64 {
switch {
case index <= 1:
// 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++ {
return 1
case f[index] > 0:
break
default:
f[index] = f.Nth(index-1) + f.Nth(index-2)
return f[index]
return fibs
}
// Returns a fibonacci code for an integer as specified in the package doc.
// 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.Nth(i+1) <= value {
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.Nth(i) <= value {
if f[i] <= value {
result |= 1
value -= f.Nth(i)
value -= f[i]
}
}
return
}
// Returns an integer from a fibonacci code as specified in the package doc.
// 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.Nth(i)
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.Nth(i) - 1
result += f[i] - 1
return
}
|