Pendahuluan
"Apa yang terjadi jika kita mengganti angka floating point dengan angka rasional dan mencoba membuat gambar?"
Saya bertanya pada diri sendiri pertanyaan ini setelah berpikir tentang tweet seorang peneliti dan guru grafis komputer Morgan McGwire. Dia berbicara tentang seberapa banyak siswa sains komputer terkejut ketika mereka pertama kali mengetahui bahwa untuk menyimpan angka floating-point yang akrab di komputer modern, kompromi harus dilakukan. Dan kompromi-kompromi ini membuat tugas-tugas sederhana menjadi sulit, misalnya, memeriksa apakah suatu titik termasuk dalam segitiga. Masalahnya, tentu saja, adalah bahwa memeriksa empat titik di bidang yang sama (coplanarity) menggunakan determinan atau semacam perkalian vektor (tetapi sebenarnya ini adalah hal yang sama) tidak akan pernah memberikan nilai persis sama dengan nol, yang diperlukan ini adalah metode matematika. Bahkan jika perhitungan nyata berada di pesawat yang sama adalah akurat, kompromi yang sama dengan akurasi hampir 1,0 akan memberikan jawaban bahwa keempat poin itu sendiri bukan coplanar.
Ini memunculkan ide pada saya - jika kita mengasumsikan bahwa semua data renderer yang masuk (koordinat titik, transformasi 3D, dll.) Ditetapkan sebagai bilangan rasional, maka mereka akan membuat semua operasi, dari membuat sinar, melintasi struktur percepatan ke persimpangan sinar dengan segitiga hanya bilangan rasional? Jika itu masalahnya, maka kita akan dapat melakukan tes coplanarity dengan tepat! Anda mungkin bertanya-tanya mengapa adegan 3D yang dinyatakan dalam bilangan rasional hanya akan memberikan hasil dalam bilangan rasional ...
Adegan sederhana, jejak jalan yang dilakukan oleh aritmatika rasional. Ini menggunakan sistem angka floating- point , bukan angka floating- point .Pertama, bilangan rasional adalah bilangan yang dapat dinyatakan sebagai rasio dua bilangan bulat, misalnya 1/2 atau 355/113. Kedua, "operasi rendering normal", seperti tes kotak pembatas, memeriksa persimpangan sinar dengan segitiga, pantulan sinar, dll., Didasarkan pada produk vektor dan skalar, serta pembagian skalar (ini termasuk mengoordinasikan transformasi dan inversi matriks, angka empat, dll.), yang pada gilirannya didasarkan pada empat operasi dasar: penambahan, pengurangan, perkalian, dan pembagian. Saat menambahkan, mengurangi, mengalikan dan membagi angka rasional, angka rasional juga diperoleh. Ahli matematika akan mengatakan bahwa banyak bilangan rasional membentuk bidang yang ditutup di bawah empat operasi aritmatika dasar. Bagi kami, ini berarti bahwa jika kita mematuhi bilangan rasional secara eksklusif, maka kita dapat benar-benar beralih dari data input adegan 3D ke gambar yang diberikan sepenuhnya tanpa meninggalkan dunia bilangan rasional.
Pengecualian untuk aturan "tindakan pada bilangan rasional memberikan bilangan rasional" adalah akar kuadrat dan fungsi trigonometri / transendental. Adapun yang terakhir, saya selalu mengatakan bahwa jika Anda harus melakukan perhitungan trigonometri di interior geometri penyaji Anda, maka kemungkinan besar Anda melakukan sesuatu yang salah (dan saya menunjukkan
cara memperbaiki kasus yang paling standar ) [
terjemahan tentang Habré]. Adapun akar kuadrat, dengan pengecualian bagian kerucut (bola, silinder, dll.) Dan melakukan peneduhan / DFOS / pewarnaan, tidak perlu untuk menormalkan sinar dan normal ke permukaan sesering yang biasanya dilakukan. Itu tentu tidak perlu dilakukan untuk membuat sinar, lintasan, persimpangan, refleksi, dll. Sayangnya, sangat sering saya melihat bahwa pemrogram menormalkan nilai-nilai tanpa alasan selain "baik, saya tidak tahu, saya melakukannya sehingga saya bisa memainkannya dengan aman." Dalam praktiknya, di bagian render di mana geometri dilacak, sangat jarang diperlukan untuk menormalkan nilai-nilai, jadi saya memiliki harapan bahwa Anda dapat melacak seluruh adegan tanpa meninggalkan dunia angka rasional - inilah yang saya sebut "rendering rasional".
Untuk menerapkannya, saya perlu membuat sistem angka berdasarkan angka rasional yang dapat digunakan komputer. Kemudian di atasnya, saya bisa menerapkan algoritma penelusuran jalur biasa, menghitung gambar tanpa kehilangan keakuratan, melakukan pemeriksaan coplanarity yang memiliki jawaban akurat, dan membuat semua siswa yang mempelajari grafik komputer senang.
Artikel ini adalah kisah tentang dua malam penelitian tentang realisme ide semacam itu. Saya akan berbicara tentang banyak aspek yang saya pelajari, tentang apa yang saya hasilkan dan tentang beberapa kejutan yang saya temukan dalam proses itu. Artikel ini ditulis dalam urutan kronologis pekerjaan saya. Selain itu, ditulis dengan gaya informal dan sangat tidak ilmiah (yang saya banggakan). Gambar yang ditunjukkan di atas adalah semacam spoiler, tetapi baca artikel sampai akhir, karena saya akan berbicara tentang yang baik dan yang buruk.
Persiapan
Hal pertama yang saya lakukan adalah untuk menerapkan di
Shadertoy pelacak
minimal terbatas untuk adegan yang
sangat sederhana yang terdiri dari pesawat, bola, paralelepiped persegi panjang dan segitiga - blok bangunan penyaji nyata. Kemudian saya menyalin kode ke file C ++ dan, setelah membuat beberapa perubahan kecil, mengkompilasinya menggunakan kerangka
piLibs saya. Jadi untuk perbandingan, saya mendapatkan gambar yang dilacak yang diberikan ke CPU menggunakan angka reguler sesuai dengan standar IEEE754 dengan floating point. Saya juga menghapus semua normalisasi ray dari kode jejak, karena, sebagaimana disebutkan di atas, tidak ada satupun yang benar-benar diperlukan. Biarkan saya mengingatkan Anda bahwa akar kuadrat diperlukan untuk normalisasi, dan bilangan rasional tidak dipertahankan ketika digunakan (akar kuadrat dari bilangan rasional bukan bilangan rasional). Beberapa saat kemudian kita akan melihat bahwa masih dimungkinkan untuk menerapkan akar kuadrat, tentu saja, saya hanya ingin membuat kode sebersih mungkin untuk melihat sejauh mana saya bisa pergi dengan aritmatika yang tepat dari bilangan rasional tanpa pembulatan.
Langkah persiapan terakhir - saya mengambil semua vec3, mat4x4 dan kelas dasar aljabar / matematika, dan kemudian mengubahnya sehingga mereka menggunakan rasional alih-alih mengapung. Karena struktur rasional saya membebani semua operator standar (tambah, sub, mul, div, pembalikan tanda, perbandingan, dll.), Penggantian terjadi tanpa masalah. Saya segera mengimplementasikan sisa operasi biasa (abs, sign, mod, fract, floor, sqrt, dll.), Yang secara teoritis cukup untuk mendapatkan rendering rasional yang indah.
Tes 1 - Solusi Naif
Tapi mari kita lihat seperti apa implementasi pertama ini. Awalnya saya selalu mencoba yang paling sederhana, dan kemudian saya melihat hasilnya. Dan cara paling sederhana untuk menerapkan nilai-nilai rasional adalah dengan menggunakan dua bilangan bulat. Seperti yang disarankan oleh nama bagian ini, ini bukan keputusan akhir saya, tetapi untuk upaya pertama itu adalah keputusan yang masuk akal. Jadi, setiap angka
x harus direpresentasikan sebagai pembilang
N dan penyebut
D , membentuk nilai
N /
D. Nilai
x didekati dengan pasangan
N /
D terbaik (dalam kedalaman bit yang ditentukan), yang paling dekat dengan nilai
x yang sebenarnya. Saya memutuskan bahwa kedua angka harus positif, dan tanda nomor tersebut harus disimpan dalam bit yang terpisah untuk menyederhanakan pekerjaan dan menghilangkan ambiguitas, meskipun ini tidak terlalu penting. Pada tahap ini, baik pembilang dan penyebut bertipe unsigned. Tetapi bahkan ketika memisahkan tanda,
N /
D memiliki banyak redundansi: misalnya, 1/4 dan 7/28 menunjukkan angka yang sama, tetapi memiliki representasi bit yang sama sekali berbeda. Kita akan membahas ini nanti, tetapi untuk sekarang, jangan memfokuskan perhatian kita dan melihat bagaimana empat operasi aritmatika dasar terlihat dalam bentuk rasional ini.
Pertama, perhatikan bahwa mengurangi
a -
b hanyalah penambahan
a dan nilai yang berlawanan dengan
b , yaitu,
a + (
-b ), di mana
-b dapat dihitung dengan hanya mengganti tanda
b . Demikian pula, membagi
a /
b sama dengan mengalikan
a dan kebalikan dari
b . Atau, dengan kata lain,
a /
b =
a · (1 /
b ), di mana (1 /
b ) dapat dihitung dengan hanya mengubah tempat-tempat pembilang
b dan penyebut
b dari angka
b . Jadi, di sini adalah properti menarik pertama dari aritmatika rasional - divisi dan multiplikasi memiliki biaya yang sama, oleh karena itu, tidak seperti rendering floating point yang biasa, di mana divisi biasanya dihindari, ditunda atau disembunyikan di bawah keterlambatan permintaan tekstur lambat, tidak perlu takut operasi ini dalam aritmatika rasional .
Kami beralih ke penjumlahan dengan perkalian: kami tahu bahwa nilai kebalikan dan kebalikannya mudah dihitung, jadi kami mendapatkan:
Pelestarian tanda selama perkalian adalah sepele, hanya xor, karena dua nilai positif memberikan hasil positif, serta dua yang negatif. Menyimpan tanda untuk penambahan adalah proses yang lebih rumit, dan untuk solusi cepat saya menerapkannya melalui tiga cabang (penambahan itu sepele jika tanda
a dan
b bertepatan, tetapi ketika mereka tidak cocok, maka Anda perlu memilih jumlah yang lebih kecil dan mengurangi dari yang lebih besar - dalam artikel Saya akan menjelaskan detail sekecil itu dengan lebih detail, tetapi hanya lay out kode sumber di suatu tempat).
Saya juga akan melewatkan implementasi fract () dan floor (); jika Anda memutuskan untuk mencoba menerapkannya sendiri, Anda akan melihat kesederhanaan dan keindahannya. Perhatian juga harus diberikan kepada operator pembanding. Setelah merawat tanda-tanda dan dengan asumsi bahwa
a dan
b positif, kita dapat
Penting untuk dicatat di sini bahwa bahkan untuk perbandingan kita memerlukan beberapa operasi multiplikasi, yang dapat mengarah pada transisi ke ukuran kata berikutnya dan akan menjadi penting sedikit lebih rendah.
Akhirnya, kita melihat akar kuadrat dalam bagian yang terpisah, mengetahui bahwa sebagian besar kita tidak membutuhkannya (kecuali untuk bola dari tes pertama ini).
Ini cukup untuk menjalankan render pertama dan melacak adegan uji (bidang + bola + segitiga + kotak persegi panjang) untuk melihat apa yang terjadi. Saya dengan murah hati menggunakan bilangan rasional 65-bit untuk tes pertama ini, yang sebenarnya mewakili sejumlah besar data (sebanding dengan tipe data "ganda"): 32 bit diambil oleh pembilang, 32 bit adalah penyebut, dan bit lainnya adalah tanda. Yang pertama adalah gambar yang diperoleh dengan pendekatan naif ini, yang kedua adalah gambar yang dibuat menggunakan angka floating point (referensi):
"Naif" angka rasional 65-bitReferensi titik mengambangHasilnya sangat buruk, kotak dan segitiga bahkan tidak muncul di render, dan bidang dan bidang lantai terlalu berisik. Masalahnya, tentu saja, adalah bahwa setiap kali bilangan rasional saya melakukan operasi aritmatika dasar pada salah satu tahap algoritmik rendering, pembilang dan penyebut menjadi semakin tidak terkendali, karena penggandaan bilangan bulat digunakan. Pikirkan hal-hal berikut: jika unit dunia awal kita adalah meter, dan kita akan mengikat geometri sumber (simpul dan kamera) dengan akurasi milimeter, maka hanya data sumber yang akan menempati volume 16-bit untuk adegan yang agak kecil. Pada saat yang sama, dengan resolusi layar HD standar dan penghalusan 4X, angka arah sinar rasional akan dengan mudah membutuhkan 12 bit. Artinya, selama interaksi pertama balok dan geometri, operasi aritmatika yang paling sederhana, menggunakan kedua set data input, akan mengubah hasilnya menjadi panjang 28-bit - cukup dekat dengan batas 32-bit yang saya tetapkan untuk diri saya sendiri dalam implementasi pertama ini. Dan ini bahkan sebelum kami menampilkan produk skalar atau vektor yang pertama. Pada saat produk skalar selesai, pemberi render akan membutuhkan bilangan rasional yang panjangnya ratusan bit untuk mewakili bilangan. Tentu saja, ini adalah kasus terburuk, tetapi kasus rata-rata akan dekat dengan ini. Menimbang bahwa saya hanya mengalokasikan kapasitas 32-bit untuk pembilang dan penyebut, mudah untuk memahami seberapa cepat nilai melampaui batas dalam tes ini - tidak mengherankan bahwa dengan pengecualian bidang lantai dan bagian bola, hampir tidak ada yang terlihat.
Tes 2 - Pengurangan oleh faktor umum terbesar
Kemudian saya memperbaiki sistem dengan menggunakan properti yang saya sebutkan secara singkat di atas - angka rasional yang berbeda dapat berarti jumlah yang sama. Dan pada kenyataannya, 6/12 adalah nilai yang sama dengan 1/2, tetapi menggunakan lebih banyak bit daripada yang terakhir. Oleh karena itu, idenya adalah sebagai berikut: jika setelah setiap operasi aritmatika dasar (atau setelahnya) saya akan mengekstrak semua pembagi umum dari pembilang dan penyebut, dan membawa pecahan ke bentuk yang paling sederhana, maka mungkin saya akan dapat menjaga semuanya terkendali dan melanjutkan operasi lebih lama dengan aritmatika yang tepat tanpa kehilangan keakuratan. Mungkin Anda bisa melakukan ini cukup lama untuk mendapatkan gambar yang bersih dan dirender? Saya akan mengambil penyimpangan kecil untuk menunjukkan contoh lain: 588/910 dapat disederhanakan menjadi 42/65, karena 14 adalah pembagi 588 dan 910. Tetapi untuk menyimpan 42/65, jelas, lebih sedikit bit yang dibutuhkan daripada 588/910. Menemukan nomor terbesar yang mungkin secara bersamaan membagi dua angka lainnya dapat dilakukan dengan menggunakan algoritma Great Common Divisor (GCD), implementasi efektif yang dapat Anda temukan di mana saja (saya secara pribadi menyalinnya langsung dari Wikipedia dan mempercepatnya sedikit dengan melakukan langkah pemindaian bit menggunakan operasi x64 internal). Jadi, dipersenjatai dengan algoritma GCD, kelas rasional saya harus terus menyederhanakan fraksi yang dihasilkan selama proses rendering. Ini bisa dilakukan dengan dua cara:
Yang pertama adalah mengonversi hasil antara dari operator penambahan dan multiplikasi ke tipe data bit berikutnya (dalam solusi naif saya saat ini adalah uin64_t), cari GCD dalam tipe data yang lebih banyak ini, dan kemudian kurangi hasilnya menjadi panjang bit asli (32). Cara kedua adalah menganalisis bagaimana
suatu n ,
a ,
d ,
b , dan
b d digabungkan satu sama lain dalam operator aritmatika dan mengekstrak pembagi umum dari mereka sebelum melakukan penggandaan. Pendekatan kedua pada dasarnya menghilangkan kebutuhan akan panjang bit yang besar. Mengetahui bahwa mungkin perlu menggunakannya, saya memutuskan untuk memilih metode pertama, karena lebih mudah untuk diterapkan dan memungkinkan saya untuk mempercepat pekerjaan saya (malam hari terbang sangat cepat). Setelah melakukan semua ini, mari kita lihat render apa yang dapat saya buat sekarang:
Angka rasional 65-bit dikurangi oleh GCDReferensi titik mengambangJauh lebih baik! Sejauh ini, jauh dari ideal, tentu saja, tetapi terlihat menjanjikan. Saya membuat kotak dan segitiga muncul, dan bola sekarang tampak jauh lebih tebal. Namun, artefak lucu muncul di sudut kanan atas, dan bilangan rasional untuk banyak piksel masih melampaui batas, yang mengarah ke banyak titik dalam gambar. Namun, perlu dicatat bahwa untuk beberapa (banyak) piksel, saya mulai mendapatkan hasil yang
akurat dan sempurna! Yaitu, pelacak menemukan persimpangan titik dan jarak yang secara matematis akurat, yang merupakan akar penyebab mencoba menggunakan bilangan rasional.
Sebelum melanjutkan ke langkah berikutnya dalam proses membuktikan penerapan bilangan rasional, saya ingin berhenti sebentar dan membagikan temuan saya mengenai GCD dan pengurangan bilangan rasional.
Penemuan pertama terkait dengan volume bit bilangan rasional. Meskipun saya masih tidak dapat membuat gambar yang indah dan ini lebih penting daripada khawatir tentang mengoptimalkan volume data, dan meskipun implementasi awal ini masih menggunakan banyak bit (1 + 32 + 32), saya sudah memikirkan tentang limbah yang disebutkan sebelumnya bit dalam bentuk pecahan berlebih. Secara khusus, setelah menambahkan tahap dengan GCD, kombinasi bit seperti 2/4 tidak lagi berlaku, karena mereka secara otomatis dikurangi menjadi 1/2 sebelum menulis ke register atau variabel apa pun. Artinya, dalam arti tertentu, dari semua 2 kombinasi bit yang bisa menjadi pembilang dan penyebut, banyak yang tetap tidak digunakan. Dan Anda tidak dapat membuang bit seperti itu. Atau mungkinkah? Berapa banyak ruang yang sebenarnya saya hilangkan? Saya melakukan sedikit penyimpangan untuk mengeksplorasi masalah ini.
Digresi - Pada Bilangan Saling Utama
Ilustrasi di bawah ini menunjukkan penggunaan bit untuk bilangan rasional dalam 5/5 bit dan 7/7 bit. Sumbu horizontal dan vertikal grafik mewakili nilai pembilang dan penyebut semua bilangan rasional yang memungkinkan memiliki pembilang dan penyebut hingga 5 bit (31) dan 7 bit (127). Piksel hitam adalah kombinasi yang tidak digunakan, dan piksel putih adalah pecahan yang digunakan. Misalnya, seluruh diagonal berwarna hitam, kecuali untuk 1/1 piksel, karena semua fraksi dari bentuk n / n dikurangi menjadi 1/1.
Menggunakan bit untuk 5/5 rasional
Menggunakan bit untuk 7/7 rasionalJika Anda menghitung piksel, seperti yang saya lakukan, maka Anda dapat dengan cepat memahami bahwa proporsi piksel bermanfaat dengan peningkatan jumlah bit cenderung 60,8%. Sebuah riset online kecil menunjukkan kepada saya bahwa rasio ini ternyata tepat 6 / π
2 , karena ini juga merupakan probabilitas menjadi relatif prima (tidak memiliki pembagi umum) untuk dua angka acak. Anda mungkin bertanya, dari mana pi itu berasal? , « „“ » — , ,
- , 2, 1/ζ(2). , - .
, , 40% . , , … . , , , , , . - - -, , , . ,
.
, : , . , — (, , ), «» , , . , . , , , . . .
, — - , , . , 16/16- , , 16/16 ++ .
3 —
, . , .
, , , , , ( , — , . , , , ).
, , , - . , , . , , , ,
. .
Dalam implementasi pertama saya, saya melihat jumlah bit yang diperlukan untuk pembilang dan penyebut, mengambil maksimum untuk keduanya, dan menggeser keduanya dengan jumlah bit ini (membulatkan ke bilangan bulat terdekat). Ketika ini diterapkan pada operator penjumlahan dan multiplikasi, semuanya mulai terlihat cukup dapat diterima:Angka rasional 65-bit dikurangi oleh GCD dan normalisasi, . 32/32 (65 ) 16/16 (33 ), ! , , . , . .
4 —
Pada tahap ini, saya memutuskan untuk mengalihkan perhatian dan berhenti mencari alasan - jika saya ingin menemukan sesuatu yang menarik untuk dirender dalam bilangan rasional, maka mereka harus menempati 32 bit dan tidak lebih. Lebih baik menemukan ide yang bagus atau berhenti, dan akhiri di sana (ini adalah awal dari eksperimen malam kedua)., , . , — , . , , . , , . . , , «» . . 16/16, 32- 16/16, 5/27 13/19, .
Itu layak untuk dicoba. Bagaimanapun, beberapa baris kode pengemasan / pembongkaran di setter internal dan getter dapat ditulis dengan cepat. Skema yang paling logis bagi saya sepertinya 1 | 5 | 26, yaitu:1 bit: tanda
5-bit: posisi garis fraksi (B)
26-bit: data pembilang dan penyebut gabungan; pembilangnya adalah bit 26-B atas, penyebutnya adalah bit B lebih rendah,
di mana bilangan pecahan (B) menentukan ukuran penyebut. Misalnya, angka 7/3 akan ditulis sebagai7/3 = 0 00010 000000000000000000000111 11,
0 , 2 ( 3), 2 , .
, IEEE754, : «1», . . «3» «1» «1»:
7/3 = 0 00001 0000000000000000000000111 1
, : , , 1 . , , 2
26 , . ! , «rational», , — , («int» «float») ! , «int» «rational». , .
, :
32- (1|5|26)32- --, ! - , , - . . , , , , . ( ), , .
( — ). ( ) , GPU :
https://www.shadertoy.com/view/Xd2fzR .
C++, . :
32- 32-bit floating point standarWow, ini sangat bagus! Meskipun kebocoran cahaya terlihat jelas di sudut-sudut di mana tepi lantai dan langit-langit terhubung. Lihatlah mereka dalam perkiraan:
Mungkin mereka disebabkan oleh masalah dalam implementasi saya dari persimpangan sinar dan kotak persegi panjang, yang hanya dinyatakan dalam bilangan rasional; Saya tidak akan terkejut. Atau mungkin saya berlari ke batas-batas apa angka rasional mampu. Namun, saya cukup senang. Selain itu, saya memiliki perubahan dan percobaan lain yang ingin saya uji untuk waktu singkat yang tersisa:Beberapa eksperimen lain
Aritmatika yang tepat dalam 64 bit
64- , 32- (1|5|26) . 64- ?
1|6|57 ( x64 ). 57 / .
( , ). ! , , , . , , «» . . , , 64 , . : - , , , ? , «» ? , .
() . . (
) ( ), . — , , . . .
: ,
x y , ,
() («» , ):
Setelah mencari di Wikipedia, saya menemukan bahwa persamaan khusus ini disebut "persamaan Pell yang Dimodifikasi". Ada algoritma yang menemukan nilai
x dan
y terkecil untuk menyelesaikan persamaan ini. Sayangnya, perhatian saya dengan cepat beralih ke matematika Diophantine lain yang penasaran, dan saya tidak melanjutkan penerapan salah satu dari algoritma ini.
Pengurangan yang lebih efektif
Pada menit-menit terakhir malam itu, saya berpikir tentang mengeksplorasi ide menggunakan banyak anggota yang bergabung dalam operator geometris yang kompleks, misalnya, dalam produk vektor. Katakanlah komponen pertama dari produk vektor adalah
dengan asumsi bahwa sy = a / b, tz = c / d, ty = e / f, sz = g / h
Ini berarti bahwa sekarang saya dapat mencoba menemukan pembagi umum, misalnya, antara a dan d, atau e dan h, dan menggunakannya untuk pengurangan awal.
Saya punya ide lain: jika pada tahap tertentu kecepatan rendering menjadi masalah, maka Anda dapat sepenuhnya menonaktifkan langkah-langkah mencari GCD dan hanya menerapkan normalisasi. Pemeriksaan cepat menunjukkan bahwa dalam kasus ini, gambar yang dihasilkan masih tetap dapat diterima dan bekerja dengan baik pada kecepatan yang jauh lebih tinggi. Namun, dalam kasus ini, tentu saja, kami mendapatkan hasil yang lebih akurat sedikit.
Sebagai kompromi, Anda dapat menolak untuk menerapkan prosedur atau skema GCD, dan menggunakan sesuatu yang sederhana secara matematis, sulit dikodekan dalam kode dan efektif, menentukan pembagian dengan hanya 2, 3, dan 5. Meskipun kami tidak akan menemukan jumlah pembagi yang lengkap, oleh dalam praktiknya, ini akan mengarah pada menemukan sejumlah besar singkatan. Pikirkan tentang hal ini - keterbagian dengan 2 terjadi tiga kali lebih sering daripada dibagikan dengan 7, dan 20 kali lebih sering daripada dibagi dengan 41!
Kesimpulan
Setelah percobaan ini, saya mulai percaya bahwa representasi bilangan mungkin didasarkan pada bilangan rasional, mirip dengan apa yang saya sebut "fraksi garis mengambang". Representasi yang kompatibel dengan bilangan bulat dan mampu melakukan banyak operasi dalam aritmatika yang tepat untuk banyak tugas (asalkan data input disajikan dalam bentuk rasional). Versi 64-bit (1 | 6 | 57) memiliki potensi besar, meskipun versi 32-bit (1 | 5 | 26) telah menciptakan rendering yang menarik.
Jika itu bukan percobaan untuk dua malam, tetapi sesuatu yang profesional dibuat di studio atau perusahaan, maka di masa depan langkah-langkah berikut dapat diambil:
* Dapatkan histogram jumlah piksel yang akurat dan tidak terlacak (dengan kata lain, frekuensi eksekusi normalisasi)
* Cobalah untuk menerapkan pengurangan kode-keras pada pembagi 2, 3, dan 5 dan mengukur persentase piksel yang tepat yang hilang
* Tampilkan perbedaan piksel antara rendering titik mengambang dan rendering titik mengambang fraksi
* Temukan cara cerdik untuk menggunakan nilai yang tidak digunakan dari format bit "pecahan garis mengambang", misalnya, untuk menunjukkan Inf dan NaN
* Menerapkan deteksi NaN, Inf, underflow, overflow.
Secara keseluruhan, ini adalah studi yang menarik. Dalam prosesnya, saya menemukan beberapa kejutan, muncul dengan satu penemuan kecil dan belajar banyak tentang persamaan Pell, akar kuadrat, GCD, mekanisme internal x86_64, fungsi zeta Riemann dan beberapa aspek lainnya. Saya sangat senang dengan ini!