Adakah prosesor yang mengimplementasikan instruksi akar kuadrat bilangan bulat?

• Isunya bukan sqrt floating-point yang umum, melainkan apakah pernah ada contoh yang menyediakan akar kuadrat bilangan bulat sebagai instruksi CPU atau fitur hardware; divider/square-rooter pada Nintendo DS mirip, tetapi bukan instruksi native
• Harris RTX 2000 Forth CPU dan RTX 2010 kelas militer disebut sebagai contoh yang menyediakan instruksi square root bertahap; RTX 2000 memakai struktur yang memperoleh hasil lewat 1 kali setup dan 15 kali step
• Contoh yang lebih lama, ENIAC, pada 1946 mengendalikan decimal integer accumulator dengan divider/square-rooter unit untuk melakukan hingga 40 operasi pembagian atau 3 operasi akar kuadrat per detik
• Akar kuadrat bilangan bulat membutuhkan pengali integer cepat dan presisi yang cukup, sehingga menjadi beban besar bagi CPU historis; ada juga pendekatan seperti frsqrte/frsqrts pada ARMv8 yang memisahkan estimasi dan iterasi untuk mengatur akurasi serta kecepatan
• Inverse square root ala Quake tidak lagi punya keunggulan performa umum pada hardware modern, sementara lookup tabel, interpolasi, iterasi keluarga Halley, dan divide-and-conquer fixed-point menjadi pilihan yang bergantung pada lingkungan implementasi

---

Cakupan pertanyaan dan contoh Nintendo DS

• Pertanyaan ini membahas apakah pernah ada prosesor yang benar-benar mengimplementasikan instruksi akar kuadrat bilangan bulat
• Instruksi square root floating-point memang umum, tetapi pembahasan dimulai dari premis bahwa penanya belum pernah melihat instruksi square root khusus integer
• Nintendo DS memiliki integer divider/square rooter yang dipetakan ke memori
  • Ini membantu perhitungan 3D karena prosesor ARM-nya tidak memiliki FPU atau hardware divider
  • Namun, petunjuk utama dalam pertanyaan adalah bahwa itu bukan instruksi prosesor native

Harris RTX 2000 dan RTX 2010

• Harris RTX 2000 Forth CPU disebut sebagai contoh yang menyediakan instruksi square root bertahap
• Sibling kelas militernya, RTX 2010, juga menyediakan fungsi dalam lini yang sama
• Materi terkait menautkan ke Stack Computers: RTX 2000
• Menurut RTX2000 Family Programmer’s Reference Manual, fungsi ini lebih dekat ke square root iteratif, dengan cara menjalankan 1 instruksi setup dan 15 instruksi step untuk mendapatkan nilai akhir
• “A Fast Method for Finding an Integer Square Root” oleh Ken Lyons juga disebut sebagai materi yang membahas implementasi hardware dan contoh pemrograman untuk keluarga RTX2000

Divider/square-rooter unit pada ENIAC

• ENIAC pada 1946 juga termasuk contoh hardware akar kuadrat bilangan bulat
• Menurut deskripsi yang dikutip, ENIAC mengendalikan 4 accumulator dengan multiplier unit khusus untuk melakukan hingga 385 perkalian per detik
• 5 accumulator dikendalikan oleh divider/square-rooter unit khusus, yang memproses hingga 40 pembagian atau 3 operasi akar kuadrat per detik
• Accumulator ENIAC bekerja sebagai decimal integer

Mengapa implementasi akar kuadrat bilangan bulat sulit

• Salah satu jawaban menjelaskan metode efisien untuk menghitung square root: mencari inverse square root dengan iterasi Newton-Raphson, lalu mengalikannya dengan nilai asal
• Metode ini dikenal sebagai “Quake method”, dan pada CPU serta GPU modern ada contoh yang digeneralisasi menjadi instruksi estimasi awal dan instruksi iterasi
  • Contoh: frsqrte pada ARMv8
  • Contoh: frsqrts pada ARMv8
• Kendala utama pendekatan ini adalah kebutuhan akan multiplier cepat
  • Sqrt floating-point membutuhkan FP multiplier cepat, dan FPU memilikinya
  • Sqrt integer membutuhkan integer multiplier cepat, tetapi penjelasannya menyebutkan bahwa secara historis sebagian besar CPU tidak memiliki hardware seperti itu
  • Untuk mendapatkan presisi yang memadai, ada juga syarat bahwa diperlukan multiplier cepat dengan lebar dua kali lebar input
• Karena kebutuhan presisi tidak selalu sama, memisahkan estimasi dan iterasi seperti frsqrte dan frsqrts memungkinkan jumlah iterasi disesuaikan dengan kompromi kecepatan–akurasi yang diinginkan

Perdebatan tentang teknik Quake dan implementasi sqrt modern

• Jawaban lain membantah klaim bahwa trik Quake adalah yang paling efisien, dengan mengatakan bahwa klaim itu sudah lama tidak benar dan hanya berlaku saat menginginkan hasil float berkualitas rendah pada hardware tertentu
• Pada chip modern, instruksi sqrt native jauh lebih cepat, sering kali dijelaskan berada pada kisaran beberapa siklus clock
• Sebagai metode yang lebih cepat, diusulkan pendekatan menyimpan tabel nilai dengan jarak tidak seragam, mengambil dua nilai dengan cepat dan melakukan interpolasi, lalu menggeser exponent base-2 dan, jika perlu, menerapkan satu iterasi yang lebih baik daripada Newton-Raphson
• Keluarga Halley dan berbagai metode iteratif dapat konvergen lebih cepat daripada Newton-Raphson, tetapi kecepatan sebenarnya bergantung pada biaya tiap operasi
• Untuk rentang khusus integer, misalnya 2^32, ide yang sama dapat diterapkan sebagai fixed-point
  • Divide and conquer diajukan sebagai metode sederhana untuk hardware
  • Setiap 8 bit dapat dipetakan ke tabel berisi 256 nilai fixed-point dan di-lookup secara paralel, lalu dari 3 perkalian, 2 di antaranya dilakukan secara paralel untuk memperoleh nilai 32-bit dan men-truncate-nya
• Riset optimasi sqrt terus berlanjut, dan materi INRIA HAL diberikan sebagai contoh

[GN⁺]

Komentar Hacker News

• AArch64 NEON memiliki instruksi URSQRTE, jadi ternyata lebih dekat dengan pertanyaan awal daripada yang dikira
  Jika nilai 32-bit dipandang sebagai bilangan bulat fixed-point dengan 32 bit pecahan, rentang representasinya berjarak seragam dari 0 hingga 1-ε, dengan ε=2^-32
  URSQRTE menghitung perkiraan invers akar kuadrat, lalu membaginya dua, dan meng-clamp hasilnya ke rentang 0 hingga 1-ε
  Bilangan bulat fixed-point memang bukan bilangan bulat yang ketat, dan perkiraan invers akar kuadrat juga bukan akar kuadrat, tetapi bisa sampai cukup dekat
  FRSQRTE yang terkait adalah instruksi yang jauh lebih umum, menyediakan perkiraan invers akar kuadrat untuk floating-point 32-bit

  • Saya penasaran pekerjaan apa yang memberi manfaat cukup besar hingga instruksi serumit itu masuk ke AArch64, padahal bisa dengan mudah dipecah menjadi instruksi-instruksi yang lebih sederhana

• Kalau ditanya apakah bisa dalam satu siklus clock, jawabannya bisa kalau ada lookup table yang sangat besar
  Ukurannya sepertinya juga bisa diperkecil tergantung seberapa banyak gerbang logika serial yang dapat dijalankan dalam satu siklus clock
  Misalnya, akar kuadrat biner dari 10000 cukup mirip dengan akar kuadrat dari 100, hanya jumlah nolnya yang berbeda

  • Instruksi estimasi invers akar kuadrat floating-point (frsqrte) biasanya diimplementasikan sebagai lookup table seperti itu, diindeks dengan sebagian bit mantissa dan bit paling rendah dari eksponen
    Presisinya umumnya kira-kira setara bf16 (ARM, RISC-V) atau fp16 (x86), jadi jika butuh presisi lebih tinggi, setelahnya dilakukan beberapa iterasi Newton-Raphson
  • Ketika jumlah bit input adalah n, akar kuadrat bilangan bulat dapat dihitung dengan n/2 iterasi hanya memakai shift dan penjumlahan
    Pada tiap langkah, dihitung apakah bit baru harus diset pada hasil n_old dengan n2_new = (n_old + (1 << bit))^2 = n2_old + (n_old << (bit + 1)) + (1 << (bit*2))
    Lalu bandingkan dengan operand asli; jika lebih kecil atau sama, 1) set bit pada hasil dan 2) perbarui n2_old menjadi n2_new
    Dengan set instruksi microcode dan ALU yang sesuai, ini bisa dilakukan dalam n/2 atau mungkin n siklus clock, dan dengan optimisasi lebih lanjut n bisa dikurangi sampai indeks bit paling kiri yang menyala pada operand
  • Mungkin ini pertanyaan bodoh, tetapi apakah lookup table besar benar-benar pernah selesai dalam satu siklus clock?
    Kalau lookup table-nya besar, harus diambil dari memori, dan rasanya itu akan menimbulkan latensi cache dan hierarki memori
  • Kalau begitu, terdengar seolah algoritma apa pun di dunia bisa dijalankan dalam 1 siklus clock
  • Akar kuadrat bilangan bulat sebenarnya tidak terlalu buruk; cukup simpan N^0.5 entri dalam lookup table besar/kecil
    Caranya menyimpan N^2 untuk setiap jawaban N
    Untuk bilangan bulat 16-bit itu realistis, 32-bit mungkin juga, tetapi 64-bit tidak masuk akal

• Jika definisi “prosesor” diperluas sampai perangkat elektromekanis, Friden SRQ bisa menghitung akar kuadrat hanya dengan penjumlahan dan shift, tanpa satu pun komponen elektronik selain motor
  Posisi titik desimal harus disesuaikan secara manual, jadi secara teknis bisa juga disebut operasi bilangan bulat
  Video: https://youtu.be/o44a1ao5h8w

• Bukankah akar kuadrat bilangan bulat dari bilangan bulat apa pun bisa didapat dengan memakai deret 1 + 3 + 5 + ... + 2k + 1?
  Pada dasarnya caranya mencari k dari suku terdekat dalam deret itu yang lebih kecil atau sama dengan angka saya

  • Bisa jelaskan idenya?
    Secara definisi itu memang algoritma, tetapi kalau diimplementasikan secara naif, bahkan untuk bilangan 32-bit pun sangat lambat
    Pada titik itu, pencarian biner saja jauh lebih cepat
  • Cara yang lebih baik mungkin memakai ekspansi (x+y)^2=x^2+2xy+y^2 bersama pengamatan bahwa dalam basis apa pun, akar kuadrat dari bilangan 2n digit maksimal n digit
    Sama seperti metode umum menghitung akar kuadrat dengan tangan memakai pena dan kertas
    Jika ini diproses 8 bit sekaligus, yang diperlukan hanya lookup table untuk akar kuadrat bilangan 8-bit
  • Jika maksudnya mengulang deret itu terus, waktunya eksponensial terhadap panjang bit input
  • Ini salah satu contoh klasik pekerjaan yang sangat mudah diparalelkan sampai memalukan

• Bagian dari jawaban di bawah ini membuat saya tertawa:

  My implementation of square root using binary search, that doesn't depend on a multiplier. Only basic ALU instructions are used. It is vigorously undocumented. I have no idea what I wrote but it seems to work.
  Ini pengingat yang bagus bahwa kalau menulis kode yang terlalu pintar, besar kemungkinan nanti kita tidak ingat bagaimana kode itu bekerja

• Harus membaca agak ke bawah, tetapi lucu sekali bahwa jawabannya adalah ENIAC

  • Banyak orang mengira semua hal sebelum mereka masuk sekolah itu primitif dan nyaris tidak berjalan :)
    Cukup membaca sedikit saja sudah terlihat sebaliknya
    Sebagian besar ide cerdas masa kini sudah digunakan di komputer tahun 1940–60-an, dan kini didaur ulang di chip semikonduktor baru
    Contohnya pipelining, eksekusi out-of-order, dan multicore
    Hardware lama mungkin memang agak “kasar”, tetapi arsitekturnya memakai teknik-teknik yang sangat cerdik

• 2 ^ (1/2 * Log2(X)) = sqrt(X)
  Jika Log2(x) diganti dengan menghitung jumlah leading zero, kita bisa mendapat perkiraan yang sangat kasar
  Dengan mengaproksimasi Log(2) lebih baik, hasilnya bisa makin mendekati jawaban

• Jika yang dibutuhkan bukan jawaban tepat sampai bilangan bulat terdekat, melainkan perkiraan yang sangat kasar, cukup lakukan shift ke kanan sebanyak setengah posisi bit 1 terdepan
  Hampir semua prosesor punya instruksi shift, dan instruksi seperti FLO (Find Leading One) atau FFS (Find First Set) juga tampaknya begitu umum sampai saya tidak yakin ada berapa yang tidak memilikinya
  Untuk beberapa penggunaan, perkiraan yang sangat kasar seperti ini bisa sama bergunanya dengan jawaban yang tepat
  Misalnya ketika hanya membutuhkan nilai awal yang layak untuk iterasi Newton-Raphson setelahnya
  Tentu saja trik shift ke kanan ini juga cukup bagus sebagai nilai awal untuk perhitungan akar kuadrat yang lebih akurat :P

  • Apakah ini bagian tempat cerita DOOM muncul?
    Sekarang ini sudah jadi kisah internet yang cukup terkenal, dengan Carmack dan angka 32-bit ajaib
  • Fakta menarik: FFS dan generalisasinya, FNS, ada di CUDA: https://docs.nvidia.com/cuda/cuda-math-api/index.html#group_...
    Intrinsic hardware CUDA lain yang juga saya sukai secara pribadi adalah log2

• Kalau ingatan saya benar, sebagian besar, mungkin semua DSP fixed-point memiliki instruksi akar kuadrat atau instruksi pembantu

• Analisis menyeluruh algoritma akar kuadrat yang setengah terkait dan mungkin menarik bagi penggemar 6502: https://github.com/TobyLobster/sqrt_test