Page 1 sur 2

option C-2014/15

Publié : jeu. sept. 11, 2014 8:39 am
par parisse
Mercredi 10/9:
Tronc commun: distinction entre donnee exacte et approchee, prise en main de Xcas pour calculs symboliques courants (menus, aide en ligne, completion debut commande touche tab)
Presentation du programme specifique de l'option C, references (aide en ligne de Xcas, page agreg xcas, references a la fin).
TP de prise en main de http://www-fourier.ujf-grenoble.fr/~par ... regtp1.pdf

Re: option C-2014/15

Publié : jeu. sept. 18, 2014 5:03 pm
par parisse
17/9:
Chapitre I: representation des objets mathematiques, algorithmes fondementaux.
1/ entiers machine, precision limitee. Entiers long, lien avec les polynomes, cout des operations de base + - * (algorithme naif) et comparaison avec la taille du resultat, il existe des algorithmes meilleurs pour la multiplication (ce qu'on peut deviner vu la taille du résultat), etude detaillee de Karatsuba pour multiplier 2 polynômes à coeffs dans un corps fini de degre<2^n -> temps en 9*3^n-8*2^n, existence d'un seuil pour multiplication naive puis Karatsuba.
Illustration avec la session Exemples>arit>multpoly de Xcas.
Multiplication de 2 polynômes à coeffs approchés par FFT
Si P1 et P2 sont 2 polynomes tels que degré(P1*P2)<n, il suffit de connaitre P1*P2 en n points pour déterminer P1*P2, par exemple les puissances xi^j d'une racine primitive n-ième complexe de 1. Comme P1*P2(x)=P1(x)*P2(x), il suffit de savoir passer des coefficients de P1 (complétés par des 0 pour en avoir n) aux valeurs P1(xi^j) et réciproquement, ce qui est la transformée de Fourier discrète (dft) de C^n dans C^n et son inverse (qui se calcule par une dft en changeant xi en 1/xi). Si n est pair, le calcul de dft(P) se déduit du calcul de dft(coeffs_pairs_de_P) et dft(coeffs_impairs_de_P) en O(n) opérations, car P(x)=Ppair(x^2)+x*Pimpair(x^2) et xi^2 est une racine primitive n/2-ième de 1. Donc si n est une puissance de 2, le calcul de dft(P) se fait en O(n*ln(n)) opérations (algorithme de la fft).
2/ algorithmes fondementaux:
a/ PGCD, temps en O(n^2) pour entiers longs de taille n,
b/ identite de Bezout pour a>=b>0 a*u+b*v=pgcd(a,b) calcul de u et v avec u_0=1, u_1=0, v_0=0, v_1=1, r_0=a, r_1=b.
Pour verifier
a*u_n+b*v_n=r_n
on definit u_n et v_n par recurrence
u_(n+2)=u_n-q_n*u_(n+1)
v_(n+2)=v_n-q_n*v_(n+1)
ou r_(n+2)=r_n-q_n*u_(n+1)
On a par récurrence v_n*r_(n+1)-v_(n+1)*r_n=(-1)^n*a, et |v_n| strictement croissante, au cran apres Bezout, on a v_n*pgcd(a,b)=a d'ou la suite |v_n| est majoree par a et |v|<a. De meme on prouve que |u|<b.

Re: option C-2014/15

Publié : mer. sept. 24, 2014 5:35 pm
par parisse
24/9: TP
Programmation du PGCD avec reste euclidien (irem) ou reste symétrique (smod), le 2ème nécessitant moins d'itérations, car la valeur absolue du reste est divisée au moins par 2 (au lieu du nombre d'or).
Programmation de Bézout itératif. Inverse modulaire, on peut économiser le calcul des v_n, la récurrence sur les u_n ne dépend que des r_n. Restes chinois (on peut aussi économiser une des récurrences).
Décompte du nombre de quotients égaux à 1, 2 ou 3 dans l'algorithme d'Euclide, et comparaison de la proportion empirique avec l'asymptotique pour N grand si a et b sont pris au hasard entre 1 et N (cf. Knuth, volume 2, la proportion de quotients egaux à q tend vers log2((a+1)^2/((a+1)^2-1))).

Re: option C-2014/15

Publié : mer. oct. 01, 2014 2:09 pm
par parisse
1/10: suite de Bezout
autre methode iterative pour Bezout avec a*u_n-b*v_n=(-1)^n*r_n, les suites u_n et v_n verifient u_{n+2}=u_n+q_n*u_{n+1} et v_{n+2}=v_n+q_n*v_{n+1}, et sont donc positives, et on a la relation u_n*r_{n+1}+u_{n+1}*r_n=b et v_n*r_{n+1}+v_{n+1}*r_n=a.
Lien avec la decomposition en fraction continue de a/b=[q0,...,q_{N-1}], l'avant-derniere reduite [q0,...,q_{N-2}]=v_N/u_N ou u_N et v_N sont les coefficients de Bezout de a et b definis comme ci-dessus. On montre pour cela par recurrence que
[q0,...,q_{n-1},x]=(v_n+x*v_{n+1})/(u_n+x*u_{n+1})
et on fait x=q_n et n=N-2
Applications: inverse modulaire, restes chinois.
Reconstruction rationnelle de a/b donné par q mod p (a=b*q mod p)
S'il existe un rationnel a/b tel que a/b=q mod p tel que |a|<sqrt(p)/2 et 1<=b<sqrt(p)/2, si a'/b' est un autre rationnel tel que a'/b'=q mod p, |a'|<=sqrt(p) et 1<=b'<=sqrt(p), alors a/b=a'/b'. De plus a/b est déterminé par l'algorithme de Bézout appliqué à q et p, avec arrêt au 1er rang n tel que r_n<=p (b=u_n et a=(-1)^n*r_n).

* puissance modulaire rapide, algorithme récursif et itératif, le calcul de a^n mod p se fait en log2(n) etapes necessitant chacune 1 ou 2 multiplications et 1 division d'entiers <p^3 (O(ln(p)^2) operations par des methodes naives).
Applications
1/ test de Miller-Rabin. Complexité en O(ln(p)^3) si on multiplie les entiers naivement.

Re: option C-2014/15

Publié : mer. oct. 08, 2014 6:02 pm
par parisse
8/10: TP, exercice sur le temps de calcul du produit de 2 entiers ou 2 polynômes, exercice sur la puissance modulaire rapide powmod(a,n,m) vs irem(a^n,m). Programmation de la puissance rapide.

Re: option C-2014/15

Publié : mer. oct. 15, 2014 2:32 pm
par parisse
15/10:
Racine carre modulo p, cas ou p=1 [4] par calcul de gcd(x^2-a,(x+r)^(p-1)/2-1) mod p avec r aleatoire.
Racine carree entiere de a par l'algorithme de soustraction d'impairs consecutifs, en O(n^2) si n est le nombre de chiffres de a.

Representation des objets mathematiques sur machine, suite
* entier modulo n: représentation symétrique dans ]-n/2,n/2]
* flottants m*b^e ou b=base (en général 2 ou 10), mantisse m, exposant e. Dans Xcas, si Digits>14 on utilise des flottants multiprécision (m entier long de taille fixée paramétrée par Digits), sinon des flottants "double". Erreur relative d'arrondi, absolue, propagation des erreurs. Artihmetique d'intervalles.
* rationnels: couple d'entiers
* complexes: couple des précédents
* polynomes à 1 variable: représentation dense par la liste des coefficients (par ordre décroissant dans Xcas). Representation creuse (par ex. pour x^1000-1).
* polynome à plusieurs variables, représentation creuse, ordre des monomes (ex. ordre lexicographique), multiplication en O(n*m*ln(taille du produit)), discussion sur la densité (formule comb(n+d,n) pour le nombre de monomes possibles d'un polynome de degre total d en n variables)
* variable affectee ou non (valeur, hypothese, purge).

Re: option C-2014/15

Publié : jeu. oct. 23, 2014 5:46 pm
par parisse
22/10:
TP:
Programmation de la méthode de Horner, et du changement d'origine pour Taylor.
Suite de la feuille de TP http://www-fourier.ujf-grenoble.fr/~par ... regtp1.pdf

Re: option C-2014/15

Publié : mer. nov. 05, 2014 7:32 pm
par parisse
29/10: vacances

5/11:
* expression symbolique, evaluation. Niveau d'évaluation (nombre de remplacements récursifs d'un nom de variable par une expression qu'on évalue). Par défaut 25 en mode interactif, 1 en programme. Empêcher l'évaluation, quote. Quote implicite dans certaines instructions comme := pour le membre de gauche, et le membre de droite dans une définition de fonction/programme.
Différence expression/fonction, passage d'une expression à une fonction par unapply. subst pour substituer dans une expression.
* liste/vecteurs, liste de listes de meme taille=matrice
Affectation := remplacement de la liste en temps O(taille de la liste), =< affectation en place en temps O(1).
* autres types : sequences (pas de profondeur), tables, attention aux tables vs listes,

Extension algébrique et corps fini: couple de polynômes A, B irréductible sur Q (extension algébrique) ou Z/pZ (corps fini) pour A(alpha) avec B(alpha)=0 (notation rootof de xcas pour les extensions algébriques).
Construction d'un corps fini.
-> démonstration de la formule X^(p^n)-X=produit des irreductibles de degré divisant n modulo p.
Dans un sens, on utilise que si A est irréductible de degré k, alors Z/pZ[X]/A est un corps ayant p^k éléments donc alpha^p^k=alpha pour tout alpha dans le corps, d'où on déduit que X^p^k-X est divisible par A, et X^p^k=X mod A entraint X^p^n=X mod A en réitérant "prendre à la puissance p^k" n/k fois.
Dans l'autre sens on utilise Bézout sur le degré k de A et n:
k*u=pgcd(n,k)+n*v
X^(p^(k*u))=X^(p^(n*v+pgcd(n,k)))
on en déduit que X^p^pgcd(n,k)=X mod A et cela entraine que pgcd(n,k)=k sinon il y a trop de racines pour X^p^pgcd(n,k)=X dans le corps Z/pZ[X]/A
-> on en déduit une majoration du nombre de polynôme irréductibles de degré n, puis une minoration, en raisonnant sur les degrés. Pour p pas trop petit, on a environ une chance sur n de tomber sur un irréductible en prenant un unitaire de degré n à coefficients aléatoires.
-> Déf. de polynôme irréductible primitif: X doit engendrer le groupe cyclique K*. Pour en construire un, on part d'un élément cyclique d'un corps fini et on calcule son polynôme minimal.
Il y a euler_phi(card(K*)) éléments cycliques dans K*, si card(K*)=p^n-1=produit des p_i^r_i, la proba de tomber sur un cyclique est produit(1-1/p_i)
-> Représentation multiplicative (on prend l'exposant entier d'un générateur fixé, et -1 ou p^n-1 pour 0 de K), adaptée à * et inverse rapides, mais il faut une table pour repasser en représentation additive pour faire + et -. Exemple petits corps fini, en particulier de caractéristique 2 où + et - sont un ou exclusif sur des entiers (représentant des polynômes, en écrivant l'entier en base 2, les bits sont les coefficients du polynôme), et la construction de table est très rapide, pour avoir le représentant additif de X^(j+1)=X^j*X on décale d'un cran le réprésentant additif de X^j, on regarde s'il a un terme de degré X^n si oui on fait le ou exclusif avec l'entier représentant le polynôme irréductible primitif en base 2.

-> Chapitre 2: PGCD, Bezout, résultant.
Début:
Polynome sur Z[X]: déf. de contenu (pgcd des coeffs entiers), partie primitive (une fois divisé par le contenu)
Proposition: Le produit de 2 polynômes primitifs est primitif. Si A et B sont primitifs et B divise A dans Q[X] alors il divise A dans Z[X].
Définition du pgcd de 2 polynomes primitifs dans Z[X], on prend un pgcd dans Q[X], on multiplie par le ppcm des dénominateurs, on prend la partie primitive, on change de signe si le coeff dominant est négatif. Unicité car si A et B sont primitifs et multiples dans Q[X], alors le coeff multiplicateur est un entier inversible donc est 1 ou -1.

Re: option C-2014/15

Publié : jeu. nov. 13, 2014 7:11 pm
par parisse
12/11: TP sur les corps finis:
-> Trouver un polynome irréductible P de degré 5 sur Z/7Z. En deduire une representation de GF(7,5). Factoriser le polynome P sur votre representation de GF(7,5) (on pourra utiliser l'application x -> x^7).
-> Determiner le polynome minimal de quelques elements de GF(7,5) en utilisant votre representation ou celle de Xcas. Meme question mais en degre 4 avec la représentation de Xcas.

Re: option C-2014/15

Publié : jeu. nov. 20, 2014 7:10 pm
par parisse
19/11: Minis-exposés d'entrainement de 20-25min par 4 étudiants, sur les thèmes:
* écriture en base b
* PGCD d'entiers
* test de primalité
* extension algébrique

Re: option C-2014/15

Publié : mer. nov. 26, 2014 5:58 pm
par parisse
26/11: mini-exposés (suite et fin)
* déterminant sur Z par une méthode modulaire
* représentations efficaces de GF(2,8)
* division euclidienne (dans Z)
* écriture en base b

Re: option C-2014/15

Publié : mer. déc. 03, 2014 3:24 pm
par parisse
3/12:
PGCD suite et resultant debut
Proposition: si p est un premier ne divisant pas le pgcd des coeff dominants de A et B, le degré du pgcd dans Z/pZ[X] est >= à celui dans Z[X]. En particulier si le degré dans Z/pZ[X] est nul, les polynômes sont premiers entre eux dans Z[X].
Idee de l'algorithme de PGCD modulaire:
Si le degre du pgcd modulo p est nul, on conclut. Sinon, il faut reconstruire un multiple entier connu du pgcd, on prend le multiple de lcoeff g=le pgcd des coefficients de A et B. On normalise le pgcd mod p pour avoir lcoeff=g. Si p est assez grand et de bonne réduction, alors le pgcd dans Z est le reconstruit symétrique du pgcd modulo p. Pour tester on vérifie que le reconstruit symétrique divise A et B dans Z[X]

Estimation sur les racines complexes d'un polynome P a coefficients complexes:
|z| < 1+max(abs(coeffs de P))/abs(lcoeff(P))
On en déduit une majoration des coefficients du PGCD de A et B en développant son écriture factorisée et en utilisant que les racines du PGCD sont racines communes de A et B.

Complexité de l'algorithme modulaire en O(deg(A)^3) dans le cas le pire (grand degré de PGCD), la plupart du temps c'est en O(deg(A)^2) (si degré du pgcd est nul ou petit).

Définition du résultant par l'identité de Bézout:
C'est le déterminant du système
A*U+B*V=C
où A, B, C donnés, U et V inconnus (coefficients dans un anneau intègre unitaire commutatif inclus dans un corps, par exemple Z dans Q ou Z[Y,Z,T...] dans le corps des fractions en Y,Z,T...), degré(U)<degré(B) et degré(V)<degré(A) et degré(C)<degré(A)+degré(B).
Prop: resultant(A,B)=0 si et seulement si A et B ne sont pas premiers entre eux.
Exemple: discriminant(A)=resultant(A,A')/lcoeff(A) exemple en degre 2 et 3.
Observation: si A et B sont premiers entre eux et si les coefficients de C sont multiples du résultant alors U et V ont leurs coefficients dans l'anneau.

Preuve: par les formules de Cramer.
Conséquence: si A(X,Y,Z,...) et B(X,Y,Z,...) s'annulent en x,y,z,... alors resultant en X de A,B s'annule en y,z,...
Application: résolution d'un système polynomial 2x2 puis de n équations à n inconnues, on prend le résultant 2 à 2 par rapport à Xn de (P1, Pn), de (P2, Pn), etc. (Pn-1,Pn) on obtient un système polynomial de n-1 équations à n-1 inconnues (si les polynomes sont premiers entre eux, cas générique), etc. jusqu'à se ramener à une équation polynomiale en 1 inconnue, dont on peut calculer les solutions (éventuellement de manière approchée), puis on revient au système précédent: 2 équations en 2 inconnues, on remplace X1 par une des racines on prend le PGCD des 2 polynomes en la variable restante, on cherche les racines, etc.
Recherche d'une equation cartesienne pour une courbe parametrique rationnelle.

Lien avec les racines (sans demonstration complete) resultant(A,B)=lcoeff(A)^b*lcoeff(B)^a*produit differences racines de A et B et discriminant(A)=lcoeff(A)^(2*deg(A)-2)*produit differences de paires ordonnnees de racines distinctes au carre.

Re: option C-2014/15

Publié : jeu. déc. 11, 2014 6:36 pm
par parisse
10/12: TP. Section 6 PGCD/résultants exercices de Aide>Manuels>Algorithmes
Exercices 6.2.1 et 6.2.2 de PGCD et 6.3.1 et 6.3.2 de résultants

Re: option C-2014/15

Publié : mer. déc. 17, 2014 7:24 pm
par parisse
17 et 18/12: 1ers oraux blancs, choix entre les textes
* Moyenne arithmetico-geometrique et application au calcul d'integrales elliptiques.
* Le modèle du calcul flottant.

Conseils: attention a ne pas paraphraser le texte, il n'est pas necessaire de parler de tout, on peut faire un ou plusieurs developpements mathematiques dans les suggestions (souvent il s'agira de completer une preuve esquissee dans le texte). Presenter en 1 minute ou 2 un plan en debut (I, II, III...) et indiquer ou il y aura des illustrations informatiques.
S'attendre a se voir poser des questions sur la complexite des programmes des illustrations s'il y en a et si on n'en a pas parle soi-meme. Il n'est pas indispensable qu'il y ait des programmes dans les illustrations, une utilisation judicieuse des instructions du logiciel peut tres bien suffire, et c'est ce qu'on a souvent interet a faire avant d'avoir les parties mathematiques de l'expose bien au point, en particulier ne pas perdre trop de temps a mettre au point un programme, si ca ne marche toujours pas en 5 minutes avec debug() laissez le programme en l'etat, le jury vous aidera eventuellement a le corriger lors du passage.
En temps limite, il peut arriver que vous passiez completement a cote du texte (certains textes sont difficiles). Essayez alors de faire quand meme un expose mettant en valeur les connaissances au programme en vous raccrochant le plus possible au theme du texte.

Sur la moyenne arithmético-géométrique, on peut montrer que les suites sont adjacentes, montrer une estimation a priori sur |a_n-b_n|<=constante^(2^n-1)*|a_0-b_0|^(2^n), et en deduire la complexite du calcul de la moyenne arithmetico-geometrique avec k digits. On peut comparer la complexite avec celle qui serait issue d'une quadrature usuelle (avec romberg ou gaussquad dans Xcas). Sur les parametrisations, on peut montrer que toute conique admet un parametrage rationnel en utilisant une droite passant par un point de la conique de pente m et l'autre point d'intersection, et expliquer comment on peut ainsi calculer les integrales de racines carrees de fraction rationnelles en x et en un polynome du second degre en x (sans utiliser des sin/cos, sinh/cosh mais en se ramenant directement a des fractions rationnelles). On peut effectuer comme suggere par le texte certains des calculs algebriques avec Xcas. On peut enfin exposer le paragraphe qui explique pourquoi une cubique ne peut pas se parametrer rationnellement.
http://www-fourier.ujf-grenoble.fr/~par ... _agreg.xws
La documentation de Xcas contient un paragraphe sur l'utilisation de la moyenne arithmético-géométrique pour calculer les fonctions élémentaires en multi-précision.

Sur les flottants, on peut représenter les flottants du texte pour une petite plage d'exposants (par ex. [-2,2]) et 2 ou 3 bits de mantisse, ça peut se faire graphiquement d'ailleurs (avec l'instruction point) pour faire apparaitre le motif pour un exposant et les homothéties en changeant d'exposant.
On peut écrire un programme qui calcule le signe, l'exposant et la mantisse pour un rationnel (avec une précision fixée).
On peut discuter la pertinence de chercher l'arrondi correct (qui est ici une troncature) dans le contexte de l'analyse numérique (indiqué au début du texte).
On peut expliquer comment faire + et * avec des opérations sur les entiers, donc sans se poser la question de gérer les mauvais cas.
On peut suivre les (autres) suggestions du texte (démonstration du lemme de la page 2, construction de mauvais cas...).

Re: option C-2014/15

Publié : jeu. janv. 15, 2015 7:48 pm
par parisse
13/1:
Proposition: si A et B sont de degré total a et b, partiel par rapport à X n et m alors le degré total du résultant par rapport à X de A et B est <= a*b, en fait il est <= a*b-(a-n)*(b-m), il y a égalité si les polynômes sont homogènes (si le résultant est non nul).
Preuve par développement du déterminant avec les permutations.

Conséquence: théorème de Bézout sur le nombre d'intersection de 2 courbes algébriques sans composante commune, ce nombre est inférieur au produit des 2 degrés des polynomes équations des 2 courbes.
Preuve en 2 étapes: on commence à montrer que le nombre est fini, puis on change de repère par rotation pour que 2 racines distinctes n'aient jamais la même projection sur Ox, et on applique la proposition sur le degré du résultant.

Exemples: intersection de x*y=4 ou (x-2)^2+y^2=4 et de y^2=(x-3)*(x^2-16), qui met en évidence comment on peut perdre des points d'intersection par rapport au produit des degrés des 2 courbes:
* points à coordonnées complexes et les points d'intersection ayant une multiplicité (se traduit par une tangence des courbes au point d'intersection), cas du cercle inter la cubique
* point à l'infini: (0,1,0) pour l'hyperbole inter la cubique:
Si on fait le résultant en x ou en y en coordonnées "normales", on a un résultant de degré 5 et non 6. En coordonnées homogènes, le résultant est de degré 5 en y et 6 en x (correspond à a*b-(a-n)*(b-m) pour a=2, b=3 et n=1,m=2 ou n=1 et m=3), avec un coefficient en y^6 nul pour le résultant en x de x*y-4t^2 et de y^2*t-(x-3t)*(x^2-16t^2), donc t=0 est racine du résultant. Le point à l'infini se trouve en posant t=0 donc x*y-4t^2=0 devient x*y=0 et y^2*t-(x-3t)*(x^2-16t^2) devient x^3=0 d'où x=0, d'où (0,y,0)=y(0,1,0) est dans l'intersection.

Autres exemples d'utilisation du resultant
-> Integration de fractions rationnelles:
etape 0: on se ramene a une fraction propre (degre numerateur<degre denominateur), la partie entiere de la fraction s'integre facilement (polynome)
etape 1: factorisation squarefree (par l'algorithme de Yun) puis decomposition en elements simples selon cette factorisation par Bezout -> on se ramene a integrer A/B^i, B sans racine multiple
etape 2: si i>1 on fait Bezout pour A=U*B+V*B' et on integre par parties V*B'/B^i, ceci permet de se ramener a une fraction A/B
etape 3: int(A/B)=somme([racines en t du resultant(B(x),A(x)-t*B'(x),x)]*ln(gcd(B,A-t*B'))
On montre que le coefficient de la decomposition en elements simples de 1/(x-z) est A/B'(z) pour z racine de B, c'est donc le coefficient du ln(x-z) correspondant. On regroupe ensuite les ln correspondant au meme coefficient. Les coefficients possibles sont bien racines du resultant puisque z est racine commune de B(x) et A(x)-(A/B')(z)*B(x), et l'ensemble des racines correspondant au meme coefficient de ln va donner le facteur ln(gcd(B,A-t*B')) apres regroupement.
-> Extensions algebriques Q[alpha,beta]: exemple ecrire Q[sqrt(2),sqrt(3)] comme un Q[gamma]
On suppose que le polynome minimal de beta sur Q est encore irreductible sur Q[alpha], par ex. x^2-3 est irreductible sur Q[sqrt(2)]. Alors l'extension est de degre le produit des degres. On peut chercher un generateur sous la forme alpha+k*beta avec k entier, par exemple k=1, on cherche donc gamma=alpha+beta. On a A(alpha)=0 et B(beta)=0 donc B(gamma-alpha)=0, on elimine alpha en prenant resultant(A(x),B(gamma-x),x) qui s'annule car alpha est racine commune. On factorise le resultant, s'il est irreductible et du bon degre (cas generique), c'est le polynome minimal de gamma et Q[gamma]=Q[alpha,beta]

Algorithme de Yun pour écrire un polynôme comme produit de puissances de polynômes sans facteur carré et premiers entre eux, présenté si les coefficients sont dans un corps de caractéristique 0.

Localisation des racines réelles d'un polynôme.
Suites de Sturm pour P polynome à coeff réels sans racines multiples on pose
R_0=P, R_1=P', R_{n+2}=-rem(R_n,R_ {n+1}), ..., R_N=dernier reste non nul (constant)
Alors le nombre de racines de P sur ]a,b] est la différence entre s(P,a) et s(P,b) où s(P,x) est le nombre de changements de signe de R_n(x) en ignorant les 0.
Corollaire: localisation à epsilon près des racines réelles, on commence par compter le nombre de racines dans [-M,M], si c'est 0 c'est fini, si c'est 1 on passe à la dichotomie usuelle, sinon on coupe en 2 et on recommence sur chaque intervalle de longueur moitié.
Nombre d'opérations: O(deg(P)) pour calculer S(P,x) en x (en utilisant la récurrence pour évaluer R_n(x) en fonction des 2 précédents)