compute list CRT via tree #34512
Description
Currently, CRT_list() works by folding the input from one side. In typical cases of interest, it is much more efficient to use a binary-tree structure instead. (This is similar to how prod() is implemented.)
Example:
sage: ms = list(primes(10^5))
sage: xs = [randrange(m) for m in ms]
sage: %timeit CRT_list(xs, ms)Sage 9.7.rc0:
7.42 s ± 20 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
This branch:
86.5 ms ± 169 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
Similar speedups can be observed for polynomials; example (a length‑1024 inverse DFT):
sage: F = GF(65537)
sage: a = F(1111)
sage: assert a.multiplicative_order() == 1024
sage: R.<x> = F[]
sage: ms = [x - a^i for i in range(1024)]
sage: zs = [R(F.random_element()) for _ in ms]
sage: %timeit CRT_list(zs, ms)
Sage 9.7.rc0:
347 ms ± 863 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)
This branch:
29.3 ms ± 37.1 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
Component: algebra
Author: Lorenz Panny
Branch/Commit: 5f3a23f
Reviewer: Kwankyu Lee
Issue created by migration from https://trac.sagemath.org/ticket/34512