195 lines
4.6 KiB
Go
195 lines
4.6 KiB
Go
// Package addchain provides addition chain types and operations on them.
|
|
package addchain
|
|
|
|
import (
|
|
"errors"
|
|
"fmt"
|
|
"math/big"
|
|
|
|
"github.com/mmcloughlin/addchain/internal/bigint"
|
|
"github.com/mmcloughlin/addchain/internal/bigints"
|
|
)
|
|
|
|
// References:
|
|
//
|
|
// [efficientcompaddchain] Bergeron, F., Berstel, J. and Brlek, S. Efficient computation of addition
|
|
// chains. Journal de theorie des nombres de Bordeaux. 1994.
|
|
// http://www.numdam.org/item/JTNB_1994__6_1_21_0
|
|
// [knuth] Knuth, Donald E. Evaluation of Powers. The Art of Computer Programming, Volume 2
|
|
// (Third Edition): Seminumerical Algorithms, chapter 4.6.3. 1997.
|
|
// https://www-cs-faculty.stanford.edu/~knuth/taocp.html
|
|
|
|
// Chain is an addition chain.
|
|
type Chain []*big.Int
|
|
|
|
// New constructs the minimal chain {1}.
|
|
func New() Chain {
|
|
return Chain{big.NewInt(1)}
|
|
}
|
|
|
|
// Int64s builds a chain from the given int64 values.
|
|
func Int64s(xs ...int64) Chain {
|
|
return Chain(bigints.Int64s(xs...))
|
|
}
|
|
|
|
// Clone the chain.
|
|
func (c Chain) Clone() Chain {
|
|
return bigints.Clone(c)
|
|
}
|
|
|
|
// AppendClone appends a copy of x to c.
|
|
func (c *Chain) AppendClone(x *big.Int) {
|
|
*c = append(*c, bigint.Clone(x))
|
|
}
|
|
|
|
// End returns the last element of the chain.
|
|
func (c Chain) End() *big.Int {
|
|
return c[len(c)-1]
|
|
}
|
|
|
|
// Ops returns all operations that produce the kth position. This could be empty
|
|
// for an invalid chain.
|
|
func (c Chain) Ops(k int) []Op {
|
|
ops := []Op{}
|
|
s := new(big.Int)
|
|
|
|
// If the prefix is ascending this can be done in linear time.
|
|
if c[:k].IsAscending() {
|
|
for l, r := 0, k-1; l <= r; {
|
|
s.Add(c[l], c[r])
|
|
cmp := s.Cmp(c[k])
|
|
if cmp == 0 {
|
|
ops = append(ops, Op{l, r})
|
|
}
|
|
if cmp <= 0 {
|
|
l++
|
|
} else {
|
|
r--
|
|
}
|
|
}
|
|
return ops
|
|
}
|
|
|
|
// Fallback to quadratic.
|
|
for i := 0; i < k; i++ {
|
|
for j := i; j < k; j++ {
|
|
s.Add(c[i], c[j])
|
|
if s.Cmp(c[k]) == 0 {
|
|
ops = append(ops, Op{i, j})
|
|
}
|
|
}
|
|
}
|
|
|
|
return ops
|
|
}
|
|
|
|
// Op returns an Op that produces the kth position.
|
|
func (c Chain) Op(k int) (Op, error) {
|
|
ops := c.Ops(k)
|
|
if len(ops) == 0 {
|
|
return Op{}, fmt.Errorf("position %d is not the sum of previous entries", k)
|
|
}
|
|
return ops[0], nil
|
|
}
|
|
|
|
// Program produces a program that generates the chain.
|
|
func (c Chain) Program() (Program, error) {
|
|
// Sanity checks.
|
|
if len(c) == 0 {
|
|
return nil, errors.New("chain empty")
|
|
}
|
|
|
|
if c[0].Cmp(big.NewInt(1)) != 0 {
|
|
return nil, errors.New("chain must start with 1")
|
|
}
|
|
|
|
if bigints.Contains(bigint.Zero(), c) {
|
|
return nil, errors.New("chain contains zero")
|
|
}
|
|
|
|
for i := 0; i < len(c); i++ {
|
|
for j := i + 1; j < len(c); j++ {
|
|
if bigint.Equal(c[i], c[j]) {
|
|
return nil, fmt.Errorf("chain contains duplicate: %v at positions %d and %d", c[i], i, j)
|
|
}
|
|
}
|
|
}
|
|
|
|
// Produce the program.
|
|
p := Program{}
|
|
for k := 1; k < len(c); k++ {
|
|
op, err := c.Op(k)
|
|
if err != nil {
|
|
return nil, err
|
|
}
|
|
p = append(p, op)
|
|
}
|
|
|
|
return p, nil
|
|
}
|
|
|
|
// Validate checks that c is in fact an addition chain.
|
|
func (c Chain) Validate() error {
|
|
_, err := c.Program()
|
|
return err
|
|
}
|
|
|
|
// Produces checks that c is a valid chain ending with target.
|
|
func (c Chain) Produces(target *big.Int) error {
|
|
if err := c.Validate(); err != nil {
|
|
return err
|
|
}
|
|
if c.End().Cmp(target) != 0 {
|
|
return errors.New("chain does not end with target")
|
|
}
|
|
return nil
|
|
}
|
|
|
|
// Superset checks that c is a valid chain containing all the targets.
|
|
func (c Chain) Superset(targets []*big.Int) error {
|
|
if err := c.Validate(); err != nil {
|
|
return err
|
|
}
|
|
for _, target := range targets {
|
|
if !bigints.Contains(target, c) {
|
|
return fmt.Errorf("chain does not contain %v", target)
|
|
}
|
|
}
|
|
return nil
|
|
}
|
|
|
|
// IsAscending reports whether the chain is ascending, that is if it's in sorted
|
|
// order without repeats, as defined in [knuth] Section 4.6.3 formula (11).
|
|
// Does not fully validate the chain, only that it is ascending.
|
|
func (c Chain) IsAscending() bool {
|
|
if len(c) == 0 || !bigint.EqualInt64(c[0], 1) {
|
|
return false
|
|
}
|
|
for i := 1; i < len(c); i++ {
|
|
if c[i-1].Cmp(c[i]) >= 0 {
|
|
return false
|
|
}
|
|
}
|
|
return true
|
|
}
|
|
|
|
// Product computes the product of two addition chains. The is the "o times"
|
|
// operator defined in [efficientcompaddchain] Section 2.
|
|
func Product(a, b Chain) Chain {
|
|
c := a.Clone()
|
|
last := c.End()
|
|
for _, x := range b[1:] {
|
|
y := new(big.Int).Mul(last, x)
|
|
c = append(c, y)
|
|
}
|
|
return c
|
|
}
|
|
|
|
// Plus adds x to the addition chain. This is the "o plus" operator defined in
|
|
// [efficientcompaddchain] Section 2.
|
|
func Plus(a Chain, x *big.Int) Chain {
|
|
c := a.Clone()
|
|
y := new(big.Int).Add(c.End(), x)
|
|
return append(c, y)
|
|
}
|