Comment pouvons-nous déterminer efficacement si un grand nombre est un carré parfait ?

Au début du programme, effectuez un pré-filtrage pour accélérer l'opération et filtrer les nombres non carrés évidents, y compris les nombres négatifs, les nombres dont les 4 derniers chiffres sont 0 , et des nombres dont les 2 derniers chiffres répondent à certaines exigences. Le numéro de la condition (5 ou 8 en décimal). Pour 0, considérez-le comme un nombre carré.

Ensuite, utilisez des techniques bit à bit pour vérifier si le reste de modulo 255 = 3 = 3 5 17 est un nombre carré. Le tableau bad255 enregistre si chaque reste est un nombre carré. en haut de la table.

Pour les nombres qui passent le pré-filtre, divisez par toutes les puissances de 2 (de manière binaire) jusqu'à ce que le quotient soit impair.

La dernière étape consiste à approximer la racine carrée en utilisant une méthode similaire au lemme de Hensel. La boucle interne commence par une valeur initiale donnée par le tableau start, qui fournit une approximation de sqrt (mod 8192). Cette approximation est continuellement améliorée grâce à des calculs successifs, en utilisant des astuces au niveau du bit pour améliorer la vitesse.

La structure approximative de cette méthode est la suivante :

1. Pré-filtre pour supprimer les nombres non carrés évidents.
2. Vérifiez si le reste modulo 255 est un nombre carré.
3. Divisé par une puissance de 2.
4. Calculez approximativement les racines carrées en utilisant une variante du lemme de Hensel.

Il convient de noter que l'auteur de cet algorithme affirme qu'il fonctionne 35 % plus rapidement que les autres méthodes.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!