Savoir si un nombre est un carré parfait

fredrick · March 2015

Bonjour,

Connaissez-vous la méthode la plus rapide pour savoir si un nombre est un carré parfait (sans calculer sa racine) ?
Merci.

Cordialement.

jacquot · March 2015

Pas forcément plus rapide, il y a la décomposition en produit de facteurs premiers, chaque facteur devant alors apparaître à une puissance paire.

fredrick · March 2015

En fait j'ai un polynôme, et je voudrais tester pour chaques valeurs de $x$ si le résultat est un carré parfait ou non. J'ai vu qu'on pouvait déjà tester le dernier chiffre du nombre, si il se termine par 2, 3, 7 ou 8 ce n'est pas un carré parfait, ça permet d'en exclure déjà pas mal.
Après si le nombre se termine par 4, le nombre précédent doit être plus grand, et s'il se termine par 6 le nombre précédent doit être plus petit.

Après, une fois ces tests effectués, je peux essayer la décomposition en facteur premier, mais il doit exister des façons plus rapides.

JLT · March 2015

Pourtant, calculer une valeur approchée de sa racine (avec une erreur strictement plus petite que 1/2) est ce qu'il y a de plus rapide.

Soit $x$ tel que $|x-\sqrt{n}|<1$. Soit $m$ l'entier le plus proche de $x$. Alors $n$ est un carré si et seulement si $n=m^2$.

Siméon · March 2015

Dans la même veine que JLT, avec la méthode de Newton entière :

def est_un_carre(x):
    y = 1
    while True:
        z = y
        y = (y**2 + x)/(2*y)
        if abs(y - z) < 2: break
    return (y**2 == x)

(code Python)

C'est très rapide.

fredrick · March 2015

Ok, je vais adapter cette fonction en c et faire différent test.
Merci (:P)

Jer anonyme · March 2015

Il y a mieux, voir le Course in computational algebraic number theory d'Henri Cohen.

L'idée est de réduire modulo 11, 63, 64 et 65, nombres pour lesquels on calcule une fois pour toutes les résidus quadratiques -- c'est a priori plus rapide que de calculer la racine carrée. Pour un grand nombre de $n$ à tester, cela permet de diviser par un peu plus de 100 le nombre de racines carrées à calculer complètement car la proportion (densité) de résidus quadratiques modulo $64\times63\times65\times11$ est $6/715$.

Mieux encore (algorithme 1.7.3, op. cit.) : pour tester si $n$ est un carré :
-- voir si $n\pmod{64}$ est un carré : si ce n'est pas le cas, terminé ; si oui, poser $r=n\pmod{45045}$ ;
-- voir si $r\pmod{63}$ est un carré ; si non, terminé, si oui, passer à la ligne suivante ;
-- voir si $r\pmod{65}$ est un carré ; si non, terminé, si oui, passer à la ligne suivante ;
-- voir si $r\pmod{11}$ est un carré ; si non, terminé, si oui, passer à la ligne suivante ;
-- calculer la « racine carrée par défaut » $q$ de $n$ (c'est-à-dire telle que $q^2\le n<(q+1)^2$ et $q^2$) et voir si $q^2=n$.

Pour calculer la « racine carrée par défaut » de $n$ :
-- poser $x=n$ ;
-- poser $y = \left\lfloor\dfrac{x+\lfloor{n/x}\rfloor}2\right\rfloor$ ;
-- si $y<x$, poser $x=y$ et reprendre au pas précédent ; sinon, renvoyer $x$.

[Edit : ajout de quelques détails.]

Fin de partie · March 2015

Puisque $x=a^2$ on en déduit que $x\equiv a^2\mod{n}$ , $n>0$ un entier naturel.
Si $n$ est premier on a des outils pour savoir si un nombre est un carré modulo un nombre premier.
Cela permet d'élaguer.

fredrick · March 2015

Jer anonyme,
Je voudrais implémenter l'algorythme 1.7.3, est-ce que tu pourrais le détailler un peu plus car il y a plusieurs points que je n'arrives pas à comprendre ?
Par exemple qu'est ce que je fais après si r(mod63) est un carré ?

J'aimerai bien comprendre aussi pourquoi ça marche ?

Merci.

nicolas.patrois · March 2015

Si c’est non, tu retournes Faux.
Si c’est oui, tu passes à la ligne suivante.

Jer anonyme · March 2015

J'ai modifié mon message pour intégrer ce que Nicolas Patrois a écrit, qui était (un peu trop ?) sous-entendu.

La raison pour laquelle ça marche a été donnée par FdP : si $n$ est un carré, alors le reste de la division de $n$ par $a$ est un carré modulo $a$ pour tout $a$. On fait quatre tests très rapides : pour $709/715$ des nombres testés, ces tests permettront de conclure que $n$ n'est pas un carré. Sinon, on calcule la racine carrée par défaut (variante de l'algorithme de Newton qui a été mentionné par Siméon) et on teste.

Pourquoi $709/715$ ? C'est la proportion d'entiers compris entre $1$ et $11\times63\times64\times65$ qui ne sont pas des carrés pour au moins un des nombres $11$, etc.

Pourquoi est-ce qu'on gagne (en moyenne) ? Parce qu'il est plus rapide de calculer les restes et faire les tests modulo ces petits nombres que de calculer la racine carrée et qu'assez souvent, ça suffit.

Au fait, je ne fais que paraphraser Henri Cohen, bien sûr. NB : je suppose que ce sont des algorithmes implémentés dans Pari/GP.

fredrick · March 2015

Ok, merci pour vos réponses, je vais étudier ça.

Mehdi Pascal · April 2015

salut
verifie s'il s'ecrie sous forme des sommes des entiers impaires,
1+3+5+7+9+11.........

Jer anonyme · April 2015

Ça, ça va être super efficace !

ngarnier54 · June 2020

Bonjour
quelqu'un un a-t-il programmé cet algo de "Jer anonyme" en c# cela me rendrait service.
Sinon j'ai tenté de mettre en c# méthode de Newton entière mais ça ne marche pas.
Merci de votre aide

private Boolean carreparfaitNT(double x)
        {           
            double y =1;
            double z =1;
            Boolean a = true;

            while (a==true)
            {
                z = y;
                y = ((Math.Pow(y, 2) + x ) / (2 * y));

                if (Math.Abs(y - z) < 2)
                {
                    a = false;
                }
            }

            if (y*y == x)
            {
                return true;
            }
            else
            {
                return false;
            }                            
        }

claude quitté · June 2020

Cf les posts autour de http://www.les-mathematiques.net/phorum/read.php?5,1809582,1809602#msg-1809602. Il y a un pdf attaché à mon post.

ngarnier54 · June 2020

Merci
mais je n'ai pas trouvé l'algorithme.

claude quitté · June 2020

Tu dois confondre algorithme et programme écrit dans un CERTAIN langage de programmation. L'avantage d'un algorithme, c'est qu'on peut le traduire dans le langage de son CHOIX. J'attache un extrait de la page 2 de la petite note pour te montrer qu'elle contient bien un algorithme.

Et j'ajoute que cette note contient tout ce qu'il faut pour implémenter le calcul de la racine carrée entière (nous l'avons déjà réalisé dans plusieurs langages différents, NO PROBLEMO).

Si tu veux vraiment un programme en C, il y a la rubrique Informatique sur ce forum. Car cela n'a rien à voir avec l'arithmétique. En passant, la locution ``... ne marche pas'' en programmation ne signifie pas grand chose. 104510

franckfranck · June 2020

si le chiffre des unités est égal à 2, 3 , 7 , 8 tu es sûr que le nombre n'est pas un carré parfait

ngarnier54 · June 2020

oui car

0**2 = 0
1**2 = 1
2**2 = 4
3**2 = 9
4**2 = 16
5**2 = 25
6**2 = 36
7**2 = 49
8**2 = 64
9**2 = 81

donc un carre parfait se termine forcement par 1 4 9 6 5 0

j'ai fait une fonction carre parfait en c# ce marche bien

ev · June 2020

Bonjour ngarnier54.

Tu pouvais t'arrêter à 5**2.

Il n'est pas clair que le calcul des congruences modulo 10 soit plus facile en machine que les congruences modulo 64, 63 ou 65.
Il reste les congruences modulo 11 de Jer.

e.v.

ngarnier54 · June 2020

Voilà ma fonction en c#, elle marche bien.
Pour les nombres de 1 à 1000000, elle trouve les 1002 carrés parfaits en 2s.
J 'ai récupéré les filtres par modulo d'un autre programme (on peut sans doute faire mieux dans les filtres).
Je suis preneur de toute améliorations !
Qui dit mieux ?

private Boolean carreparfaitbon(ulong N)
        {
            decimal NN = N;
                ulong c = N % 10;

                if (c == 3 | c == 7 | c == 2 | c == 8)
                    return false;

                if (c == 5)
                {
                    if ((Math.Truncate(NN / 10) % 10) != 2)
                        return false;

                    decimal aa = Math.Truncate(NN / 100) % 10;

                    if (aa == 1 | aa == 3 | aa == 4 | aa == 5 | aa == 7 | aa == 8 | aa == 9)
                        return false;

                    if (aa == 6)
                    {
                        aa = (Math.Truncate(NN / 1000) % 10);
                        if (aa == 1 | aa ==2 | aa ==3 | aa == 4 | aa == 6 | aa == 7 | aa == 8| aa == 9)
                            return false;
                    }               
                }
                 
            c = N % 7;
                if (c == 3 | c == 5 | c == 6)
                    return false;

                c = N % 9;
                if (c == 2 | c == 3 | c == 5 | c == 6 | c == 8)
                    return false;

                c = N % 13;
                if (c == 2 | c == 5 | c == 6 | c == 7 | c == 8 | c == 11)
                    return false;

                ulong x = N;
                ulong y = 1;
                Boolean lastY = true;

            while (lastY == true)          
                {                
                y = (x + (N/x)) >> 1;

                if (y < x)
                {
                    x = y;
                }
                else
                {
                    lastY = false;
                }
            }
         
            if (x*x  == N )
            {
                return true;
            }
            else
            {
                return false;            
            }
        }

[Pour afficher l'indentation, [b]IL FAUT[/b] utiliser le [b]bouton "Code"[/b] (5ème par la droite au dessus de la fenêtre d'édition. AD]

Math Coss · June 2020

Euh... Comment pourrait-il y avoir $1002$ carrés parfaits entre $1$ (ou même $0$) et $1000^2$ ?

Côté temps, Sage fait à peu près pareil

sage: time L = [k for k in range(1000000+1) if is_square(k)]
CPU times: user 2.31 s, sys: 10.4 ms, total: 2.32 s
Wall time: 2.29 s
sage: len(L)
1001

aurelpage · June 2020

En pari/gp...

? L = [i | i <- [1..10^6], issquare(i)];
cpu time = 196 ms, real time = 198 ms.

Amicalement,
Aurel

Math Coss · June 2020

C'est (dix fois) mieux ! Voici ce que donne la commande pari/gp invoquée par Sage...

sage: time L = pari("[i | i <- [0..10^6], issquare(i)]")
CPU times: user 89.5 ms, sys: 100 µs, total: 89.6 ms
Wall time: 89.7 ms
sage: len(L)
1001

aurelpage · June 2020

Haha, tu dois avoir un ordi deux fois plus rapide que le mien !

Le code de pari utilise les mêmes idées que mentionnées ci-dessus (notez aussi le subtil mélange de français et d'anglais dans le code, c'est beau B-)) :

static int
carremod(ulong A)
{
  const int carresmod64[]={
    1,1,0,0,1,0,0,0,0,1, 0,0,0,0,0,0,1,1,0,0, 0,0,0,0,0,1,0,0,0,0,
    0,0,0,1,0,0,1,0,0,0, 0,1,0,0,0,0,0,0,0,1, 0,0,0,0,0,0,0,1,0,0, 0,0,0,0};
  const int carresmod63[]={
    1,1,0,0,1,0,0,1,0,1, 0,0,0,0,0,0,1,0,1,0, 0,0,1,0,0,1,0,0,1,0,
    0,0,0,0,0,0,1,1,0,0, 0,0,0,1,0,0,1,0,0,1, 0,0,0,0,0,0,0,0,1,0, 0,0,0};
  const int carresmod65[]={
    1,1,0,0,1,0,0,0,0,1, 1,0,0,0,1,0,1,0,0,0, 0,0,0,0,0,1,1,0,0,1,
    1,0,0,0,0,1,1,0,0,1, 1,0,0,0,0,0,0,0,0,1, 0,1,0,0,0,1,1,0,0,0, 0,1,0,0,1};
  const int carresmod11[]={1,1,0,1,1,1,0,0,0,1, 0};
  return (carresmod64[A & 0x3fUL]
    && carresmod63[A % 63UL]
    && carresmod65[A % 65UL]
    && carresmod11[A % 11UL]);
}

/* sqrt()'s result may be off by 1 when a is not representable exactly as a
 * double [64bit machine] */
ulong
usqrt(ulong a)
{
  ulong x = (ulong)sqrt((double)a);
#ifdef LONG_IS_64BIT
  if (x > LOWMASK || x*x > a) x--;
#endif
  return x;
} 

long
uissquare(ulong A)
{
  if (!A) return 1;
  if (carremod(A))
  {
    ulong a = usqrt(A);
    if (a * a == A) return 1;
  }
  return 0;
}

et si vous vous demandez ce que c'est que ulong, c'est juste un alias pour unsigned long :

#ifdef _WIN64
typedef unsigned long long pari_ulong;
#define long long long 
#define labs llabs
#else
typedef unsigned long pari_ulong;
#endif
#define ulong pari_ulong

Amicalement,
Aurel

ngarnier54 · June 2020

Merci pour vos commentaires,
j’aurais aimé une aide pour améliorer le code (en vitesse) juste pour le fun !

Il y a bien 1001 carrés parfaits entre 0 et 1 000 000 (pas 1002).

nicolas.

marco · June 2020

On peut aussi écrire ce programme pour les entiers supérieurs ou égaux à $1$. Il doit être lent.

#include <iostream>
using namespace std;

bool estcarre(int n) {
  int d=2;
  while(d*d<=n) {
    if(n%d==0) {
      if(n%(d*d)!=0) {
	return false;
      }
      n=n/(d*d);
      d=2;
    }
    else {
      d++;
    }
  }
  if(n!=1) {
    return false;
  }
  return true;
}

int main() {
  int i,s;
  s=0;
  for(i=1;i<=1000000;i++) {
    if(estcarre(i)) {
      s++;
    }
  }
  cout<<s;
}

Alban_ · July 2020

Bonjour, je tombe un peu par hasard sur ce fil et je trouve la réponse de Jer anonyme tirée du Cohen assez rigolote (pour ma part, j'en serais resté tranquillement à la méthode proposée par JLT et Siméon qui me va parfaitement). Je dois dire que je n'ai pas vérifié la phrase "le nombre de racines carrées à calculer complètement car la proportion (densité) de résidus quadratiques modulo 64×63×65×11 est 6/715" car je vois comment faire s'il le fallait.

Mais une question me vient : pourquoi réduire modulo ces nombres ? J'imagine qu'il y a une histoire de compromis de vitesse entre "je réduis modulo ces 1500 nombres" et "je réduis modulo 1 seul nombre" mais je ne vois ni pourquoi on choisit 4 nombres ni pourquoi on choisit précisément ceux-là ?

Math Coss · July 2020

aurelpage a écrit:

Le code de pari utilise les mêmes idées que mentionnées ci-dessus.

Pas très étonnant vu que Pari/GP a été initié par Henri Cohen – ce que je sais que tu sais, c'est pour ceux qui ne sauraient pas.

ev · July 2020

@Math Coss.

Tu veux dire pour ceux qui ne sauraient pas que tu sais qu'il sait ?

amicalement,

e.v.

Savoir si un nombre est un carré parfait

Réponses

Bonjour!

Catégories

In this Discussion