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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
|
package addchain
import (
"fmt"
"math/big"
"github.com/mmcloughlin/addchain/internal/bigint"
)
// Op is an instruction to add positions I and J in a chain.
type Op struct{ I, J int }
// IsDouble returns whether this operation is a doubling.
func (o Op) IsDouble() bool { return o.I == o.J }
// Operands returns the indicies used in this operation. This will contain one
// or two entries depending on whether this is a doubling.
func (o Op) Operands() []int {
if o.IsDouble() {
return []int{o.I}
}
return []int{o.I, o.J}
}
// Uses reports whether the given index is one of the operands.
func (o Op) Uses(i int) bool {
return o.I == i || o.J == i
}
// Program is a sequence of operations.
type Program []Op
// Shift appends a sequence of operations that bitwise shift index i left by s,
// equivalent to s double operations. Returns the index of the result.
func (p *Program) Shift(i int, s uint) (int, error) {
for ; s > 0; s-- {
next, err := p.Double(i)
if err != nil {
return 0, err
}
i = next
}
return i, nil
}
// Double appends an operation that doubles index i. Returns the index of the
// result.
func (p *Program) Double(i int) (int, error) {
return p.Add(i, i)
}
// Add appends an operation that adds indices i and j. Returns the index of the
// result.
func (p *Program) Add(i, j int) (int, error) {
if err := p.boundscheck(i); err != nil {
return 0, err
}
if err := p.boundscheck(j); err != nil {
return 0, err
}
*p = append(*p, Op{i, j})
return len(*p), nil
}
// boundscheck returns an error if i is out of bounds.
func (p Program) boundscheck(i int) error {
// Note the corresponding chain is one longer than the program.
n := len(p)
switch {
case i < 0:
return fmt.Errorf("negative index %d", i)
case i > n:
return fmt.Errorf("index %d out of bounds", i)
}
return nil
}
// Doubles returns the number of doubles in the program.
func (p Program) Doubles() int {
doubles, _ := p.Count()
return doubles
}
// Adds returns the number of adds in the program.
func (p Program) Adds() int {
_, adds := p.Count()
return adds
}
// Count returns the number of doubles and adds in the program.
func (p Program) Count() (doubles, adds int) {
for _, op := range p {
if op.IsDouble() {
doubles++
} else {
adds++
}
}
return
}
// Evaluate executes the program and returns the resulting chain.
func (p Program) Evaluate() Chain {
c := New()
for _, op := range p {
sum := new(big.Int).Add(c[op.I], c[op.J])
c = append(c, sum)
}
return c
}
// ReadCounts returns how many times each index is read in the program.
func (p Program) ReadCounts() []int {
reads := make([]int, len(p)+1)
for _, op := range p {
for _, i := range op.Operands() {
reads[i]++
}
}
return reads
}
// Dependencies returns an array of bitsets where each bitset contains the set
// of indicies that contributed to that position.
func (p Program) Dependencies() []*big.Int {
bitsets := []*big.Int{bigint.One()}
for i, op := range p {
bitset := new(big.Int).Or(bitsets[op.I], bitsets[op.J])
bitset.SetBit(bitset, i+1, 1)
bitsets = append(bitsets, bitset)
}
return bitsets
}
|
