Documentation ¶
Overview ¶
Package dag provides the base for Directed Asynchronous Graphs functions with two inputs per node. It also includes examples using this base.
Index ¶
- Constants
- type BoolFunStub
- type BoolTry
- type DTryData
- type Dag
- type FloatFunStub
- type FloatTry
- type FunBool
- type FunFloat
- type Int2Float
- type Int2FloatList
- type Int2FloatRange
- type Node
- type Opt
- type Opt2Float
- type Opt4Bool
- type OptBool
- type OptFloat
- type OptMorphFloat
- type SamplerBool
- type SamplerFloat
- type Try
- type TryData
Examples ¶
Constants ¶
const ( // source from global input array ITypeVar = iota // source from another node ITypeNode // source from a constant node of value 1 ITypeConst )
The code for the input sources for the node.
const ( // output not yet allocated OTypeNone = iota // output allocated to be used by a node OTypeNode // output adopted by an output OTypeOutput )
The code for output type from node.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type BoolFunStub ¶
type BoolFunStub = futil.IntFunStub
BoolFunStub gives interface to setpso
func NewFunBool ¶
func NewFunBool(nnode, nbitslookback int, opt OptBool, sizeCostFactor int64, sampler SamplerBool, sampleSize int, rnd *rand.Rand) *BoolFunStub
NewFunBool returns a new *FunBool ready to be used.
Example ¶
s := parity.NewSampler(4) opt := NewOpt4Bool() nnode := 4 nbitslookback := 4 sizeCostFactor := int64(1) sampleSize := 16 rnd := rand.New(rand.NewSource(3142)) f := NewFunBool(nnode, nbitslookback, opt, sizeCostFactor, s, sampleSize, rnd) fmt.Printf("About:\n %s\n", f.About()) z := big.NewInt(0) fmt.Sscanf("056038017", "%x", z) fmt.Printf("z: %b\n", z) t := f.CreateData() f.IDecode(t, z) fmt.Printf("Number of bits to encode: %d\n", f.MaxLen()) fmt.Printf("Dag Decode:\n %s\n", t.Decode()) cost := big.NewInt(0) f.Cost(t, cost) fmt.Printf("Cost: %v\n", cost)
Output:
type DTryData ¶
type DTryData struct { // interior node array INodes []Node // interface to node operation Opt Opt // contains filtered or unexported fields }
DTryData contains the decoded data for a try without committing explicitely to node input data type.
type Dag ¶
type Dag struct { // interface to node operation Opt Opt // contains filtered or unexported fields }
Dag is the method for encoding/decoding special type of Directed Asynchronous Graph into a binary string with an array of input nodes and an array of ordered interior nodes.
Node Linking ¶
For encoding/decoding conceptually The inputs are placed before the interior nodes to make one contiguous array and each interior node has a pair of offset values of positive integers each obtained by adding 1 to a binary string of length nBinOffset. The offset values are used to link each interior node to two inputs. if an offset reaches further than available slots the offset is taken to be pointing to an element with value 1.
Interior Node Operation ¶
Each interior node is allocated OptSize() bits to encode how the two inputs to the node are operated on to give an output value. At this level how this is done is opaque: an interface called Opt does this instead using the method Opt().
func NewDag ¶
NewDag creates a dag-function base for carrying out common operations. opt gives the detailed process of converting the input pair of an interior node into an output. nvar gives the number of inputs to the function; nnode is the number of interior nodes; nout is the number of expected outputs which should be significantly less than nnode; nbitslookback is the number of bits used to give a look-back offset integer, where a look-back offset of i points to the i+1 th object before the inner-node. Note the inputs are before the inner node and anything before an input is regarded as a in put with a constant value of 1.
using sampleSize random samples.
Example ¶
opt := NewOpt4Bool() nvar := 4 nnode := 4 nout := 1 nbitslookback := 4 d := NewDag(nvar, nnode, nout, nbitslookback, opt) z := big.NewInt(0) fmt.Sscanf("056036016", "%x", z) fmt.Printf("z: %b\n", z) t := d.CreateData() d.IDecode(t, z) fmt.Printf("Number of bits to encode: %d\n", d.MaxLen()) fmt.Printf("Dag Decode:\n %s\n", t.Decode())
Output:
func (*Dag) Constraint ¶
Constraint attempts to constrain hint possibly using a copy of pre to do this
func (*Dag) CreateData ¶
CreateData creates a empty structure for decoded try
type FloatFunStub ¶
type FloatFunStub = futil.SFloatFunStub
FloatFunStub gives interface to setpso
func NewFunFloat ¶
func NewFunFloat(nnode, nbitslookback int, opt OptFloat, sizeCostFactor float64, sampler SamplerFloat, sampleSize int, rnd *rand.Rand, Tc, sigmaThres float64) *FloatFunStub
NewFunFloat returns a new *FunFloat ready to be used.
type FunBool ¶
type FunBool struct { // temporary store of dag decoder *Dag // contains filtered or unexported fields }
FunBool is the cost-function for evaluating boolean DAG encoded as a (positive) big integer.
func (*FunBool) Cost ¶
Cost evaluates cost, where a lower cost is better. In this case where
cost = node usage cost * sizeCostFactor + number of output component match errors
using random samples.
func (*FunBool) DefaultParam ¶
DefaultParam gives a default that satisfies constraints
func (*FunBool) Delete ¶
Delete hints to the function to remove/replace the ith item it returns true if the function takes the hint
func (*FunBool) SetSizeCostFactor ¶
SetSizeCostFactor sets factor weight to include INode usage cost
func (*FunBool) SizeCostFactor ¶
SizeCostFactor returns factor weight to include INode usage cost
type FunFloat ¶
type FunFloat struct { // temporary store of dag decoder *Dag // Timeconstant for cost evaluation Tc float64 // contains filtered or unexported fields }
FunFloat is the cost-function for evaluating boolean DAG encoded as a (positive) big integer.
func (*FunFloat) Cost ¶
Cost evaluates cost, where a lower cost is better. In this case where
cost = node usage cost * sizeCostFactor + sum of absolute value of output mismatches
using random samples.
func (*FunFloat) DefaultParam ¶
DefaultParam gives a default that satisfies constraints
func (*FunFloat) Delete ¶
Delete hints to the function to remove/replace the ith item it returns true if the function takes the hint
func (*FunFloat) SetSizeCostFactor ¶
SetSizeCostFactor sets factor weight to include INode usage cost
func (*FunFloat) SizeCostFactor ¶
SizeCostFactor returns factor weight to include INode usage cost
type Int2Float ¶
type Int2Float interface { // the mapping Float(uint) float64 // maximum number of least significant bits of the integer used BitSize() uint }
Int2Float gives a mapping of an indexing integer to a float.
type Int2FloatList ¶
type Int2FloatList struct {
// contains filtered or unexported fields
}
Int2FloatList uses a list of values to give the int to float index where the index is obtained taking modulus of the index length. Typicall the length of the list is a power of 2.
func NewInt2FloatList ¶
func NewInt2FloatList(a ...float64) *Int2FloatList
NewInt2FloatList creates an Int2floatList from a list of values.
func (*Int2FloatList) BitSize ¶
func (f *Int2FloatList) BitSize() uint
BitSize gives the number of bits needed for the index.
func (*Int2FloatList) Float ¶
func (f *Int2FloatList) Float(index uint) float64
Float returns the corresponding float value where the index od modded with the list length to avoid over flow.
type Int2FloatRange ¶
type Int2FloatRange struct {
// contains filtered or unexported fields
}
Int2FloatRange converts bits to a range of floats
func NewInt2FloatRange ¶
func NewInt2FloatRange(nbits int, begin, end float64) *Int2FloatRange
NewInt2FloatRange creates an Int2floatRange from number of bits to use and the corresponding floating point range .
func (*Int2FloatRange) BitSize ¶
func (f *Int2FloatRange) BitSize() uint
BitSize gives the number of bits needed for the index.
func (*Int2FloatRange) Float ¶
func (f *Int2FloatRange) Float(index uint) float64
Float returns the corresponding float value
type Node ¶
type Node struct {
// contains filtered or unexported fields
}
Node is interior node Data
type Opt ¶
type Opt interface { // gives a description of the operation type About() string //this gives a human readable version of the encoded operation opt. Decode(opt uint) string // Number of bits needed to store opt encoding. BitSize() int // cost of using opt Cost(opt uint) int }
Opt is bearbones interface used by Dag to decode operations into human readable form for the nodes and reserve spacing for the nodes operation encoding.
type Opt2Float ¶
type Opt2Float struct { // cost of using node table NodeCost [4]int // contains filtered or unexported fields }
Opt2Float encodes the Float operation as a choice betwee '+','-','/','^' operations
func NewOpt2Float ¶
func NewOpt2Float() *Opt2Float
NewOpt2Float creates a Opt2Float and inserts default node cost values
type Opt4Bool ¶
type Opt4Bool struct { // cost of using node table NodeCost [16]int // contains filtered or unexported fields }
Opt4Bool encodes the Boolean operation as a 2-dimesion table of bits. the rows are indexed by the left binary in put l and the column by the right binary input r; the value of the table entry gives the corresponding binary output o. each op is thus represented by a 4 bit integer opt where o=opt[r+2*l] treated as an array of bits this gives 16 possible operations.
func NewOpt4Bool ¶
func NewOpt4Bool() *Opt4Bool
NewOpt4Bool creates a Opt4Bool and inserts default node cost values that discourages input negation, input selection, and ignore input nodes. It promotes or("|"),and("&"), exclusive or ("+") operation nodes .
Example ¶
o := NewOpt4Bool() opt := uint(6) // code for exclusive or fmt.Printf("Encoding bit size: %d\n", o.BitSize()) fmt.Printf("Symbol:[%s]\n", o.Decode(opt)) fmt.Printf("Node cost: %d\n", o.Cost(opt)) for i := 0; i < 2; i++ { for j := 0; j < 2; j++ { fmt.Printf("l=%d r= %d => %d\n", i, j, o.Opt(uint(i), uint(j), opt)) } }
Output: Encoding bit size: 4 Symbol:[ + ] Node cost: 1 l=0 r= 0 => 0 l=0 r= 1 => 1 l=1 r= 0 => 1 l=1 r= 1 => 0
type OptBool ¶
type OptBool interface { Opt // function to generate a node output l,r are the left and right inputs and opt // is the encoded operation to be carried out on l,r to return the result. Opt(l, r uint, opt uint) uint }
OptBool is interface for interior node operation using boolean operations . l and r are the left and right inputs to the node, opt is a, positive integer, operations code
type OptFloat ¶
type OptFloat interface { Opt // function to generate a node output l,r are the left and right inputs and opt // is the encoded operation to be carried out on l,r to return the result. Opt(l, r float64, opt uint) float64 }
OptFloat is interface for interior node operation using float operations . l and r are the left and right inputs to the node, opt is a, positive integer, operations code
type OptMorphFloat ¶
type OptMorphFloat struct {
// contains filtered or unexported fields
}
OptMorphFloat encodes the Float operation in a uniform way so the nodes can morph easily between algebraic and power law values. The operator has at first sight the strange form:
z=h(il;x)+ h(ir;y)
operating on the pair (x,y) to give z at a node. the binary string representing the operation is il|ir where il and ir sub binary sequences for left and right parts of the input to the node.
h(sc|jc|sp|jp,x)= (-1)^sc*(sign(x))^sp*C(jc)*|x|^P(jp)
where sc,sp are 0 or 1 ;jc,jp short non negative integers in the range 0<= jc<2^nc , 0<= jp<2^np that are mapped by the functions C and P to floating point values. nc,np are natural numbers giving the number of bits used to represent jc, jp. C and P are of type Int2Float.
this is surprisingly expressive for instance a ratio can be expressed using just 3 nodes.
func NewOptMorphFloat ¶
func NewOptMorphFloat(C, P Int2Float) *OptMorphFloat
NewOptMorphFloat creates a OptMorphFloat and inserts default node cost values
func (*OptMorphFloat) About ¶
func (o *OptMorphFloat) About() string
About gives description of operation type
func (*OptMorphFloat) BitSize ¶
func (o *OptMorphFloat) BitSize() int
BitSize returns Number of bits needed to store opt encoding.
func (*OptMorphFloat) Cost ¶
func (o *OptMorphFloat) Cost(opt uint) int
Cost gives the cost of using a node
func (*OptMorphFloat) Decode ¶
func (o *OptMorphFloat) Decode(opt uint) string
Decode gives a human readable discriptin of opt.
func (*OptMorphFloat) IDecode ¶
func (o *OptMorphFloat) IDecode(z uint)
IDecode splits the opt into its constituent parts
type SamplerBool ¶
type SamplerBool interface { Sample(x, y *big.Int, rnd *rand.Rand) InputSize() int OutputSize() int About() string }
SamplerBool is an interface for sampling inputs and required output results. Where x is the input array; y is the corresponding required output array of bits given by the sampler; both arrays stored as big integers; rnd is the random number generator used to create samples.
type SamplerFloat ¶
type SamplerFloat interface { Sample(x, y []float64, rnd *rand.Rand) InputSize() int OutputSize() int About() string }
SamplerFloat is an interface for sampling inputs and required output results. Where x is the input array; y is the corresponding required output array of bits given by the sampler; both arrays stored as big integers; rnd is the random number generator used to create samples.