VectorIntegerReconstructorΒΆ

vecrec.spad line 384 [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

one step of Hensel lifting

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

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

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

combines rational reconstruction with removal of common denominators in blocks.

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

remove common denominators in blocks