Savoir si un nombre est un carré parfait
dans Arithmétique
Bonjour,
Connaissez-vous la méthode la plus rapide pour savoir si un nombre est un carré parfait (sans calculer sa racine) ?
Merci.
Cordialement.
Connaissez-vous la méthode la plus rapide pour savoir si un nombre est un carré parfait (sans calculer sa racine) ?
Merci.
Cordialement.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
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.
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$.
C'est très rapide.
Merci (:P)
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.]
Si $n$ est premier on a des outils pour savoir si un nombre est un carré modulo un nombre premier.
Cela permet d'élaguer.
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.
Si c’est oui, tu passes à la ligne suivante.
-- Schnoebelen, Philippe
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.
verifie s'il s'ecrie sous forme des sommes des entiers impaires,
1+3+5+7+9+11.........
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
mais je n'ai pas trouvé l'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.
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
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.
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 ? [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]
Côté temps, Sage fait à peu près pareil
Amicalement,
Aurel
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-)) :
et si vous vous demandez ce que c'est que ulong, c'est juste un alias pour unsigned long :
Amicalement,
Aurel
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.
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à ?
Tu veux dire pour ceux qui ne sauraient pas que tu sais qu'il sait ?
amicalement,
e.v.