Szybkie obliczenia trygonometryczne
Twoim zadaniem jest stworzenie programu, który może obliczyć sinus, cosinus i styczną kąta w stopniach.
Zasady
- Brak wbudowanych funkcji trygonometrii (nawet siecznych, cosecant i cotangent, jeśli ma je Twój język).
- Możesz użyć tabel odnośników, ale ich całkowity rozmiar nie może przekraczać 3000 elementów (dla wszystkich trzech razem wziętych operacji). Proszę odczytaj tabele z pliku (np.
trig.lookup
), Aby nie myliły kodu. - Brak dostępu do sieci.
- Musisz poprawnie zaokrąglić wynik, jak wyjaśniono poniżej. Nie używaj podłogi ani sufitu.
- Możesz użyć dowolnej metody do obliczenia wartości, na przykład ułamków ciągłych , o ile jest to poprawne do 7 cyfr znaczących.
- Twój kod musi być w stanie sam się zmierzyć. Wyklucz operacje we / wy pliku z twojego czasu - więc po prostu określ czas funkcji, które wykonują wyzwalanie i dowolne zaokrąglanie.
- Muszę być w stanie uruchomić Twój kod. Proszę zamieścić link do darmowego kompilatora / interpretera i podać instrukcje potrzebne do skompilowania / uruchomienia kodu (np. Jakie opcje przekazać do GCC).
- Obowiązują standardowe luki .
Format wejściowy
- Czytaj z pliku o nazwie,
trig.in
chyba że Twój język nie obsługuje plików I / O. - Kąty zawierają się w przedziale od 0 do 360 włącznie.
- Dane wejściowe będą się składały z kątów do dziesięciu cyfr znaczących w liczbach dziesiętnych, oddzielonych nowymi wierszami. Na przykład:
90,00000000
74,54390000
175,5000000
Format wyjściowy
- Dla każdego podanego kąta należy wyprowadzić jego sinus, cosinus i styczną do 7 znaczących liczb, oddzielonych spacjami, w jednym wierszu. Użyj „notacji naukowej”, np.
1.745329E-5
Dlatan 0.001
lub1.000000E+0
dlasin 90
. - Oznacz nieskończoność lub NaN
n
, na przykład wyjściem dla90.00000000
powinno być1.000000 0.000000 n
. - Jeśli wejście ma trzy kąty oddzielone znakiem nowej linii, wynik powinien składać się z trzech linii, z których każda zawiera sinus, cosinus i styczną.
- Nie możesz wyprowadzać niczego innego.
- Wyjście do pliku o nazwie,
trig.out
chyba że twój język nie obsługuje I / O pliku.
Punktacja
- najszybszy kod . Wyzwanie polega na napisaniu programu, który oblicza te trzy wartości tak szybko, jak to możliwe. Najszybszy czas wygrywa.
- Każdy otrzyma ten sam testowy sygnał wejściowy pod wieloma kątami.
- Czasy zostaną zapisane na moim komputerze.
- Twój wynik to średnia z trzech przebiegów na tym samym wejściu (oczywiście nie możesz zapisać niczego pomiędzy przebiegami).
- Czas kompilacji nie jest wliczony. To wyzwanie dotyczy bardziej użytej metody niż języka. (Gdyby ktoś mógł mi wskazać, jak wykluczyłbym czas kompilacji dla języków takich jak Java, byłbym bardzo wdzięczny)
- Moja maszyna to instalacja Ubuntu 14.04. Statystyki procesora są na Pastebin (uzyskane przez uruchomienie
cat /proc/cpuinfo
). - Zmienię twój czas na twoją odpowiedź, kiedy ją przetestuję.
math
fastest-code
trigonometry
Geobity
źródło
źródło
sin
,cos
itan
jest w nowej linii. Czy muszę to zmienić, aby wyświetlać odpowiedzi w jednym wierszu?Odpowiedzi:
Fortran 90
I zatrudnić CORDIC metodę z pre-tabelaryczne tablicy 60 wartości arctan (patrz artykuł Wiki Szczegółowe informacje o tym, dlaczego to jest konieczne).
Ten kod wymaga pliku,
trig.in
w którym wszystkie wartości nowego wiersza będą przechowywane w tym samym folderze, co plik wykonywalny Fortran. Kompilowanie tego jestgdzie
file
jestSinCosTan.f90
podana nazwa pliku (prawdopodobnie byłoby to najłatwiejsze, chociaż nie jest konieczne dopasowanie nazwy programu i nazwy pliku). Jeśli masz kompilator Intel, zalecamy użyciejak
-xHost
(który nie istnieje dla gfortran) zapewnia optymalizacje wyższego poziomu dostępne dla twojego procesora.Moje testy dały mi około 10 mikrosekund na obliczenie podczas testowania 1000 losowych kątów za pomocą gfortran 4.4 (4.7 lub 4.8 jest dostępne w repozytoriach Ubuntu) i około 9,5 mikrosekund przy użyciu ifort 12.1. Testowanie tylko 10 losowych kątów da nieokreślony czas przy użyciu procedur Fortrana, ponieważ procedura pomiaru czasu jest dokładna do milisekundy, a prosta matematyka mówi, że uruchomienie wszystkich 10 liczb powinno zająć 0,100 milisekund.
EDIT Najwyraźniej mierzyłem czas IO, który (a) spowodował, że czas był dłuższy niż to konieczne i (b) jest sprzeczny z punktorem 6. Zaktualizowałem kod, aby to odzwierciedlić. Odkryłem również, że użycie
kind=8
liczby całkowitej z wewnętrznym podprogramemsystem_clock
zapewnia dokładność w mikrosekundach.Dzięki temu zaktualizowanemu kodowi obliczam teraz każdy zestaw wartości funkcji trygonometrycznych w około 0,3 mikrosekundy (znaczące cyfry na końcu zmieniają się między biegami, ale stale unosi się w pobliżu 0,31 us), co znacznie zmniejsza w porównaniu z poprzednim iteracja, która mierzyła czas IO.
źródło
Python 2.7.x lub Java (wybierz)
Bezpłatny interpreter języka Python można pobrać stąd .
Bezpłatny interpreter Java można pobrać stąd .
Program może pobierać dane wejściowe zarówno z pliku o nazwie
trig.in
znajdującej się w tym samym katalogu, co plik programu. Dane wejściowe są oddzielone znakami nowej linii.Pierwotnie robiłem to w Pythonie, ponieważ - cóż, uwielbiam Pythona. Ale ponieważ chcę również wygrać, przepisałem go później w Javie ...
Wersja Python: Mam około 21 µs na uruchomienie na moim komputerze. Dostałem około 32µs, gdy uruchomiłem go na IDEone .
Wersja Java: Dostaję około 0,4 µs na uruchomienie na moim komputerze i 1,8 µs na IDEone .
Dane techniczne komputera:
Test:
sin
,cos
itan
wszystkie kąty wejściowych.Dane wejściowe testu użyte dla obu są następujące:
O Kodeksie:
Założeniem tego programu było oszacowanie
sin
icos
użycie wielomianów Taylora z 14 terminami, co, jak obliczyłem, było konieczne, aby oszacować błąd na mniej niż 1e-8. Stwierdziłem jednak, że obliczenie było szybszesin
niżcos
, więc postanowiłem zamiast tego obliczyćcos
za pomocącos=sqrt(1-sin^2)
Wersja Python:
Wersja Java:
źródło
cos
obliczenia to przesada, po prostu bym to zrobiłsin(x+90degrees)
sin
zarówno jako funkcji, jak i zmiennej. Myślałem, że szybciej będzie nie musieć przekazywać czegośsin()
po raz drugi, ale porównam te dwa, aby zobaczyć, czy tak naprawdę jest. Czy miałeś wrażenie, żecopySign()
funkcja działa wolniej niż dodawanie rzeczy, na przykład w mojejsin()
funkcji?Oktawa (lub Matlab) i C.
Trochę skomplikowany proces kompilacji, ale rodzaj nowatorskiego podejścia, a wyniki były zachęcające.
Podejście polega na generowaniu przybliżonych kwadratowych wielomianów dla każdego stopnia. Tak więc stopień = [0, 1), stopień = [1, 2), ..., stopień = [359, 360) będzie miał inny wielomian.
Oktawa - część budowlana
Oktawa jest publicznie dostępna - Google
download octave
.Określa to najlepiej dopasowany wielomian kwadratowy do każdego stopnia.
Zapisz jako
build-fast-trig.m
:C - część budynku
Konwertuje to podwójnie w formacie tekstowym na natywny format binarny w twoim systemie.
Zapisz jako
build-fast-trig.c
:Skompilować:
Generowanie pliku współczynników
Biegać:
Teraz mamy
qcoeffs.dat
jako plik danych do użycia dla rzeczywistego programu.C - część szybkiego wyzwalania
Zapisz jako
fast-trig.c
:Skompilować:
Biegać:
Będzie odczytywał
trig.in
, zapisywał siętrig.out
i drukował, aby pocieszać upływający czas z milisekundową precyzją.W zależności od zastosowanych metod testowania może się nie powieść na niektórych danych wejściowych, np .:
Prawidłowe wyjście powinno być
0.000000e+00 1.000000e+00 0.000000e+00
. Jeśli wyniki zostaną sprawdzone przy użyciu ciągów, dane wejściowe zakończą się niepowodzeniem, jeśli zostaną zweryfikowane przy użyciu błędu bezwzględnego, npfabs(actual - result) < 1e-06
. Dane wejściowe przejdą.Maksymalny błąd bezwzględny dla
sin
icos
wynosił ≤ 3e-07. Ponieważtan
, ponieważ wynik nie jest ograniczony do ± 1 i można podzielić stosunkowo dużą liczbę przez względnie małą liczbę, błąd bezwzględny może być większy. Od -1 ≤ tan (x) ≤ +1 maksymalny błąd bezwzględny wynosił ≤ 4e-07. Dla tan (x)> 1 i tan (x) <-1 maksymalny względny błąd , np.fabs((actual - result) / actual)
Zwykle wynosił <1e-06, dopóki nie osiągniesz obszaru (90 ± 5) lub (270 ± 5) stopni, a następnie błąd się pogarsza.W badaniach, średni czas był za jednego wejścia (1,053 ± 0,007 ms), który na moim komputerze było około 0,070 mikrosekundy szybciej niż rodzimy
sin
icos
,tan
jest zdefiniowana w ten sam sposób.źródło
Kobra
Skompiluj to z
cobra filename -turbo
Testy: AMD FX6300 @ 5.1GHz
Test 360 * 10000 zastosowany w odpowiedzi C działa w ciągu 365 ms (w porównaniu do 190 ms)
4-wejściowy test używany w odpowiedziach na Python i Java przebiega w 0,32µs (vs 30µs, 3µs)
Test 1000 losowych kątów zastosowany w odpowiedzi Fortrana przebiega przy 100ns na kąt (vs 10µs)
źródło
do
Oto moja próba. Działa to tak:
Zbuduj tabelę wszystkich wartości sin (x) od 0 do 450 stopni. Równolegle są to wszystkie wartości cos (x) od -90 do 360 stopni. Przy 2926 elementach jest wystarczająco dużo miejsca na wartość co 1 / 6,5 stopnia. Jednostka programu wynosi zatem 1 / 6,5 stopnia, a na ćwierć obrotu jest 585 jednostek.
Przelicz stopnie wejściowe na jednostki programu (pomnóż przez
6.5==110.1 binary.
) Znajdź najbliższe wartości sin i cos z tabeli. następnie zamień pozostałą część danych wejściowych (dx) na radiany.zastosuj wzór
sin(x+dx) == sin x +(d(sin x)/dx)*dx.
zwróć uwagę, że(d(sin x)/dx)==cos x,
tylko, jeśli użyjemy radianów.niestety nie jest to wystarczająco dokładne, więc wymagany jest inny termin, oparty na następnej pochodnej.
d2(sin x)/dx2 == -sin x.
Należy to pomnożyć przezdx*dx/2
(nie jestem pewien, skąd bierze się współczynnik 2, ale działa).Postępuj zgodnie z analogiczną procedurą dla
cos x
, a następnie oblicztan x == sin x / cos x
.Kod
Jest tu około 17 operacji zmiennoprzecinkowych. Można to nieco poprawić. Program zawiera dane wyjściowe do budowania tabel i testowania przy użyciu natywnych funkcji wyzwalania, ale algorytm nie. Dodam taktowanie i edycję, aby spełnić wymagania we / wy później (mam nadzieję, że w ten weekend.) Pasuje do wyjściowej funkcji natywnej, z wyjątkiem bardzo małych wartości sin x i cos x, które powinny być lepsze niż wyjściowa funkcja natywna za pomocą trochę poprawiania.
źródło