Szybszy algorytm matematyczny poświęcający dokładność

Question

Pracuję nad grą, która wywołuje wiele funkcji matematycznych dla fizyki i renderingu. "Fast inverse sqrt" używany w Quake3 jest znany jako szybszy niż sqrt(), a jego tło jest piękne.

Czy znasz inny algorytm, który jest szybszy niż zwykle o akceptowalnej dokładności?

Answer 1

Algorytmy te nazywane są w literaturze "algorytmami aproksymacyjnymi". Standardowa książka z wieloma przykładami to Approximation Algorithms by Vijay V. Vazirani.

Przypadek grzechu x ~~ x jest szczególnym przypadkiem czegoś nieco bardziej ogólnego: Spójrz na Taylor series (lub serię Fouriera w przypadku funkcji okresowych) swojej funkcji i oblicz tylko kilka pierwszych terminów.

Inną (nieco brutalną) techniką jest losowe zebranie kilku punktów swojej funkcji, a następnie uruchomienie liniowej regresji przeciwko niemu. W ten sposób możesz uzyskać dobry wielomian opisujący twoją funkcję :).

Answer 2

małych x: sin (x) = x ~ to taki, który jest często stosowany w fizyce

Answer 3

Wszystko probabilistycznej jest zwykle w ten sposób. Uruchomienie symulacji 10 razy będzie szybsze, ale przyniesie mniej dokładne wyniki niż uruchomienie symulacji 1000 razy.

Answer 4

Niko ma kilka dobrych sugestii, do których dodaję tabelę ze starą modą.

Używam tabeli wyszukiwania dla funkcji okrągłych (sin/cos/tan) z powodzeniem wiele razy w systesmie o wysokiej wydajności w czasie rzeczywistym. W ten sposób sqrt() jest trudniejszy, ale jeśli twój zakres wejściowy jest ograniczony (powiedzmy piksele ekranu), trudno jest pokonać prędkość, i możesz dokładnie wyregulować kompromis w przestrzeni/dokładności. Możesz również użyć funkcji wyszukiwania dla zwykłego zakresu, a następnie zastosować funkcję ramową sqrt() dla rzadkiego przypadku.

Paul

Answer 5

Każda funkcja ciągła (która obejmuje większość typowych operacji matematycznych) można również w przybliżeniu ponad ograniczonym przedziale przez wielomian. To, wraz ze stosunkowo prostymi tożsamościami, które zwykle spełniają funkcje matematyczne (takie jak dodawanie praw) i wyszukiwaniem tabel, stanowi podstawę standardowych technik konstruowania szybkich algorytmów aproksymacyjnych (a także podstawą metod o wysokiej dokładności, takich jak stosowane w matematyce systemowej biblioteka).

Seria Taylora jest zwykle złym wyborem; Wielomiany Czebyszewa lub Minimax mają znacznie lepszą charakterystykę błędów dla większości zastosowań obliczeniowych. Standardową techniką dopasowania wielomianów minimax jest użycie algorytmu Remesa, który jest zaimplementowany w wielu komercyjnych programach matematycznych, lub możesz wdrożyć własną implementację w dzień pracy, jeśli wiesz, co robisz.

Dla przypomnienia, „Szybka odwrotność pierwiastka kwadratowego” należy unikać na nowoczesnych procesorach, jak to jest znacznie szybsze użyć zmiennoprzecinkową dyspozycję oszacowanie odwrotność pierwiastka kwadratowego (rsqrtss/rsqrtps na SSE, vrsqrte na neon, vrsqrtefp w AltiVec). Nawet (nie w przybliżeniu) pierwiastek kwadratowy sprzętu jest dość szybki na obecnych procesorach Intela.

Answer 6

z kodu źródłowego Zagłady, o przybliżonej odległości między dwoma punktami 2D bez konieczności użycia sqrt() lub funkcje trygonometryczne:

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); 
} 

Zauważ, że x >> 1 jest taka sama jak x/2 ale nieco szybciej - dobre współczesne kompilatory Zrób to automatycznie teraz, ale wtedy nie były tak świetne.