Closure in RPL

[Albert Chan]

(11-20-2022 02:29 AM)Thomas Klemm Wrote:  Using MAX on a list is \(\mathcal{O}(n)\) while LSORT is probably \(\mathcal{O}(n\log{}n)\).
But I don't think it matters in this case.

I think the bottleneck is PROOT. What is its time complexity?
For example, below trick will reduce primes needed. How much time will it save?

Primes grow slower than any geometric series. Asymptotically, p_n ≈ n*ln(n)

Let M = minimum absolute root function

M(2+3x+5x^2+...+887*x^153) ≈ M((2+3x+5x^2+...+683*x^123) + 683*x^124/(1-x))

Last term assumed primes stop growing after p₁₂₄ = 683, thus the factor 1/(1-x)
Multiply by (1-x), we have another polynomial that contains the same min abs root, but with less terms.

2 + (3-2)*x + (5-3)*x^2 + (7-5)*x^3 + ... + (683-677)*x^123