Kalkulator aproksimasi Chebyshev

 (stuffmatic.com)
2 poin oleh GN⁺ 2024-10-06 | 1 komentar | Bagikan ke WhatsApp
  • Chebyshev approximation calculator adalah alat yang menghasilkan kode aproksimasi fungsi matematika di web
  • Pengguna dapat menentukan fungsi yang akan diaproksimasi, interval, dan jumlah suku melalui f(x), x min, x max, dan Terms
  • Opsi Match x min x max dan area Coefficients menyediakan alur untuk memeriksa atau menyesuaikan batas interval dan nilai koefisien
  • Di area Generated code, hasil perhitungan ditampilkan dalam bentuk kode; pada layar contoh terlihat koefisien dari c0 hingga c10
  • Karena terhubung dengan repositori GitHub, pengguna dapat memeriksa langsung kode implementasi alat web ini

Generator kode aproksimasi Chebyshev

  • Chebyshev approximation calculator menghasilkan kode untuk mengaproksimasi fungsi matematika secara efisien
  • Kondisi aproksimasi dimasukkan melalui UI web
    • f(x): fungsi yang akan diaproksimasi
    • x min: nilai minimum interval
    • x max: nilai maksimum interval
    • Terms: jumlah suku yang digunakan
    • Match x min x max: opsi yang terkait dengan batas interval

Pemeriksaan koefisien dan kode yang dihasilkan

  • Layar dibagi menjadi area Coefficients dan Generated code
  • Koefisien yang ditampilkan sebagai contoh dapat diperiksa dari c0 hingga c10
    • c0 = 0.16793649417016518
    • c1 = -0.12411164956092625
    • c2 = -0.09756341588422193
    • c3 = 0.1800765790518846
    • c4 = -0.06972963647223016
    • c5 = -0.09250127939333941
    • c6 = 0.18076946080324185
    • c7 = 0.15990613621816677
    • c8 = -0.028659588693985123
    • c9 = -0.09494966104347571
    • c10 = -0.04980429834982578
  • Di layar juga ditampilkan item koefisien dari c11 hingga c39

Repositori kode

Bacaan terkait

1 komentar

 
GN⁺ 2024-10-06
Komentar Hacker News

  • Keren. Sekitar tahun 1974 saya pernah dibayar untuk menulis fungsi yang menghitung akar kuadrat dalam assembly IBM 360
    Itu tahun terakhir saya sebagai mahasiswa S1, dan saya diminta membuatnya seefisien mungkin. Masukannya saya skala ke antara 0 dan 1, lalu untuk tebakan awal saya memakai aproksimasi Chebyshev, kemudian menerapkan 2 atau 3 iterasi metode Newton yang di-unroll untuk mendapatkan hasilnya. Itu adalah penghasilan pertama saya dari menulis kode

    • Saya suka cerita seperti ini. Saya masih ingat betul momen di kelas pertama analisis numerik ketika tiba-tiba sadar akan potensi komputasi dan rasanya seperti mata saya terbuka lebar

  • Dibuat dengan sangat baik. Saya jadi terpikat dengan betapa efisiennya aproksimasi seperti ini, dan jadi jauh lebih paham mengapa implementasi fungsi trigonometri atau fungsi matematika lain di komputer 8-bit dulu sering dilakukan dengan cara seperti itu
    Ada juga dokumen asli yang keren dari BBC Research Department tahun 1969 yang membahas mengapa pendekatan ini sangat bagus: https://downloads.bbc.co.uk/rd/pubs/reports/1969-10.pdf
    Kalau selama ini hanya pernah melihat aproksimasi Taylor, ini bisa terlihat seperti sihir pada awalnya

    • Betul. Sisi matematikanya memang begitu, dan fakta bahwa pada akhirnya semuanya bermuara pada beberapa baris kode juga terasa cukup magis

  • Dulu saya pernah mendapat hasil yang bagus dengan Sollya: https://www.sollya.org/
    Hanya saja, meskipun hasilnya bagus, perangkat lunaknya sendiri agak merepotkan untuk dipakai

    • Sollya mungkin memang salah satu alat modern terbaik untuk pekerjaan seperti ini. Di dalamnya kemungkinan ia melakukan aproksimasi Remez lalu mengkuantisasi ke floating-point dengan LLL, jadi tidak memakai Chebyshev secara langsung

  • Jika Math.sin(x)/x, yaitu fungsi sinc, diaproksimasi pada interval [-3,3] dengan 7 suku, maka koefisien c0...c6 semuanya menjadi NaN. Apakah ini bug?
    Sebagai solusi sementara saya memaksa kasus saat x mendekati 0 menjadi 1.0 saja
    if(Math.abs(x) > 1e-8 ){ Math.sin(x)/x } else { 1.0 }

    • Sulit dibilang benar-benar bug. Kodenya kemungkinan mengevaluasi fungsi pada titik grid seperti x_j = (xmin) + (xmax - xmin)/2(1 + cos(pi[0..j-1]/(j-1)) untuk mendapatkan koefisien Chebyshev, dan jika salah satunya tepat 0 maka ia akan menghitung Math.sin(0)/0, yang menghasilkan NaN
      Jalan memutar lainnya adalah memakai rentang yang sedikit tidak simetris seperti [-3,+3.0000001]
    • Masalahnya di sini adalah ekspresi awalnya memang tidak terdefinisi dengan baik di x=0, dan sepertinya kode aproksimasinya tersandung di situ. Agak disayangkan juga
    • Ya, ini bug. Jika fungsi tidak terdefinisi di semua node Chebyshev, aplikasinya seharusnya menampilkan error. Untuk saat ini, seperti yang sudah ditemukan, masalah ini mudah diakali

  • Polinomial Chebyshev terlalu kuat dan serbaguna untuk aproksimasi; orang-orang sampai terlalu menyukainya, mengira ini seperti curang, lalu malah tidak memakainya
    Chebyshev seharusnya menjadi metode pertama yang dicoba. Jaringan saraf sebaiknya jadi pilihan terakhir

  • Luar biasa. Belakangan ini saya ingin melakukan hal seperti ini, tetapi ternyata sangat sulit mencari kode untuk menghitung aproksimasi
    Saya sudah menandainya untuk dipakai nanti saat perlu mengaproksimasi fungsi dengan cepat

    • Saya juga terkejut betapa sulitnya menemukan kode aproksimasi Chebyshev yang benar-benar berfungsi. Semoga proyek ini bisa mengubah itu

  • Chebyshev terasa seperti ilmu hitam. Bahkan setelah melihat penurunannya di kelas pascasarjana pun rasanya masih begitu

  • Chebfun dari Nick Trefethen dan yang lain juga wajib disebut. Itu adalah alat yang memperluas ide ini ke hampir semua arah yang bisa dibayangkan
    Chebfuns bisa dianggap sebagai padanan fungsi dari bilangan floating-point terhadap bilangan matematis nyata. Perangkat lunak yang sangat mengesankan
    https://www.chebfun.org

    • Setuju. Metode-metode di sana sangat kuat dan cepat. Dengan teknik berbasis Chebyshev dan fungsi ultrasferis, sebagian besar fungsi bisa diaproksimasi hingga tingkat presisi mesin dengan sangat cepat, dan setelah itu representasinya jauh lebih mudah dimanipulasi
      Ini membuka berbagai kemungkinan, misalnya mencari solusi persamaan diferensial-aljabar hingga presisi mesin, atau mencari minimum/maksimum global fungsi satu dimensi
      Setahu saya sekarang mereka memakai algoritme lain, tetapi metodologi dasar yang dulu dipakai Chebfun bisa dilihat di bab 6 buku Trefethen Spectral Methods in Matlab. Metode terbaru yang memakai fungsi ultrasferis dijelaskan dalam makalah SIAM Review oleh Olver dan Townsend, A Fast and Well-Conditioned Spectral Method

  • Saya penasaran, semoga tidak apa-apa bertanya di sini. Dulu saya menonton video yang mengatakan bahwa Nintendo 64 tidak punya kemampuan menghitung fungsi sinus, jadi ia memakai tabel lookup dari 0 sampai 2π, dan juga ada trik cerdas untuk mengecilkan ukuran tabelnya
    Apakah mungkin melatih jaringan saraf lalu menyimpan bobotnya, atau membuat fungsi dan menyimpan koefisiennya, untuk menghitung sinus dan cosinus?

    • Jaringan saraf sering kali secara internal memakai fungsi trigonometri, jadi perhitungannya akan jauh lebih banyak daripada yang dibutuhkan
      Jika ada sedikit sisa siklus CPU, Anda bisa memakai aproksimasi hibrida: ambil nilai dari tabel lookup kasar sebagai tebakan awal lalu lakukan beberapa iterasi teknik aproksimasi numerik. Atau, seperti di tulisan utama, simpan saja beberapa koefisien awal dari aproksimasi polinomial
    • Kalau belum familiar, coba lihat CORDIC. Dulu itu trik umum untuk trigonometri, dan sampai sekarang masih lumayan dipakai di dunia embedded
      Jaringan saraf bisa berguna jika Anda punya sampel suatu fungsi tetapi tidak tahu cara mengaproksimasinya; di sini bukan itu kasusnya
    • Tentu saja mungkin melatih jaringan saraf untuk menghitung fungsi apa pun, tetapi untuk fungsi yang sudah sangat dipahami seperti sinus itu sama sekali tidak masuk akal
      Jaringan saraf adalah solusi hebat ketika Anda harus mengevaluasi sesuatu yang tidak mudah dianalisis secara matematis, tetapi teknik yang sudah diketahui untuk menghitung dan mengaproksimasi fungsi trigonometri sudah sangat banyak
      Melatih jaringan saraf untuk menghitung sinus itu seperti versi matematis dari memakai LLM untuk membalik string. Bisa saja dilakukan, tetapi itu ide yang biasanya muncul hanya kalau Anda tidak tahu bahwa masalah itu pada dasarnya sudah terselesaikan dengan pendekatan yang lebih langsung
      Sebelum memakai teknik AI/ML, selalu ada gunanya mengecek apakah para matematikawan sudah punya solusinya. Zaman sekarang kemungkinan besar banyak usaha dihabiskan untuk menempelkan AI/ML pada masalah yang sebenarnya sudah punya solusi yang dikenal, efisien, bahkan optimal—hanya saja pengembangnya belum tahu
    • Jaringan saraf pada dasarnya adalah curve fitting, jadi tentu bisa. Video ini mungkin membantu: https://www.youtube.com/watch?v=FBpPjjhJGhk But what is a neural network REALLY?
      Kekuatan utama jaringan saraf baru terasa ketika jumlah masukannya sangat banyak, bukan hanya beberapa. Untuk kasus sederhana seperti sin(x), ada metode lain seperti alat yang dibagikan di sini
    • Teknik penghematan yang biasa dipakai adalah hanya menyimpan tabel dari 0 sampai π/2, lalu memakai 2 bit indeks tambahan untuk membangkitkan tiga kuadran sisanya

  • Sangat keren. Karena iseng, saya ingin melihat seberapa cepat saya bisa membuat fungsi yang sulit diaproksimasi dengan baik
    Sejauh ini Math.cos(x * Math.exp(Math.cos(x * x))) adalah yang paling berhasil. Komposisinya banyak, jadi muncul osilasi cepat dan gradien curam, sehingga sulit diaproksimasi dengan mudah memakai Chebyshev