Skip to content

Support for fault/error-tolerant rational reconstruction #2407

@JohnAAbbott

Description

@JohnAAbbott

Is your feature request related to a problem? Please describe.
FLINT offers non-fault-tolerant rational reconstruction which includes as a final check that the putative numerator and denominator are coprime (line 1038 in reconstruct_fmpz_2.c); it would be convenient to be able suppress this check.

Describe the solution you'd like
No special desire: it could be an extra boolean arg, or a new function name.
Better still a new "probabilistic" function which performs the fault-tolerant reconstruction.

Describe alternatives you've considered
It seems a shame to reimplement the sophisticated, adaptive euclidean algorithm which is already in FLINT; nevertheless, we may develop (in Julia) a Lehmer-based implementation as a stop-gap.

Additional context
Add any other context about the feature request here.
Two related articles:

  1. https://arxiv.org/pdf/1303.2965 (by me, but the Heuristic algorithm is a bit different)
  2. https://arxiv.org/abs/1207.1651 (by Claus Fieker et al.)

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions