helib::AddDAG Class Reference

A class representing the logic of the order of bit products when adding two integers. More...

Public Member Functions
void	init (const CtPtrs &a, const CtPtrs &b)
	Build a plan to add a and b. More...
	AddDAG (const CtPtrs &a, const CtPtrs &b)
void	apply (CtPtrs &sum, const CtPtrs &a, const CtPtrs &b, long sizeLimit=0)
	Perform the actual addition. More...
long	lowLvl () const
	Returns the lowest level in this DAG. More...
DAGnode *	findP (long i, long j) const
	Returns a pointer to the a 'p' node of index (i,j) More...
DAGnode *	findQ (long i, long j) const
	Returns a pointer to the a 'q' node of index (i,j) More...

Detailed Description

A class representing the logic of the order of bit products when adding two integers.

Given two input arrays a[], b[], we build a DAG with each node representing a term either of the form p_{i,j} = \prod_{t=j}^i (a[t]+b[t]), or of the form q_{i,j} = (a[j]*b[j]) * \prod_{t=j+1}^i (a[t]+b[t]). The source nodes are of the forms (a[i]*b[i]) and (a[i]+b[i]), and each non-source node has exactly two parents, whose product yields that node.

When building the DAG, we keep the level of each node as high as possible. For example we can set q_{i,j}=p_{i,k}*q_{k-1,j} or q_{i,j}=p_{i,k+1}*q_{k,j} (among other options), and we choose the option that results in the highest level. In addition, we try to minimize the number of nodes in the DAG that actually need to be computed while adding the two numbers (subject to still consuming as few levels as possible).

Constructor & Destructor Documentation

AddDAG()

helib::AddDAG::AddDAG ( const CtPtrs &  a, const CtPtrs &  b  )

inline

Member Function Documentation

apply()

void helib::AddDAG::apply	(	CtPtrs &	sum,
		const CtPtrs &	a,
		const CtPtrs &	b,
		long	sizeLimit = 0
	)

Perform the actual addition.

Apply the DAG to actually compute the sum.

findP()

DAGnode* helib::AddDAG::findP ( long  i, long  j  ) const

inline

Returns a pointer to the a 'p' node of index (i,j)

findQ()

DAGnode* helib::AddDAG::findQ ( long  i, long  j  ) const

inline

Returns a pointer to the a 'q' node of index (i,j)

init()

void helib::AddDAG::init	(	const CtPtrs &	a,
		const CtPtrs &	b
	)

Build a plan to add a and b.

lowLvl()

long helib::AddDAG::lowLvl ( ) const

inline

Returns the lowest level in this DAG.