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: % -> Union(Record(numers: PrimitiveArray Integer, denoms: PrimitiveArray Integer), failed)

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

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.

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.