Documentation
¶
Overview ¶
Package contfrac implements addition sequence algorithms based on continued-fraction expansions.
Index ¶
Constants ¶
This section is empty.
Variables ¶
var Strategies = []Strategy{ BinaryStrategy{}, CoBinaryStrategy{}, DichotomicStrategy{}, SqrtStrategy{}, TotalStrategy{}, DyadicStrategy{}, FermatStrategy{}, }
Strategies lists all available continued fraction strategies.
Functions ¶
This section is empty.
Types ¶
type Algorithm ¶
type Algorithm struct {
// contains filtered or unexported fields
}
Algorithm uses the continued fractions method for finding an addition chain contfrac [efficientcompaddchain].
func NewAlgorithm ¶
NewAlgorithm builds a continued fractions addition sequence algorithm using the provided strategy for selecting the auziallary integer k.
func (Algorithm) FindSequence ¶
FindSequence applies the continued fractions method to build a chain containing targets.
type BinaryStrategy ¶
type BinaryStrategy struct{}
BinaryStrategy implements the binary strategy, which just sets k = floor(n/2). See [efficientcompaddchain] page 26. Since this is a singleton strategy it gives rise to a logarithmic sequence algoirithm that may not be optimal.
func (BinaryStrategy) Singleton ¶
func (BinaryStrategy) Singleton() bool
Singleton returns true, since the binary strategy returns a single proposal for k.
func (BinaryStrategy) String ¶
func (BinaryStrategy) String() string
type CoBinaryStrategy ¶
type CoBinaryStrategy struct{}
CoBinaryStrategy implements the co-binary strategy, also referred to as the "modified-binary" strategy. See [efficientcompaddchain] page 26 or [gencontfrac] page 6. Since this is a singleton strategy it gives rise to a logarithmic sequence algorithm that may not be optimal.
func (CoBinaryStrategy) K ¶
func (CoBinaryStrategy) K(n *big.Int) []*big.Int
K returns floor(n/2) when n is even, or floor((n+1)/2) when n is odd.
func (CoBinaryStrategy) Singleton ¶
func (CoBinaryStrategy) Singleton() bool
Singleton returns true, since the co-binary strategy returns a single proposal for k.
func (CoBinaryStrategy) String ¶
func (CoBinaryStrategy) String() string
type DichotomicStrategy ¶
type DichotomicStrategy struct{}
DichotomicStrategy is a singleton strategy, defined in [efficientcompaddchain] page 28. This gives rise to a logarithmic sequence algorithm, but the result is not necessarily optimal.
func (DichotomicStrategy) K ¶
func (DichotomicStrategy) K(n *big.Int) []*big.Int
K returns only one suggestion for k, namely floor( n / 2ʰ ) where h = log2(n)/2.
func (DichotomicStrategy) Singleton ¶
func (DichotomicStrategy) Singleton() bool
Singleton returns true, since the dichotomic strategy suggests just one k.
func (DichotomicStrategy) String ¶
func (DichotomicStrategy) String() string
type DyadicStrategy ¶
type DyadicStrategy struct{}
DyadicStrategy implements the Dyadic Strategy, defined in [efficientcompaddchain] page 28. This gives rise to a sequence algorithm with complexity O(n*log³(n)). Must not be used for large inputs.
func (DyadicStrategy) K ¶
func (DyadicStrategy) K(n *big.Int) []*big.Int
K returns floor( n / 2ʲ ) for all j.
func (DyadicStrategy) Singleton ¶
func (DyadicStrategy) Singleton() bool
Singleton returns false, since the dyadic strategy returns more than once k.
func (DyadicStrategy) String ¶
func (DyadicStrategy) String() string
type FermatStrategy ¶
type FermatStrategy struct{}
FermatStrategy implements Fermat's Strategy, defined in [efficientcompaddchain] page 28. This returns a set of possible k of size O(log(log(n))), giving rise to a faster algorithm than the Dyadic strategy. This has been shown to be near optimal for small inputs. Must not be used for large inputs.
func (FermatStrategy) K ¶
func (FermatStrategy) K(n *big.Int) []*big.Int
K returns floor( n / 2^(2^j) ) for all j.
func (FermatStrategy) Singleton ¶
func (FermatStrategy) Singleton() bool
Singleton returns false, since Fermat's strategy returns more than once k.
func (FermatStrategy) String ¶
func (FermatStrategy) String() string
type SqrtStrategy ¶
type SqrtStrategy struct{}
SqrtStrategy chooses k to be floor(sqrt(n)). See [gencontfrac] page 6. Since this is a singleton strategy, it gives rise to a logarithmic sequence algorithm that's not necessarily optimal.
func (SqrtStrategy) Singleton ¶
func (SqrtStrategy) Singleton() bool
Singleton returns true, since the square root strategy suggests just one k.
func (SqrtStrategy) String ¶
func (SqrtStrategy) String() string
type Strategy ¶
type Strategy interface {
// K returns values of k to try given n.
K(n *big.Int) []*big.Int
// Singleton returns whether every call to K will return one value of k. This
// determines whether the resulting continued fractions sequence algorithm will
// be logarithmic, and therefore suitable for large inputs.
Singleton() bool
// String returns a name for the strategy.
String() string
}
Strategy is a method of choosing the auxiliary integer k in the continued fraction method outlined in [efficientcompaddchain].
type TotalStrategy ¶
type TotalStrategy struct{}
TotalStrategy returns all possible values of k less than n. This will result in the optimal continued fraction chain at a complexity of O(n² log²(n)). Note that the optimal continued fraction chain is not necessarily the optimal chain. Must not be used for large inputs.
func (TotalStrategy) Singleton ¶
func (TotalStrategy) Singleton() bool
Singleton returns false, since the total strategy returns more than once k.
func (TotalStrategy) String ¶
func (TotalStrategy) String() string
Source Files