Inscription / Connexion Nouveau Sujet
carré parfait et algorithme
Bonjour
je vous propose l'exercice suivant :
Ecrire un algorithme dans le language de votre choix permetant de determiner le premier carré parfait inferieur ou égal à un entier n choisit dans N .
On a droit à quelles fonctions standard ?
Si les fonctions racine () et int() sont autorisées, c'est trop facile :
def f(x) :
a=int(sqrt(x))
return a*a
Si on interdit les 2 fonctions partie-entières et racines carrée, ou une de ces 2 fonctions, le challenge devient beaucoup plus intéressant.
- Exercice 1 : on interdit la fonction racine carrée.
On a droit uniquement aux 4 opérations courantes, et à la fonction partie entière.
Le Héron, je m'attendais à le voir apparaître.
Mais ce Newton-Raphson, je ne connais pas du tout.
Oui, ce n'est pas le challenge du siècle, mais c'est un peu plus difficile que la question initiale.
Le problème pour Héron et Newton-Raphson, c'est le coté itératif à faire un certain nombre de fois. Du coup, utilisation de for ou while mais alors le problème initial est trivial.
Newton-Raphson est un algorithme simple pour trouver un zéro d'une fonction de R->R.
Tu prends un point initial x(0)
Et par récurrence tu définis x(n+1) = x(n) - f(x(n))/f'(x(n))
Si tu choisis correctement x(0) ça converge quadratiquement vers un zéro de f.
Ici pour f on prendrait f(x) = x^2-n et comme valeur initiale x(0) = n.
Comme je le disais ça converge très vite, donc avec 100 itérations (ce qui prend moins d'un quart de seconde) on sera très proche de sqrt(n).
Vu qu'on veut la partie entière c'est de toute façon pas très grave si on pas immensément proche. A +0.5 près à suffit.
n │²
Et la version Newton-Raphson avec juste des entiers (division entière) marche très bien pour la racine carrée.
Même plus besoin de passer par des float (nombres à virgules)
Et la version Newton-Raphson avec juste des entiers (division entière) marche très bien pour la racine carrée.
Même plus besoin de passer par des float (nombres à virgules)
Effectivement ça va bien fonctionner mais je pense que ça mettra plus de temps à converger par rapport aux floats. Et les divisions entières utilisant rarement des instructions SIMD, les calculs eux-mêmes seront plus longs.
L'avantage des divisions entières, c'est qu'on ne se prend pas la tête avec des erreurs d'arrondi et des divisions euclidiennes.
Voici un petit code qui illustre cela.
Les valeurs hardcodées dans les for ont été éudiées pour ce N en particulier, mais je suppute que les floats restent plus rapides pour des N plus grands.
Ici je suis resté sur Newton-Raphson, mais peut être que la méthode de la sécante, bien que d'ordre inférieur(phi), sera plus rapide ici. Parce que
Cliquez pour afficher
Avec des divisions entières on a la même convergence qu'avec des floats.
Pour les SIMD, la division entière est la division par défaut pour deux entiers la plupart du temps.
A noter que python a déjà la méthode toute faite pour nous: 
Je suis étonné que tu aies besoin de 77 itérations, mais tu pars de n ce qui n'est pas une bonne approximation de la racine du tout.
En utilisant n >> (n.bit_length()>>1), j'obtiens la réponse en seulement 5 itérations pour le m que tu as utilisé.
def isqrt(n: int):
x = n >> (n.bit_length() >> 1)
while not (x * x <= n < (x + 1) * (x + 1)):
x = (x + n // x) >> 1
return x
24 = 5²-1 est le plus petit nombre tel que 2 itérations sont nécessaires
483 = 22²-1 est le plus petit nombre tel que 3 itérations sont nécessaires
506943 = 712²-1 est le plus petit nombre tel que 4 itérations sont nécessaires
Il n'y a pas de nombres en dessous de 100 000 000 qui nécessite plus de 4 itérations.
Annuler
connectez vous