Karim Belabas on Wed, 25 Oct 2023 10:27:31 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Polynomials with integer roots 

* Gordon Royle [2023-10-25 08:14]:
> Hi Pari/GP ers
> 
> Suppose that I have billions of polynomials of degree around 10 with integer coefficients of modest size.
> 
> I want to find the tiny number, if any, that have all integer roots.
> 
> What is the fastest way to do this in gp ?

Say the list is contained in vector L. Here's the simplest way.

  [ T | T <- L, #nfroots(,T) == poldegree(T) ]

There are ways to do it faster in library mode by cloning a few private
functions around DDF_roots() and having them abort as soon as the
polynomial is not totally split modulo some small prime p [when
Flx_nbroots in pick_prime() returns a lower value than the degree].

I guess trying to replicate that in gp will slow down the program rather
than speed it up... You might still want to experiment with
  
  install(Flx_nbroots, GU);  \\ once
  Flx_nbroots(T, p) == poldegree(T)

where p is in a small list of primes. (Without installing functions,
you'll have to use factormod(T, p, 1) which will be slower.)

If you can organize you work that way, it will be more efficient to weed
out polynomials as soon as they are produced rather than store them in a
huge list.

Cheers,

    K.B.
-- 
Pr. Karim Belabas, U. Bordeaux, Vice-président en charge du Numérique
Institut de Mathématiques de Bordeaux UMR 5251 - (+33) 05 40 00 29 77
http://www.math.u-bordeaux.fr/~kbelabas/