heuristic

Documentation

Overview

Package heuristic implements heuristic-based addition sequence algorithms with the Bos-Coster Makesequence structure.

Index

• type Algorithm
  • func NewAlgorithm(h Heuristic) *Algorithm
  • func (h Algorithm) FindSequence(targets []*big.Int) (addchain.Chain, error)
  • func (h Algorithm) String() string
• type Approximation
  • func (Approximation) String() string
  • func (Approximation) Suggest(f []*big.Int, target *big.Int) []*big.Int
• type DeltaLargest
  • func (DeltaLargest) String() string
  • func (DeltaLargest) Suggest(f []*big.Int, target *big.Int) []*big.Int
• type Halving
  • func (Halving) String() string
  • func (Halving) Suggest(f []*big.Int, target *big.Int) []*big.Int
• type Heuristic
  • func UseFirst(heuristics ...Heuristic) Heuristic

Types

type Algorithm

type Algorithm struct {
	// contains filtered or unexported fields
}

Algorithm searches for an addition sequence using a heuristic at each step. This implements the framework given in [mpnt], page 63, with the heuristic playing the role of the "newnumbers" function.

func NewAlgorithm

func NewAlgorithm(h Heuristic) *Algorithm

NewAlgorithm builds a heuristic algorithm.

func (Algorithm) FindSequence

func (h Algorithm) FindSequence(targets []*big.Int) (addchain.Chain, error)

FindSequence searches for an addition sequence for the given targets.

func (Algorithm) String

func (h Algorithm) String() string

type Approximation

type Approximation struct{}

Approximation is the "Approximation" heuristic from [boscoster].

func (Approximation) String

func (Approximation) String() string

func (Approximation) Suggest

func (Approximation) Suggest(f []*big.Int, target *big.Int) []*big.Int

Suggest applies the "Approximation" heuristic. This heuristic looks for two elements a, b in the list that sum to something close to the target element f. That is, we look for f-(a+b) = epsilon where a ⩽ b and epsilon is a "small" positive value.

type DeltaLargest

type DeltaLargest struct{}

DeltaLargest implements the simple heuristic of adding the delta between the largest two entries in the protosequence.

func (DeltaLargest) String

func (DeltaLargest) String() string

func (DeltaLargest) Suggest

func (DeltaLargest) Suggest(f []*big.Int, target *big.Int) []*big.Int

Suggest proposes inserting target-max(f).

type Halving

type Halving struct{}

Halving is the "Halving" heuristic from [boscoster].

func (Halving) String

func (Halving) String() string

func (Halving) Suggest

func (Halving) Suggest(f []*big.Int, target *big.Int) []*big.Int

Suggest applies when the target is at least twice as big as the next largest. If so it will return a sequence of doublings to insert. Otherwise it will return nil.

type Heuristic

type Heuristic interface {
	// Suggest insertions given a target and protosequence f. Protosequence must
	// contain sorted distinct integers.
	Suggest(f []*big.Int, target *big.Int) []*big.Int

	// String returns a name for the heuristic.
	String() string
}

Heuristic suggests insertions given a current protosequence.

func UseFirst

func UseFirst(heuristics ...Heuristic) Heuristic

UseFirst builds a compositite heuristic that will make the first non-nil suggestion from the sub-heuristics.