Perhitungan Trigonometri Cepat
Tugas Anda adalah membuat program yang dapat menghitung sinus, kosinus dan garis singgung dari sudut dalam derajat.
Aturan
- Tidak ada fungsi trigonometri bawaan (bahkan tidak secant, cosecant dan cotangent jika bahasa Anda memilikinya).
- Anda dapat menggunakan tabel pencarian, tetapi ukuran totalnya tidak boleh lebih dari 3000 anggota (untuk ketiga operasi disatukan). Tolong buat itu membaca tabel dari file (misalnya
trig.lookup
) sehingga mereka tidak membingungkan kode. - Tidak ada akses jaringan.
- Anda harus membulatkan output dengan benar seperti dijelaskan di bawah ini. Jangan gunakan lantai atau langit-langit.
- Anda dapat menggunakan metode apa pun untuk menghitung nilai, misalnya pecahan lanjutan , asalkan benar ke 7 angka penting.
- Kode Anda harus dapat menentukan waktu sendiri. Kecualikan operasi file I / O dari waktu Anda - jadi tentukan saja fungsi yang melakukan trigonometri dan pembulatan apa pun.
- Saya harus dapat menjalankan kode Anda. Silakan kirim tautan ke kompiler / juru bahasa yang tersedia secara bebas dan berikan instruksi yang diperlukan untuk mengkompilasi / menjalankan kode (mis. Opsi apa yang harus diteruskan ke GCC).
- Celah standar berlaku.
Masukkan format
- Baca dari file yang dipanggil
trig.in
kecuali bahasa Anda tidak mendukung file I / O. - Sudutnya antara 0 dan 360 inklusif.
- Input akan terdiri dari sudut hingga sepuluh angka signifikan dalam digit desimal, dipisahkan oleh garis baru. Sebagai contoh:
90.00000000
74.54390000
175.5000000
Format output
- Untuk setiap sudut yang disediakan, Anda harus menampilkan sinus, kosinus, dan garis singgung ke 7 angka signifikan, dipisahkan oleh spasi, pada satu baris. Gunakan "notasi ilmiah", misalnya
1.745329E-5
untuktan 0.001
atau1.000000E+0
untuksin 90
. - Nyatakan tak terhingga atau NaN oleh
n
, misalnya output untuk90.00000000
seharusnya1.000000 0.000000 n
. - Jika input adalah tiga sudut yang dipisahkan oleh baris baru, output Anda harus terdiri dari tiga baris, masing-masing berisi sinus, kosinus dan garis singgung.
- Anda mungkin tidak menghasilkan apa pun.
- Keluaran ke file yang dipanggil
trig.out
kecuali bahasa Anda tidak mendukung file I / O.
Mencetak gol
- kode tercepat . Tantangannya adalah menulis sebuah program yang menghitung tiga nilai ini secepat mungkin. Waktu tercepat menang.
- Setiap orang akan menerima input tes yang sama dari banyak sudut.
- Waktu akan direkam di mesin saya.
- Skor Anda adalah rata-rata dari tiga proses pada input yang sama (Anda tidak dapat menyimpan apa pun di antara proses yang jelas).
- Waktu kompilasi tidak termasuk. Tantangan ini lebih tentang metode yang digunakan daripada bahasa. (Jika seseorang bisa mengarahkan saya ke bagaimana saya akan mengecualikan waktu kompilasi untuk bahasa seperti Java, saya akan sangat berterima kasih)
- Mesin saya adalah instalasi Ubuntu 14.04. Statistik prosesor ada di Pastebin (diperoleh dengan menjalankan
cat /proc/cpuinfo
). - Saya akan mengedit waktu Anda menjadi jawaban Anda ketika saya sudah mengujinya.
math
fastest-code
trigonometry
Geobit
sumber
sumber
sin
,cos
dantan
ada di jalur baru. Apakah saya perlu mengubahnya untuk menampilkan jawaban ke satu baris?Jawaban:
Fortran 90
Saya menggunakan metode CORDIC dengan array pra-tabulasi dari 60 nilai arctan (lihat artikel Wiki untuk detail tentang mengapa itu perlu).
Kode ini membutuhkan file,,
trig.in
dengan semua nilai pada baris baru untuk disimpan dalam folder yang sama dengan yang dapat dieksekusi Fortran. Kompilasi ini adalah,di mana
file
nama file apa pun yang Anda berikan (mungkinSinCosTan.f90
akan lebih mudah, meskipun tidak perlu mencocokkan nama program dan nama file). Jika Anda memiliki kompiler Intel, saya sarankan menggunakansebagai
-xHost
(yang tidak ada untuk gfortran) memberikan optimasi tingkat yang lebih tinggi tersedia untuk prosesor Anda.Uji coba saya memberi saya sekitar 10 mikrodetik per perhitungan saat menguji 1000 sudut acak menggunakan gfortran 4.4 (4,7 atau 4,8 tersedia di repo Ubuntu) dan sekitar 9,5 mikrodetik menggunakan ifort 12.1. Menguji hanya 10 sudut acak akan menghasilkan waktu yang tidak dapat ditentukan dengan menggunakan rutinitas Fortran, karena rutinitas waktu akurat untuk milidetik dan matematika sederhana mengatakan perlu 0,100 milidetik untuk menjalankan semua 10 angka.
EDIT Rupanya saya adalah timing IO yang (a) membuat timing lebih lama dari yang diperlukan dan (b) bertentangan dengan bullet # 6. Saya telah memperbarui kode untuk mencerminkan hal ini. Saya juga menemukan bahwa menggunakan
kind=8
integer dengan subrutin intrinsiksystem_clock
memberikan akurasi mikrodetik.Dengan kode yang diperbarui ini, saya sekarang menghitung setiap set nilai fungsi trigonometri dalam sekitar 0,3 mikrodetik (angka signifikan pada akhirnya bervariasi run-to-run, tetapi secara konsisten melayang di dekat 0,31 us), pengurangan yang signifikan dari sebelumnya iterasi yang menghitung waktu IO.
sumber
Python 2.7.x atau Java (Silakan pilih)
Juru bahasa Python gratis dapat diunduh dari sini .
Penerjemah Java gratis dapat diunduh dari sini .
Program dapat mengambil input dari file bernama
trig.in
terletak di direktori yang sama dengan file program. Input dipisahkan oleh baris baru.Saya awalnya melakukan ini dengan python karena - yah, saya suka python. Tapi, karena saya ingin mencoba untuk menang juga, saya menulis ulang di java setelahnya ...
Versi Python: Saya mendapat sekitar 21 μs per dijalankan di komputer saya. Saya mendapat sekitar 32 μs ketika menjalankannya di IDEone .
Versi Java: Saya mendapatkan sekitar 0,4 μs per dijalankan di komputer saya, dan 1,8 μs pada IDEone .
Spesifikasi komputer:
Uji:
sin
,cos
dantan
semua sudut masukan.Input tes yang digunakan untuk keduanya adalah sebagai berikut:
Tentang Kode:
Premis untuk program ini adalah untuk memperkirakan
sin
dancos
menggunakan polinomial Taylor mereka dengan 14 istilah, yang menurut saya perlu untuk memiliki perkiraan kesalahan kurang dari 1e-8. Namun saya menemukan itu lebih cepat untuk menghitungsin
daripadacos
, jadi saya memutuskan untuk menghitungcos
dengan menggunakancos=sqrt(1-sin^2)
Versi Python:
Versi Java:
sumber
cos
Perhitungan Anda berlebihan, saya hanya akan lakukansin(x+90degrees)
sin
sebagai fungsi, dan variabel. Saya pikir akan lebih cepat untuk tidak harus melewati sesuatu untuk yangsin()
kedua kalinya, tetapi saya akan membandingkan keduanya untuk melihat apakah itu benar-benar terjadi. Apakah kesan Anda bahwacopySign()
fungsi lebih lambat sehingga menambahkan hal-hal seperti dalamsin()
fungsi saya ?Oktaf (atau Matlab) & C
Sedikit proses pembangunan yang rumit, tetapi semacam pendekatan baru dan hasilnya menggembirakan.
Pendekatannya adalah untuk menghasilkan polinomial kuadratik yang mendekati untuk setiap tingkat. Jadi derajat = [0, 1), derajat = [1, 2), ..., derajat = [359, 360) masing-masing akan memiliki polinomial yang berbeda.
Bagian bangunan oktaf
Oktaf tersedia untuk umum - Google
download octave
.Ini menentukan polinomial kuadratik paling cocok untuk setiap derajat.
Simpan sebagai
build-fast-trig.m
:C - bagian bangunan
Ini mengkonversi ganda dalam format teks ke format biner asli pada sistem Anda.
Simpan sebagai
build-fast-trig.c
:Menyusun:
Menghasilkan file koefisien
Lari:
Sekarang kita memiliki
qcoeffs.dat
file data yang akan digunakan untuk program yang sebenarnya.C - bagian trigonometri cepat
Simpan sebagai
fast-trig.c
:Menyusun:
Lari:
Ini akan membaca dari
trig.in
, simpan ketrig.out
dan cetak untuk menghibur waktu yang telah berlalu dengan presisi milidetik.Bergantung pada metode pengujian yang digunakan, mungkin gagal pada input tertentu, misalnya:
Output yang benar seharusnya
0.000000e+00 1.000000e+00 0.000000e+00
. Jika hasilnya divalidasi menggunakan string, input akan gagal, jika divalidasi menggunakan kesalahan absolut, misalnyafabs(actual - result) < 1e-06
, input akan diteruskan.Kesalahan absolut maksimum untuk
sin
dancos
adalah ≤ 3e-07. Karenatan
, karena hasilnya tidak terbatas pada ± 1 dan Anda dapat membagi angka yang relatif besar dengan angka yang relatif kecil, kesalahan absolut bisa lebih besar. Dari -1 ≤ tan (x) ≤ +1, kesalahan absolut maksimum adalah ≤ 4e-07. Untuk tan (x)> 1 dan tan (x) <-1, kesalahan relatif maksimum , misalnyafabs((actual - result) / actual)
biasanya <1e-06 sampai Anda mendapatkan area (90 ± 5) atau (270 ± 5) derajat, maka kesalahan bertambah buruk.Dalam pengujian, waktu rata-rata per input tunggal adalah (1,053 ± 0,007) μs, yang pada mesin saya sekitar 0,070 μs lebih cepat daripada asli
sin
dancos
,tan
didefinisikan dengan cara yang sama.sumber
Kobra
Kompilasi dengan
cobra filename -turbo
Pengujian: AMD FX6300 @ 5.1GHz
Tes 360 * 10000 yang digunakan oleh jawaban C berjalan dalam 365ms (vs 190ms)
Tes 4-entri yang digunakan oleh Python dan Java jawaban berjalan dalam 0,32 μs (vs 30 μs, 3 μs)
Uji sudut acak 1000 yang digunakan oleh jawaban Fortran berjalan pada 100ns per sudut (vs 10μs)
sumber
C
Inilah usaha saya. Ini berfungsi seperti ini:
Bangun tabel semua nilai dosa (x) dari 0 hingga 450 derajat. Secara setara, ini semua nilai cos (x) dari -90 hingga 360 derajat. Dengan 2926 elemen, ada ruang yang cukup untuk nilai setiap 1 / 6,5 derajat. Oleh karena itu unit program 1 / 6,5 derajat, dan ada 585 unit dalam seperempat putaran.
Ubah derajat input menjadi unit program (dikalikan dengan
6.5==110.1 binary.
) Temukan nilai terdekat untuk sin dan cos dari tabel. kemudian ubah sisa bagian input (dx) menjadi radian.terapkan formula
sin(x+dx) == sin x +(d(sin x)/dx)*dx.
perhatikan itu(d(sin x)/dx)==cos x,
tetapi hanya jika kita menggunakan radian.sayangnya itu tidak cukup akurat dengan sendirinya, jadi diperlukan istilah lain, berdasarkan turunan berikutnya.
d2(sin x)/dx2 == -sin x.
Ini perlu dikalikan dengandx*dx/2
(tidak yakin dari mana faktor 2 berasal, tetapi berfungsi.)Ikuti prosedur analog untuk
cos x
, lalu hitungtan x == sin x / cos x
.Kode
Ada sekitar 17 operasi floating point di sini. Itu bisa diperbaiki sedikit. Program ini berisi pembuatan tabel dan hasil tes menggunakan fungsi trigonometri asli, tetapi algoritma tidak. Saya akan menambahkan waktu dan edit untuk memenuhi persyaratan I / O nanti (mudah-mudahan akhir pekan ini.) Ini cocok dengan output fungsi asli kecuali untuk nilai yang sangat kecil dari sin x dan cos x, yang harus diperbaiki menjadi lebih baik daripada output fungsi asli dengan beberapa penyesuaian.
sumber