Algorithme mathématique plus rapide sacrifiant la précision

Question

Je développe un jeu qui appelle autant de fonctions mathématiques pour la physique et le rendu. "Fast inverse sqrt" utilisé dans Quake3 est connu pour être plus rapide que sqrt() et son arrière-plan est magnifique. Connaissez-vous un autre algorithme plus rapide que d'habitude avec une perte de précision acceptable?

Answer 1

Ces algorithmes sont appelés "algorithmes d'approximation" dans la littérature. Le livre standard avec beaucoup d'exemples est Approximation Algorithms by Vijay V. Vazirani.

Le cas de sin x ~~ x est un cas particulier de quelque chose d'un peu plus général: Regardez le Taylor series (ou série de Fourier dans le cas des fonctions périodiques) de votre fonction et ne calculez que les premiers termes.

Une autre technique (quelque peu brutale) consiste à assembler de façon aléatoire quelques points de votre fonction, puis à exécuter une régression linéaire contre celle-ci. De cette façon, vous pouvez obtenir un bon polynôme décrivant votre fonction aussi :).

Answer 2

pour les petites x: sin (x) = x ~ est celui qui est souvent utilisé en physique

Answer 3

Tout est habituellement probabiliste comme celui-ci. Lancer une simulation 10 fois sera plus rapide, mais produira des résultats moins précis que d'exécuter une simulation 1000 fois.

Answer 4

Niko a quelques bonnes suggestions auxquelles j'ajouterais la vieille table de recherche de mode.

J'ai utilisé plusieurs fois une table de consultation pour des fonctions circulaires (sin/cos/tan) dans un système en temps réel haute performance. Le sqrt() est plus dur de cette façon, mais si votre plage d'entrée est restreinte (pour dire les pixels de l'écran), il est difficile de battre pour la vitesse, et vous pouvez ajuster le compromis espace/précision exactement. Vous pouvez également utiliser la recherche d'une plage commune, puis avoir une retombée sur une fonction framework sqrt() pour le cas rare.

Paul

Answer 5

Toute fonction continue de (qui comprend les opérations mathématiques les plus courantes) peut être une bonne approximation sur un intervalle borné par un polynôme. Ceci, avec des identités relativement simples que les fonctions mathématiques communes satisfont habituellement (comme les lois d'addition) et les recherches de tables, fournit la base des techniques standard pour construire des algorithmes d'approximation rapide (et aussi la base des méthodes de précision). bibliothèque).

Les séries de Taylor sont généralement un mauvais choix, cependant; Les polynômes Chebyshev ou Minimax ont de bien meilleures caractéristiques d'erreur pour la plupart des utilisations de calcul. La technique standard pour ajuster les polynômes minimax est d'utiliser l'algorithme de Remes, qui est implémenté dans beaucoup de logiciels mathématiques commerciaux, ou vous pouvez rouler votre propre implémentation avec une journée de travail si vous savez ce que vous faites.

Pour mémoire, il faudrait éviter les « racine carrée inverse rapide » sur les processeurs modernes, car il est beaucoup plus rapide d'utiliser une racine instruction estimation carré réciproque virgule flottante (rsqrtss/rsqrtps sur SSE, vrsqrte sur NEON, vrsqrtefp sur AltiVec). Même la racine carrée matérielle (non approximative) est assez rapide sur les processeurs Intel actuels.

Answer 6

À partir du code source Doom, pour la distance approximative entre deux points 2D sans avoir à utiliser sqrt() ou fonctions trigonométriques:

fixed_t P_AproxDistance(fixed_t dx, fixed_t dy) 
{ 
    dx = abs(dx); 
    dy = abs(dy); 
    if (dx < dy) 
     return dx+dy-(dx>>1); 
    else 
     return dx+dy-(dy>>1); 
} 

Notez que x >> 1 est le même que x/2 mais un peu plus rapide - compilateurs bons modernes faites-le automatiquement de nos jours, mais à l'époque, ils n'étaient pas si bien.