L'estimation de la racine carrée

StackOverflow https://stackoverflow.com/questions/3722975

Question

Je suis en train d'écrire une application iPhone qui doit calculer la racine carrée d'un nombre d'environ 2000 fois tous les 1 / 30e de seconde. sqrt () fonctionne très bien sur un ordinateur, mais le taux de trame tombe à environ 10 FPS sur un iPhone ou iPad, et je l'ai déjà optimisé le reste du code. Je l'ai entendu dire que cela peut être accéléré de façon spectaculaire en estimant la racine carrée, mais je ne peux pas trouver un code pour ce faire. Je ne ai besoin d'un ou deux décimales de précision. Toutes les suggestions sur la façon de le faire, ou d'autres façons de accélérer les choses seraient appréciés.

Merci!

Était-ce utile?

La solution

Quelle est la précision que vous voulez votre estimation est? Si vous savez à quel point vous voulez que votre estimation soit au réel sqrt méthode de Newton est votre ami.

Savez-vous la plage de valeurs qui sont transmises à sqrt? Si oui, vous pouvez faire une table qui est précalculée au démarrage (ou même de lire à partir du disque au démarrage en fonction de ce qui se révèle être plus rapide). Trouver le plus proche de la table à votre entrée et vous obtenez votre estimation.

Autres conseils

Sauf si vous avez réellement besoin la racine carrée, comparer les valeurs au carré plutôt que les valeurs brutes et la racine carrée.

équerrage est beaucoup plus rapide (et plus précis) que de prendre une racine carrée, si vous ne comparaisons besoin. Ceci est la façon dont la plupart des jeux le font.

Savez-vous la plage de valeurs que vous essayez de trouver la racine carrée de? Disons que vous avez des valeurs allant de 0 à 10. Vous pouvez ensuite précalculer un tableau: 

sqrt_val[0] = 0;
sqrt_val[1] = 1;
sqrt_val[2] = // the sqrt of 2
...
sqrt_val[10] = // the sqrt of 10

Ensuite, lors de l'exécution, vous prenez le numéro que vous voulez que la racine carrée de, convertir en un entier (donc par exemple 3,123 devient 3) et l'utiliser comme un indice (3) pour rechercher la valeur précalculée.

Bien sûr, si vous voulez une résolution plus fine, vous pouvez simplement augmenter le nombre d'éléments dans votre tableau.

Tout d'abord, êtes-vous certain que la racine carrée est en fait le goulot d'étranglement? Avez-vous un profil? 2000 racines carrées tous les 1 / 30e de seconde est en fait pas tout ce que beaucoup, même sur un téléphone cellulaire. La documentation ARM cite 33 cycles pour une racine carrée simple précision et 60 cycles pour double précision; un processeur 600MHz peut faire 10 M racines carrées par seconde (plus si l'instruction est en pipeline du tout).

Si vous avez sélectionnés, et la racine carrée est vraiment le goulot d'étranglement, vous voulez utiliser l'instruction vrsqrte.f32 NEON. Cette instruction est assez rapide et vous donne les racines carrées approximatives réciproques de quatre nombres à virgule flottante en même temps. Vous pouvez ensuite utiliser l'instruction vmul.f32 pour obtenir des racines carrées approximatives (bien que pour de nombreuses utilisations l'inverse est plus utile que la racine carrée lui-même).

Peut-être que ceci est pour vous:
rapide inverse racine carrée
Si cette méthode ne fournit pas la précision nécessaire, il y a aussi beaucoup d'autres méthodes itératives où vous pouvez choisir plus ou moins précis entre vitesse et précision:
Méthode de calcul des racines carrées

Le changement le plus simple que vous pouvez faire sur un iPhone est d'utiliser sqrtf () au lieu de sqrt (). Un seul calcul flottant de précision est beaucoup plus rapide que la double précision, en particulier sur les appareils de vintage 3GS et plus récent.

Si vous avez besoin de la racine carrée pour calculer un triangle de Pythagore (sqrt (x * x + y * y)), et les deux x et y sont non négatifs, alors une approximation très rapide à cette question est 

max(x,y) + min(x,y)*0.333

a une erreur maximale de 5,7%. Méfiez-vous branche en min erreurs de prédiction () et max () si.

Si vous avez un flottant positif « normal » ou double, pas un int, et que vous voulez utiliser une méthode de consultation table, vous pouvez faire deux consultation de tables séparées ups, un pour l'exposant (re-biaisé), et une pour quelques bits de la mantisse (décalage et le masque extraction bitfield), et puis multiplier les deux look up table de résultats ensemble.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top