VectorIntegerReconstructor

vecrec.spad line 388 [edit on github]

This domain supports modular methods based on evaluation and rational reconstruction.Each evaluation is done modulo machine sized prime p.Both Chinese remaindering and (linear) Hensel lift are supported. Once enough evaluations are known rational reconstruction produces vector of rational numbers or integers.

chinese_update : (U32Vector, Integer, %) -> Void

chinese_update(v, p, r) informs r about evaluation at p

empty : Integer -> %

empty(n) produces reconstructor with n slots

hensel_update : (U32Vector, Integer, %) -> Void

hensel_update(v, p, r) performs one step of Hensel lifting

rational_reconstruction : (Integer, Integer, Integer, Integer) -> Union(Record(num : Integer, den : Integer), "failed")

rational_reconstruction(x, y, i, j) finds rational number r/s such that r/s = x modulo y, |r| <= i and q <= j. Returns "failed" when such r/s does not exist.

rational_reconstruction : % -> Union(Record(numers : PrimitiveArray(Integer), denoms : PrimitiveArray(Integer)), "failed")

rational_reconstruction(r) reconstructs vector of rational functions based on information stored in reconstructor.

reconstruct : (%, Vector(Integer)) -> Union(PrimitiveArray(Integer), "failed")

reconstruct(r, bo) combines rational reconstruction with removal of common denominators in blocks.

remove_denoms : (Vector(Integer), PrimitiveArray(Integer), PrimitiveArray(Integer)) -> PrimitiveArray(Integer)

remove_denoms(bo, n, d) remove common denominators in blocks. n is vector of numerators, d is vector of denomiantors, bo(i) contains starting index of block number i.