Blue Caterpillar: Ya, Anda tidak akan mengecewakan kami. Kita duduk, kita tahu: mereka menunggu transformasi kita. Apa? Tapi tidak ada apa-apa! Kami duduk, merokok, tunggu ...
Boneka Alice: Apa?
Blue Caterpillar: Apa, mengapa! Transformasi. Rumah menjadi asap, asap menjadi wanita, dan wanita menjadi seorang ibu. Itu dia. Jangan ikut campur, jangan melompat maju, jika tidak Anda sendiri akan berubah menjadi kupu-kupu.
Melihat melalui kode di salah satu forum yang didedikasikan untuk Arduino, saya menemukan cara yang menyenangkan untuk bekerja dengan angka floating point (PT). Nama umum kedua untuk angka dalam format ini adalah floating point, tetapi singkatan yang dihasilkan (PZ) secara pribadi menyebabkan asosiasi yang sangat berbeda bagi saya, jadi kami akan menggunakan opsi ini. Kesan pertama (dari kode yang terlihat) adalah jenis sampah apa yang ditulis di sini (saya harus mengatakan bahwa yang kedua adalah sama, meskipun ada nuansa, tetapi lebih banyak tentang itu nanti), tetapi pertanyaan muncul - bagaimana ini benar-benar perlu - jawaban yang diberikan dalam teks selanjutnya.
Bagian Satu - Mempertanyakan
Kami merumuskan masalah - kami perlu mencetak ke konsol (berubah menjadi representasi simbolis) angka floating-point, tanpa menggunakan opsi cetak, yang dimaksudkan untuk tujuan ini. Mengapa kita ingin melakukan ini sendiri -
- menggunakan format% f mencakup menghubungkan pustaka untuk bekerja dengan floating point dan versi yang diperluas dari fungsi prntf (atau lebih tepatnya, membuatnya tidak mungkin untuk menggunakan versi terpotongnya), yang mengarah pada peningkatan signifikan dalam ukuran modul yang dapat dieksekusi,
- solusi standar membutuhkan waktu yang lama (selalu bekerja dengan angka presisi ganda), yang mungkin tidak dapat diterima dalam situasi khusus ini,
- Yah (terakhir, tapi tidak kalah pentingnya), itu hanya menarik.
Untuk memulai, pertimbangkan opsi yang diusulkan dalam materi di atas, seperti:
for (float Power10=10000.0; Power10>0.1; Power10/=10.0; ) {char c=(int)(Fdata/Power10); Fdata -=Power10*c; };
dan kami setuju bahwa ia sepenuhnya menyelesaikan masalah. Selain itu, ini bukan pilihan yang buruk, karena kecepatannya dapat diterima. Mari kita melihat lebih dekat pada saat ini - kita melihat pembagian angka PT, tetapi jika kita menyelidiki lebih dalam esensi masalah, ternyata hampir secepat pembagian bilangan bulat dari kedalaman bit yang sesuai. Bahkan, sebelum mengevaluasi kinerja algoritma, Anda harus mengevaluasi kinerja berbagai operasi dasar, yang akan kami lakukan.
Bagian Dua - Evaluasi Kinerja Operasi Dasar
Operasi pertama yang menarik adalah penambahan (pengurangan, dalam arti waktu yang dihabiskan, mereka setara) dari bilangan bulat dan kita dapat mengasumsikan bahwa dibutuhkan satu unit waktu (clock cycle) dengan peringatan berikut - ini hanya berlaku untuk data "asli". Misalnya, untuk AVR seri MK, ini adalah kata 8-bit, untuk MSP430 itu adalah kata 16-bit (dan, tentu saja, lebih kecil), untuk Cortex-M itu adalah kata 32-bit, dan seterusnya. Maka operasi penambahan angka dengan panjang H kali lebih banyak dari yang asli dapat diperkirakan sebagai siklus H. Ada pengecualian, misalnya, AddW di pengontrol AVR, tetapi itu tidak membatalkan aturan.
Operasi selanjutnya adalah penggandaan bilangan bulat (tetapi bukan pembagian, ini berbeda dalam hal kecepatan) dan baginya tidak semuanya begitu sederhana. Pertama-tama, perkalian dapat diimplementasikan dalam perangkat keras dan, misalnya, dalam AVR MEGA memerlukan 2 siklus clock, dan dalam peningkatan sebanyak 51 (untuk mengalikan angka asli).
Tetapi pertimbangkan kasus ketika tidak ada implementasi perangkat keras dan kami harus mengimplementasikan perkalian dalam bentuk subrutin. Karena ketika mengalikan angka bit H, sebuah produk bit 2H diperoleh, maka estimasi versi klasik dengan shift dapat ditemukan sebagai berikut: kita membutuhkan pergeseran faktor H dengan siklus 1 jam per shift, H bergeser dari faktor kedua dengan panjang 2 H dengan 2 siklus clock per shift, kemudian H akan membuat keputusan dan , rata-rata, penambahan N / 2 angka dengan panjang 2H, sebagai kesimpulan, organisasi dari siklus 2 langkah. Total + 2 + + 2 / 2 + 2 = 7 ticks, dan benar-benar melakukan operasi aritmatika darinya hanya membutuhkan tick (wow efisiensi, walaupun kami berhasil menyiasati mesin).
Yaitu, untuk mengalikan dua angka 8p dengan 8p MK, diperlukan 56 siklus, dan untuk mengalikan angka 16p sudah ada 112 siklus (sedikit lebih sedikit, tetapi kami mengabaikan nilai persisnya) siklus, yang agak lebih dari yang kita inginkan. Untungnya, arah pergeseran dapat dimodifikasi dan ada cara penggandaan yang unik, yang hanya akan membutuhkan pergeseran H dari jumlah 2H digit dan penambahan H / 2 angka asli, yang meningkatkan waktu operasi dari algoritma perkalian menjadi 0 + 2 + 1 + 1/2 + 2 = 5.5 - tentu saja, itu tidak dapat dibandingkan dengan implementasi perangkat keras, tetapi setidaknya beberapa keuntungan tanpa kehilangan fungsionalitas. Ada peningkatan pada algoritma ini, misalnya, analisis 2 bit per siklus, tetapi mereka tidak mengubah situasi secara drastis - waktu penggandaan dengan perintah besarnya melebihi waktu penambahan.
Tetapi dengan pembagian, situasinya lebih buruk - bahkan divisi yang diimplementasikan perangkat keras kehilangan hampir dua kali lipat dari perkalian, dan ada MK dengan perkalian perangkat keras, tetapi tanpa divisi perangkat keras. Dalam kondisi tertentu, pembagian dapat diganti dengan perkalian dengan timbal balik, tetapi kondisi ini spesifik dan memberikan hasil yang serupa - dua iterasi perkalian diperlukan diikuti oleh jumlah, sehingga ada kerugian 2 kali lipat. Jika kita menerapkan pembagian sebagai subprogram, maka N pergeseran pembagi 2H panjang, H pengurangan dari panjang 2H yang dapat dibagi, H bergeser dari hasilnya, organisasi siklus 2H diperlukan, tetapi semua ini didahului oleh penyelarasan, yang akan mengambil siklus 5H lainnya, sehingga total angka adalah 2 + 2 + 1 + 2 + 5 = 12, yaitu sekitar 2 kali lebih buruk daripada perkalian.
Nah, sekarang kita akan mempertimbangkan operasi PT, dan di sini situasinya agak paradoks - operasi penggandaan membutuhkan waktu sebanyak untuk bilangan bulat (sesuai dengan kapasitas bit, sebagai aturan, 24 bit), karena kita harus melipatgandakan mantissa dan hanya menambahkan pesanan, normalisasi tidak diperlukan. Dengan pembagian juga bagus, bagikan mantissa dan kurangi pesanan, normalisasi sekali lagi tidak diperlukan. Oleh karena itu, untuk dua operasi ini, kerugian dibandingkan dengan bilangan bulat tidak terlalu signifikan, meskipun tidak ada tempatnya.
Tetapi operasi penambahan dan pengurangan membutuhkan, pertama-tama, penyelarasan pesanan (dan ini adalah pergeseran dan mungkin ada banyak, meskipun ada nuansa), maka operasi itu sendiri, dan (saat pengurangan) normalisasi (ketika menambahkan, juga, tetapi tidak lebih dari 1 shift) ), yang boros dalam waktu, oleh karena itu operasi kelas ini untuk PT jauh lebih lambat daripada untuk bilangan bulat, terutama dalam hal relatif.
Mari kita kembali ke domba-domba kita dan setuju bahwa, berdasarkan perkiraan sebelumnya, metode yang diusulkan mungkin tidak terlalu lama, terutama karena langsung memberikan hasilnya, tetapi memiliki batasan yang signifikan - itu berlaku untuk rentang nilai input PT yang sangat terbatas. Oleh karena itu, ia akan mencari solusi universal (kurang lebih).
Segera buat reservasi bahwa solusi kami tidak boleh menggunakan operasi floating-point secara umum (dari kata sama sekali) untuk menekankan manfaat dari opsi kami. Dan untuk pertanyaan bingung tentang bagaimana maka sejumlah jenis ini akan muncul jika operasi tidak tersedia, kami menjawab - mungkin muncul, misalnya, ketika membaca informasi dari sensor cahaya (seperti pada contoh asli), yang menghasilkan data dalam format PT.
Bagaimana tepatnya jumlah PTs diatur, Anda dapat dengan mudah menemukan di banyak situs, ada artikel terbaru tentang Habré, seharusnya tidak ada masalah dengan ini. Namun demikian, sejumlah pertanyaan menarik untuk format PT dengan gaya “jika saya adalah sutradara” - mengapa demikian, dan bukan sebaliknya. Saya akan memberikan jawaban saya kepada beberapa dari mereka, jika ada yang tahu lebih benar, silakan komentar.
Pertanyaan pertama adalah mengapa mantissa disimpan dalam kode langsung dan bukan dalam kode tambahan? Jawaban saya adalah karena lebih mudah untuk bekerja dengan mantissa yang dinormalisasi dengan bit (opsional) yang tersembunyi.
Pertanyaan kedua adalah mengapa pesanan disimpan dengan offset, dan bukan sebaliknya? Jawaban saya adalah karena dalam hal ini mudah untuk membandingkan modul dari dua PTs sebagai bilangan bulat, dengan metode lain lebih rumit.
Pertanyaan ketiga adalah mengapa tanda negatif dikodekan oleh satu daripada nol, karena dengan demikian akan mungkin untuk hanya membandingkan dua titik sebagai bilangan bulat? Jawaban saya adalah saya tidak tahu, itu hanya "sangat biasa di sini".
Bagian Tiga - Penjelasan yang Diperlukan
Dalam paragraf sebelumnya, saya bisa memberikan istilah yang tidak bisa dimengerti, jadi sedikit tentang representasi angka. Tentu saja, mereka berbeda, kalau tidak, tidak perlu membahasnya. Segera, kami mencatat bahwa dalam memori MK (hal yang sama berlaku untuk komputer, meskipun saya tidak begitu kategoris tentang arsitektur paling modern - mereka sangat rumit sehingga semuanya dapat diharapkan) tidak ada angka, hanya ada unit penyimpanan dasar - bit dikelompokkan dalam byte dan selanjutnya menjadi kata-kata. Ketika kita berbicara tentang representasi angka, itu berarti bahwa kita menafsirkan set bit dengan panjang tertentu dalam satu atau lain cara, yaitu, kita menetapkan hukum yang dengannya kita dapat menemukan nomor tertentu yang sesuai dengan set bit yang diberikan, dan tidak lebih.
Tak terhitung undang-undang semacam itu dapat ditemukan, tetapi beberapa di antaranya akan memiliki sejumlah properti yang berguna dalam melakukan berbagai operasi, sehingga mereka akan lebih sering diterapkan dalam praktik. Salah satu dari sifat-sifat ini, yang tersirat secara implisit, misalnya, adalah determinisme, dan yang lainnya adalah independensi dari lingkungan - properti yang, pada pandangan pertama, jelas, walaupun ada nuansa. Properti lain dari jenis korespondensi satu-ke-satu sudah menjadi bahan diskusi dan tidak selalu terjadi dalam representasi konkret. Topik mewakili angka itu sendiri sangat luar biasa menarik, karena Knut (dalam Volume Dua) sepenuhnya diungkapkan, sehingga melampaui kedalaman, dan kita pergi ke permukaan.
Di bawah asumsi bahwa himpunan bit memiliki panjang n (kami beri nomor secara berurutan dari 0 hingga n-1) dan ditimbang secara seragam dengan langkah 2 dan bit yang paling tidak signifikan (dengan angka 0) memiliki bobot 1 (yang, secara umum, tidak diperlukan sama sekali, kami hanya Kami terbiasa dengan hal-hal seperti itu, dan mereka tampak jelas bagi kami) kami mendapatkan representasi biner dari angka, di mana rumus reduksi terlihat seperti ini: angka yang ditampilkan oleh himpunan bit
(2) = (0)*2^0 + (1)*2^1 + ... + (-1)*2^(-1) atau dalam bentuk cascaded
2() = (0)+2*((1)+2*(...+2*((-1))..))) , selanjutnya, B (k) menunjukkan sedikit dengan angka k. Perhatikan bahwa di bawah pandangan yang berbeda tidak memaksakan pembatasan pada lokasi byte nomor dalam memori, tetapi akan lebih logis untuk menempatkan byte rendah di alamat yang lebih rendah (ini adalah cara mudah dan alami saya menyelesaikan "argumen abadi Slavia di antara mereka sendiri" mengenai ujung mana yang lebih nyaman untuk memecahkan telur).
Dengan interpretasi ini dari sekumpulan bit dengan panjang n (= 8), kami mendapatkan representasi untuk angka dari 0 hingga (2 ^ n) -1 (= 255) (selanjutnya dalam kurung akan ada nilai spesifik untuk satu set 8 bit), yang memiliki jumlah yang luar biasa dan sifat-sifat yang bermanfaat, itulah sebabnya ia menjadi tersebar luas. Sayangnya, ia juga memiliki sejumlah kelemahan, salah satunya adalah bahwa kita tidak dapat mewakili angka negatif dalam catatan seperti itu secara prinsip.
Anda dapat menawarkan berbagai solusi untuk masalah ini (representasi angka negatif), di antaranya ada juga kepentingan praktis, mereka tercantum di bawah ini.
Representasi dengan offset dijelaskan oleh rumus H = N2 (n) - offset (C), di mana N2 adalah angka yang diperoleh dalam notasi biner dengan n bit, dan C adalah beberapa nilai yang dipilih sebelumnya. Kemudian kami mewakili angka dari 0-C hingga 2 ^ (n) -1-C, dan jika kami memilih C = 2 ^ (n-1) -1 (= 127) (ini sepenuhnya opsional, tetapi sangat nyaman), maka kita mendapatkan rentang dari 0 (2 ^ (n-1) -1) (= - 127) hingga 2 ^ (n-1) (= 128). Keuntungan utama dari representasi ini adalah monoton (apalagi, peningkatan) selama seluruh interval, ada juga kelemahan, di antaranya kami menyoroti asimetri (ada yang lain terkait dengan kompleksitas melakukan operasi pada jumlah dalam representasi ini), tetapi para pengembang standar IEEE 457 (ini adalah standar untuk PT) mengubah kelemahan ini menjadi kebajikan (menggunakan nilai ekstra untuk menyandikan situasi nan), yang sekali lagi menekankan kesetiaan pepatah keren: "Jika Anda lebih tinggi dari lawan, maka ini adalah keuntungan Anda. Jika lawan lebih tinggi darimu, maka ini juga keuntunganmu. ”
Perhatikan bahwa karena jumlah total kombinasi yang mungkin dari sejumlah bit adalah genap (jika Anda tidak memiliki kombinasi yang dilarang karena alasan agama), maka kesimetrian antara angka-angka representatif positif dan negatif pada dasarnya tidak dapat dicapai (atau lebih tepatnya, dapat dicapai, tetapi dalam kondisi tambahan tertentu, tentang yang selanjutnya) .
Representasi dalam bentuk kode langsung ketika salah satu bit (paling signifikan) mewakili tanda yang dikodekan dari nomor H = (-1) ^ B (n-1) * P2 (n-1) memiliki rentang dari 0 (2 ^ (n-1) -1) (= -127) hingga 2 ^ (n-1) -1 (= 127). Sangat menarik untuk dicatat bahwa saya baru saja mendeklarasikan ketidakmungkinan dasar simetri, dan ini dia jelas - angka positif maksimum yang dapat diwakili sama dengan modulus angka negatif minimum yang dapat diwakili. Hasil ini dicapai dengan memiliki dua representasi untuk nol (00 ... 00 dan 10 ... 00), yang biasanya dianggap sebagai kerugian utama dari metode ini. Ini benar-benar kelemahan, tetapi tidak separah yang diyakini umumnya, karena ada yang lebih signifikan yang membatasi penggunaannya.
Representasi kode terbalik, ketika dalam representasi langsung kita membalikkan semua bit nilai untuk angka negatif H = (1-B (n-1)) * P2 (n-1) + B (n-1) * (2 ^ (n -1) -CH2 (n-1)) - ini dari definisi, Anda dapat membuat rumus yang lebih dimengerti H = Ch2 (n-1) -B (n-1) * (2 ^ (n-1) -1), yang memungkinkan kita untuk mewakili angka dari 0-2 ^ (n-1) +1 (= - 127) hingga 2 ^ (n-1) -1 (= 127). Dapat dilihat bahwa representasi ini dipindahkan, tetapi perpindahannya berubah bertahap, yang membuat representasi ini tidak monoton. Sekali lagi, kami memiliki dua nol, yang tidak terlalu menakutkan, terjadinya transfer sirkuler selama penambahan jauh lebih buruk, yang menciptakan masalah tertentu dalam implementasi ALU.
Untuk menghilangkan kelemahan terakhir dari representasi sebelumnya adalah luar biasa sederhana, itu cukup untuk mengganti offset dengan satu, maka kita mendapatkan = = 22 (n-1) -B (n-1) * 2 ^ (n-1) dan kita dapat mewakili angka dari 0-2 ^ ( n-1) (= - 128) hingga 2 ^ (n-1) -1 (= 127). Mudah untuk melihat bahwa representasi asimetris, tetapi nol adalah unik. Yang secara signifikan lebih menarik adalah properti berikut, “sangat jelas bahwa” transfer cincin tidak terjadi untuk operasi tipe tambahan, yang merupakan alasan (bersama dengan fitur menyenangkan lainnya) untuk distribusi universal metode khusus pengkodean angka negatif ini.
Kami menyusun tabel nilai menarik untuk berbagai metode pengkodean angka, yang ditunjukkan oleh H nilai 2 ^ (n-1) (128)
| Bits | 00.00 | 11/01 | 10..00 | 11.11 |
|---|
| H (n) | 0 | H-1 (127) | H (128) | 2 * H-1 (255) |
| H (n-1) | 0 | H-1 (127) | 0 | H-1 (127) |
| Offset. N | -H + 1 (-127) | 0 | 1 | H (128) |
| Langsung | 0 | H-1 (127) | 0 | -H + 1 (-127) |
| Membalikkan | 0 | H-1 (127) | -H + 1 (-127) | 0 |
| Selain itu | 0 | H-1 (127) | -H (-128) | -1 |
Nah, untuk menyimpulkan topik, kami memberikan grafik untuk representasi yang terdaftar, dari mana kelebihan dan kekurangannya segera terlihat (tentu saja, tidak semua yang membuat orang mengingat diktum yang menarik "Keuntungan dari presentasi grafis informasi adalah visual, tidak memiliki keunggulan lain").
Bagian Empat - Sebenarnya memecahkan masalah asli (lebih baik terlambat daripada tidak pernah).
Penyimpangan kecil
Untuk mulai dengan, saya ingin mencetak PT dalam format heksadesimal (dan akhirnya saya melakukannya), tetapi secara tak terduga / benar-benar tidak terduga (saya harus mengganti), saya menemukan hasil berikut. Menurut Anda apa yang akan dicetak sebagai hasil dari mengeksekusi operator:
printf("%f %x", 1.0,1.0); printf("%f %x",2.0,2.0); printf("%x %d",1.0,1.0); printf("%x %d",2.0,2.0);
, perhatikan juga konstruksi berikut dan hasilnya:
printf("%x %x %f",1.0,1.0);
Saya tidak akan memberikan penjelasan untuk fenomena ini, "cukup pintar."
Namun, bagaimana kita mencetak dengan benar representasi heksadesimal dari PT? Solusi pertama jelas - penyatuan, tetapi yang kedua adalah untuk penggemar baris tunggal printf ("% x", * ((int *) (& f))); (Saya minta maaf jika seseorang tersinggung oleh tanda kurung tambahan, tetapi saya tidak pernah, dan tidak pernah bermaksud, mengingat prioritas operasi, terutama mengingat bahwa tanda kurung tidak menghasilkan kode, jadi saya akan terus melakukan hal yang sama). Dan ini dia, solusi dari tugas - kita melihat serangkaian karakter, 0x45678, yang secara unik menentukan angka yang diinginkan untuk kita, tetapi sedemikian rupa sehingga kita (saya tidak tahu tentang Anda, saya pasti) tidak dapat mengatakan apa pun yang dapat dimengerti tentang nomor ini. Saya pikir akademisi Karnal, yang bisa menunjukkan kesalahan dalam rekaman berlubang dengan kode sumber, akan berurusan dengan tugas ini, tetapi tidak semua orang begitu maju, jadi kami akan melanjutkan.
Kami akan berusaha mendapatkan informasi dalam bentuk yang lebih mudah dipahami.
Untuk melakukan ini, kita kembali ke format PT (selanjutnya, saya hanya mempertimbangkan float), yang merupakan sekumpulan bit yang dapat Anda ekstrak (sesuai aturan tertentu) tiga set bit untuk mewakili tiga angka - tanda (s), mantissa (m) dan pesanan (p), dan nomor yang diinginkan yang disandikan oleh angka-angka ini akan ditentukan oleh rumus berikut: Cs * Chm * Chn. Di sini, simbol menunjuk angka-angka yang diwakili oleh himpunan bit yang sesuai, oleh karena itu, untuk menemukan angka yang diinginkan, kita perlu mengetahui hukum yang digunakan untuk mengekstrak ketiga himpunan ini dari himpunan bit asli, serta jenis penyandian untuk masing-masing bit.
Dalam memecahkan masalah ini, kita beralih ke standar IEEE dan menemukan bahwa tandanya adalah satu bit (senior) dari set asli dan rumus untuk pengkodean Cs = (- 1) ^ B (0). Urutan menempati 8 bit tinggi berikutnya, ditulis dalam kode dengan offset 127, dan mewakili kekuatan dua, kemudian Cn = 2 ^ (C2 (8) -127). Mantissa mengambil urutan berikutnya dari 23 digit dan mewakili angka Chm = 1 + Ch2 (23) / 2 ^ 23.
Sekarang kita memiliki semua data yang diperlukan dan kita dapat sepenuhnya menyelesaikan tugas - untuk membuat string dengan karakter, yang, dengan bacaan tertentu, akan mewakili angka yang sama dengan yang disandikan. Untuk melakukan ini, kita harus, melalui operasi sederhana, mengekstrak angka-angka di atas, dan kemudian mencetaknya, memberikan atribut yang diperlukan. Kami berasumsi bahwa kami dapat mengubah integer dengan tidak lebih dari 32 bit ke string karakter, maka ini benar-benar tidak rumit.
Sayangnya, kita hanya berada di awal perjalanan, karena beberapa pembaca posting ini dalam catatan "+ 1.625 * 2 ^ 3" mengenali angka sial, yang dikodekan oleh desimal yang lebih umum "13", dan tebak dalam catatan "1.953125 * 2 ^ 9 ”“ 1E3 ”atau“ 1 * 10 ^ 3 ”yang sederhana atau“ 1000 ”yang sangat lazim mampu unit orang secara umum, saya pasti bukan milik mereka. Aneh bagaimana hal itu terjadi, karena kami menyelesaikan tugas awal, yang sekali lagi menunjukkan betapa hati-hati Anda harus memperlakukan formulasi. Dan intinya bukan bahwa notasi desimal lebih baik atau lebih buruk daripada biner (dalam hal ini, deuce didasarkan pada derajat), tetapi kita terbiasa dengan desimal sejak kecil dan membuat ulang orang jauh lebih sulit daripada program, jadi kami akan memberikan masuk ke yang lebih akrab.
Dari sudut pandang matematika, kita memiliki operasi sederhana - ada catatan PT = (- 1) ^ s * m * 2 ^ n, dan kita perlu mengubahnya menjadi bentuk PT = (-1) s '* m' * 10 ^ n '. Kami menyamakan, mengubah, dan mendapatkan (salah satu opsi yang mungkin) solusi s '= s', m '= m, n' = n * log (2). Jika kita meninggalkan tanda kurung kebutuhan untuk dikalikan dengan angka irasional eksplisit (ini dapat dilakukan jika nomor dirasionalisasi, tetapi kita akan membicarakan ini nanti), maka masalah tampaknya akan diselesaikan sampai kita melihat jawabannya, karena jika catatannya seperti "+1.953125 * 2 ^ 9 "bagi kami tidak jelas, catatan" + 1.953125 * 10 ^ 2.70927 "bahkan lebih tidak dapat diterima, meskipun tampaknya tidak ada yang lebih buruk.
Kami terus meningkatkan solusi dan menemukan solusi berikut - persamaan reduksi ke derajat pada basis 10 m '= m * 10 ^ {n * log (2)}, n' = [n * log (2)], di mana kurung keriting dan kotak menunjukkan fraksional dan bagian integer dari angka tertentu, masing-masing. Maka untuk contoh yang dimaksud kita dapatkan (1.953125 * 10 ^ 0.7 0927) * 10 ^ 2 = "10 * 10 ^ 2", yang jauh lebih dapat diterima, meskipun tidak sempurna, tetapi sudah dapat diimplementasikan.Masalahnya kecil, kita perlu belajar:- kalikan bilangan bulat (n) dengan irasional yang sebelumnya diketahui (log (2)) (ini tidak sulit dengan pembatasan tertentu pada keakuratan hasil);
- ambil bilangan bulat dan pecahan dari angka titik tetap (ini mudah);
- untuk meningkatkan keseluruhan yang diketahui (10) ke tingkat yang tidak rasional (hmm ...);
- kalikan keseluruhan dengan irasional sewenang-wenang ("kami akan menyederhanakan perhitungan, kata mereka ...").
Namun demikian, kami akan mencoba untuk bergerak ke arah ini dan mempertimbangkan apa yang tidak sulit untuk dilakukan, yaitu poin 1. Kami segera mencatat bahwa masalah ini pada dasarnya tidak dapat diselesaikan dan kami tidak dapat menghitung n * log (2), kami tidak dapat dari kata "sepenuhnya", kecuali untuk kasus sepele n = 0 (well, dan kasus yang jelas n = k / log (10)). Pernyataan yang menarik, terutama setelah pernyataan "itu tidak sulit", tetapi kontradiksi yang tampak dihilangkan dengan frase "dengan akurasi tertentu". Artinya, kita masih bisa menghitung produk bilangan bulat sembarang dengan irasional yang diketahui dan ini tidak sulit untuk hasilnya dengan akurasi tertentu. Misalnya, jika kita tertarik pada hasil dengan akurasi satu persen, maka menyajikan hasil yang diinginkan n '= n * log (2) dalam bentuk n * [log (2) * 256 + 1/2] / 256 kita mendapatkan nilai dengan akurasi yang kita butuhkan ,karena kemungkinan kesalahan relatif tidak dapat melebihi 1/2/77 = 1/144, yang jelas lebih baik dari yang diperlukan 1/100. Satu pertimbangan penting harus diperhitungkan - nilai kecil dari deviasi relatif tidak mengatakan sama sekali tentang perilaku fungsi ketika transformasi nonlinier diterapkan, dan operasi mengambil seluruh bagian jelas nonlinier. Kami memberikan contoh sederhana [4,501] = 5, dan [4.499] = 4 dan, meskipun fakta bahwa penyimpangan relatif dalam data sumber adalah 0,002 / 4,5 = 0,04%, penyimpangan hasil akan sebanyak 1/4 = 25%. Sayangnya, secara umum, masalahnya tidak terpecahkan sama sekali, menggunakan algoritma pembulatan apa pun. Anda hanya dapat menyelesaikan kasus khusus ketika input data terbatas dan, apalagi, mengambil set nilai tetap, kemudian dengan memilih offset awal dan sudut kemiringan, Anda bisa mendapatkan yang benar-benar akurat,dalam arti pembulatan, aproksimasi.Untuk kasus kami, perkiraan ideal seperti itu adalah fungsi n '= n * 77/256.Sebelum melanjutkan dengan desain algoritma, kita harus mengevaluasi akurasi yang kita butuhkan. Karena mantissa adalah 24 bit, angka yang diwakilinya memiliki kesalahan relatif 2 ^ -24 = 2 ^ -4 * 2 ^ -20 = 16 ^ -1 * (2 ^ 10) ^ - 2 ~ (10) ^ - 1 * (10 ^ 3) ^ - 2 = 10 ^ -7, yang berarti 7 digit desimal tepat. Mengalikan dua angka 24-bit akan cukup untuk menjaga akurasi dalam kisaran ini (well, hampir cukup). Perhatikan bahwa transisi ke angka 32 bit (kedua faktor) mengurangi kesalahan relatif lebih dari 100 (256) kali, fakta ini akan berguna nantinya.Rumus akurasi paling tidak menyenangkan dalam menghitung mantissa baru dan terlihat sepertim '= m * 10 ^ {n * log (2)}Mengapa ini yang paling tidak menyenangkan - 1) ini berisi rantai perhitungan sehubungan dengan n dan kesalahan akan menumpuk, 2) ia memiliki operasi yang sangat buruk dari sudut pandang akurasi, dan ini tidak mengambil bagian fraksional, karena jika Anda melakukannya secara bersamaan dengan mengambil seluruh bagian, semuanya tidak terlalu buruk, tetapi eksponen. Jika sisa operasi adalah perkalian dan kesalahan relatif dalam kasus ini hanya dijumlahkan, dapat diprediksi dan hanya bergantung pada panjang grid bit dari representasi operan, maka semuanya sangat buruk untuk eksponen dan sangat jelas bahwa kesalahan relatif akan sangat besar untuk nilai argumen yang besar."Ya, ya, sudah jelas bahwa"q (10 ^ x) = Δ (10 ^ x) / 10 ^ x = (10 ^ (x + Δx) - 10 ^ x) / 10 ^ x = 10 ^ Δx -1 = 10 ^ (x * qx) -1,10 ^ (x * qx)> ~ 10 ^ (x * 0) + (10 ^ (x * 0)) '* qx = 1 + x * ln (10) * 10 ^ (0) * qx = 1 + x * ln (10) * qx,dari sini kita dapatkan
Apa arti ungkapan ini adalah bahwa pada batas kisaran nilai, dengan n = 127, kesalahan relatif akan meningkat sebesar 292 kali dan untuk menjaga akurasi hasil dalam batas yang diperlukan, kita perlu meningkatkan keakuratan argumen secara signifikan.Ingatlah bahwa transisi dari 24 ke 32 bit memberi kita peningkatan akurasi yang diperlukan (tidak cukup, tapi sangat dekat), kami memahami bahwa perkalian pertama (n * log (2)) harus dilakukan dengan operan 32 bit, yaitu, dengan akurasi seperti itu logaritma dua harus diekspresikan, maka itu akan sama dengan 1'292'914'005 / 2 ^ 32. Perhatikan bahwa dalam kode pembilang konstanta ini harus ditulis sebagai (int) ((log (2) * float (2 ^ 32)) + 0,5), tetapi dalam kasus apa pun sebagai 0x4d104d42 yang misterius, bahkan dengan komentar tentang hal itu komputasi, karena kode yang ditulis dengan baik adalah dokumentasi diri.Selanjutnya, kita perlu seluruh bagian dari hasilnya, ini tidak sulit, karena kita tahu persis posisi titik desimal di kedua faktor dan, sebagai hasilnya, sebagai hasilnya.Tapi kemudian kita harus menghitung 10 pangkat 0 hingga 1, dan di sini kita akan menggunakan trik kecil untuk mendapatkan akurasi yang diperlukan. Karena, sesuai dengan rumus untuk kesalahan, keakuratan di tepi kanan rentang turun lebih dari dua, maka jika kita menyatakan nilai argumen sebagai jumlah dari logaritma desimal dua dan beberapa sisanya, n '' = log (2) * i + (n '' - log ( 2) * i), maka anggota pertama dari jumlah tersebut akan dikalikan 2 dengan derajat yang sesuai, yang mudah diimplementasikan dengan nol kesalahan (sampai terjadi luapan), dan yang tersisa akan dibatasi oleh nilai log (2) dan kami tidak akan kehilangan keakuratan dalam menghitung 10 ^ n '' (dikenakan pengurangan yang tepat).Namun demikian, fungsi eksponensial untuk argumen yang dibatasi oleh nilai lg (2) masih harus dihitung dan satu-satunya cara yang saya lihat adalah ekspansi dalam deret Taylor. Sayangnya, itu tidak menyatu terlalu cepat pada jangkauan kami, dan, misalnya, untuk mencapai akurasi 10E-7, kami membutuhkan 9 anggota penjumlahan, yang mengarah pada kebutuhan untuk melaksanakan 1 + 9 * 2 = 19 perkalian bilangan bulat 32-bit, yang agak melebihi kinerja yang diinginkan. Masih ada keraguan samar tentang kemampuan kita menghitung n '= n * log (2) dengan akurasi sedemikian sehingga cukup untuk nilai maksimum n.Namundemikian, algoritma tersebut ternyata cukup fungsional dan kita hanya perlu penggandaan 32-bit untuk mendapatkan hasil dalam jumlah 1 + 19 + 1 = 21 operasi yang menentukan kompleksitas komputasi dari algoritmaApakah mungkin untuk mengurangi kompleksitas komputasi dari transformasi kita - tampaknya tidak, kita semua dengan cermat menghitung - tetapi tiba-tiba ternyata itu masih mungkin. Pernyataan yang agak tidak terduga, kunci untuk memahami kemungkinan ini terletak pada sifat urutan PT - dibutuhkan seperangkat nilai yang tetap (dan relatif kecil), dan Anda dan saya tidak memperhitungkan ini saat mengubah rumus konversi, tetapi secara implisit bekerja dengan nilai kontinu.Solusi paling sederhana - ubah memori untuk sementara waktu - hitung terlebih dahulu untuk semua kemungkinan (2 ^ 8 = 256) eksponen n nilai yang sesuai [n '] (eksponen paling cocok 10) dan {n'} (faktor korektif untuk mantissa), masukkan ke meja dan seterusnya mudah digunakan dalam proses perhitungan. Rumusnya ternyata cukup sederhana - PT = m * 2 ^ n = m * 10 ^ n '* (2 ^ n / 10 ^ n') = (m * (2 ^ n / 10 ^ n ')) * 10 ^ n '.Dalam kasus yang paling sederhana, kita perlu 256 * 3 (faktor koreksi 24 bit, tidak lagi diperlukan) + 256 * 1 (pesanan pada basis 10 dijamin lebih rendah dari pesanan pada basis 2) = konstanta 1kbyte. Dalam hal ini, tetap bagi kita untuk melakukan hanya satu perkalian dari bit 24 * 24 (kemungkinan besar akan menjadi 32 * 32), yang secara signifikan mempercepat pekerjaan dibandingkan dengan versi perhitungan ini.Mari kita lihat apa yang dapat dilakukan dari sudut pandang penghematan memori (dalam hal ini, kita harus membayar waktu lagi, jadi kami mencari kompromi yang masuk akal). Pertama-tama, jika kita memperhitungkan tanda pesanan secara terpisah, kita hanya dapat mengelola setengah dari memori yang diperlukan (dari 256 byte untuk pesanan 10) dan membalikkan hasilnya jika perlu. Sayangnya, dengan faktor koreksi, itu tidak akan mudah, karena2 ^ -n / 10 ^ -n '= 1 / (2 ^ n / 10 ^ n')! = 2 ^ n / 10 ^ n ',sangat disayangkan. Kita harus meninggalkan meja panjang, atau untuk indikator negatif, dibagi dengan konstanta untuk indikator positif. Tentu saja, pembagian bukanlah 18 perkalian, tetapi tetap itu persis setara dalam kecepatan hingga dua perkalian, sehingga waktu pasti akan berlipat ganda untuk menghemat memori dua kali, hingga 512 byte. Apakah itu sepadan - pertanyaannya tidak sederhana, tetapi, untungnya, kita memiliki cara yang jauh lebih indah yang memungkinkan kita untuk menyingkirkan penderitaan karena pilihan.Metode ini umumnya disebut pendekatan linier piecewise dan terdiri dalam menetapkan konstanta bukan untuk setiap titik dari nilai awal, tetapi hanya untuk beberapa dan menghitung nilai-nilai yang hilang (dengan akurasi yang diperlukan) menggunakan nilai yang diberikan menggunakan rumus sederhana. Sehubungan dengan masalah kami, kami memperoleh (tanpa memperhitungkan tanda)PT = m * 2 ^ n = m * 2 ^ (n0 + n1) = m * 10 ^ n '* (2 ^ (n0 + n1) / 10 ^ n') = m * (2 ^ n0 / 10 ^ n ') * 2 ^ n1 * 10 ^ n', dimana n0 adalah beberapa nilai referensi, dan n1 = n-n0. Kemudian mantissa baru dihitung dengan mengalikan dua angka dengan titik tetap, diikuti oleh perubahan dalam hasilnya, yang tidak merusak akurasi.Kemudian muncul pertanyaan yang sah - mengapa kita membutuhkan tabel sama sekali, karena Anda dapat mengambil indikator minimum sebagai n0 dan bertahan hanya dengan satu nilai faktor koreksi? Sayangnya, pendekatan semacam itu kontraproduktif karena dua keadaan yang saling melengkapi - kebutuhan untuk mendapatkan eksponen 10 yang paling sesuai dan munculnya pergeseran yang sangat lama dengan pendekatan ini. Keadaan terakhir menunjukkan batas penerapan metode seperti itu - jika kita melakukan perkalian 32 * 32, dan mantissa awal memiliki 24 digit, maka pergeseran 8 digit tidak akan mengarah pada luapan dan kita akan membutuhkan satu titik referensi dengan 8 nilai biner.Maka jumlah total memori yang diperlukan akan 256/8 * 4 = 32 * 4 = 128 byte - penghematan memori yang baik dengan biaya waktu eksekusi karena kebutuhan untuk menggeser seluruh hasil pekerjaan dengan maksimum 8 bit.Anda dapat mengurangi jumlah konstanta sedikit lebih karena simetri eksponen sehubungan dengan 0, yang saya sebutkan sebelumnya, tetapi penghematan akan menjadi 32/2 = 16 byte, saya tidak yakin bahwa ini akan membenarkan komplikasi (dan peningkatan panjang kode) dari program itu sendiri.Ngomong-ngomong, saya baru-baru ini melihat kode perpustakaan AdWords, yang dikenal luas di kalangan sempit, dan sedikit terkejut oleh fragmen kode berikut const UINT8 Bits[] = {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80}; ... data = data | Bits[n];
dengan komentar bahwa operasi 1 << n pada AVR membutuhkan waktu lama. Dalam posting saya, saya sudah menunjukkan keajaiban apa yang dilakukan kompiler dengan parameter konstan, tetapi ini tidak terjadi.Sepertinya saya ragu bahwa mengambil bitmask dari array akan lebih cepat daripada melakukan operasi shift secara langsung dan analisis kode selanjutnya (menggunakan situs godbolt, meskipun sangat tidak mungkin bahwa penciptanya akan membaca Habr, namun sekali lagi saya membawanya kepadanya dengan tulus. terima kasih) menunjukkan bahwa memang demikian adanya.Kode yang dihasilkan oleh kompiler untuk kedua opsi (di sini adalah opsi yang benar dengan shift, dengan mempertimbangkan fitur tugas, karena kita hanya perlu 1 bit) ldi r18,lo8(4) sbrs r25,1 ldi r18,lo8(1) sbrc r25,0 lsl r18 sbrs r25,2 swap r18
mengambil tempat yang persis sama di memori, dan jika semuanya dilakukan dengan hati-hati di assembler, opsi dengan indeks di depan 8: 7 karena tambahan 8 byte program (tentu saja, jika kita tidak menganggap serius solusi yang benar-benar menyenangkan dengan penyimpanan terpisah dari topeng terbalik, yang akan dikenakan biaya dalam 16 byte - dan IT digunakan di mana-mana - “Saya tahu ini akan buruk, tetapi saya tidak tahu bahwa itu akan sangat cepat”). Nah, paket yang disebutkan pada umumnya adalah lagu yang terpisah, dijelaskan sebaik mungkin oleh kutipan berikut dari satu buku yang luar biasa: "Kastil ini meminta sampul benteng dengan tulisan" Bagaimana tidak membangun kastil atau menemukan 12 kesalahan "(" The Last Ringman ", jika siapa pun yang belum membacanya, saya sarankan.)Mari kita kembali ke domba jantan floating point kami dan membangun formula yang dihasilkanPT = m * 2 ^ n = (m * pc [n / 8]) * 2 ^ (n% 8) * 10 ^ nn [n / 8], dimana tanda kurung siku berarti mengambil elemen array pc, koreksi pada indikator dan nn- urutan indikator. Kompleksitas komputasi dari algoritma ini segera terlihat, yang ditentukan dengan mengalikan 32 * 32 (24 * 24) dan perubahan selanjutnya. Selanjutnya, Anda dapat mempertimbangkan kemungkinan menggabungkan eksponen 10 dan faktor koreksi dalam satu kata 32-bit, ini diserahkan kepada bagian dari pembaca yang ingin tahu (dan pasien, setelah semua, ia membaca sampai akhir) dari posting ini.Satu-satunya komentar di akhir adalah ketika kita akan membuat tabel konstanta, dalam keadaan apa pun kita tidak dapat melakukannya dengan gaya berikut: konst uint32_t Data [32] PROGMEM = {0xF82345, ...}dan intinya, tentu saja, bukan dalam atribut deskripsi array, tetapi dalam data itu sendiri dalam bentuk angka ajaib. Seperti yang penulis catat dengan benar, itu pasti tidak lebih bodoh dari saya, kode yang ditulis dengan baik mendokumentasikan diri dan, jika kita menulis konstanta di atas (dan sisanya) dalam bentuk #define POWROUD(pow) ((uint8_t)((pow & 0x07)*log(2)+0.5)) #define MULT(pow) (2^pow / 10^POWROUND(pow)) #define MULTRAW(pow) (uint32_t((MULT(pow) << 24) +0.5)) #define BYTEMASK 0xFF #define POWDATA(pow) ((POWROUND(pow) & BYTEMASK)| (MULTRAW(pow) & (~BYTEMASK))) const uint32_t Data[(BYTEMASK/8)+1] = { POWDATA(0x00),POWDATA(0x08), ..POWDATA(0xF8)}
maka tidak ada yang akan mengirimi kami pertanyaan yang membingungkan, dan jika seseorang mengirim kami, kami pasti tidak bisa menjawabnya, itu masih sia-sia.Kita dapat mengusulkan modifikasi metode ini di mana kekuatan sepuluh yang sesuai akan dihitung bukan untuk tepi kanan segmen, tetapi untuk kiri dan kemudian hasilnya tidak akan bergeser ke kanan untuk memperhitungkan kekuatan dua, tetapi ke kiri. Dari sudut pandang matematika, metode ini benar-benar setara. Mari kita lihat hasilnya:1.953125 * 2 ^ 9 = 1.953125 * 2 ^ (8 + 1) = 1.953125 * 42949673/256/256/256 (2.56) * 2 * 10 ^ 2 = 10 * 10 ^ 2sudah sangat mudah untuk menemukan 1000 di sini. Tentu saja, kita juga perlu mengonversi mantissa yang diperoleh dan memesan ke string, dengan hati-hati membulatkannya, menyesuaikan hasilnya dengan format yang diperlukan, menambahkan karakter, memperhitungkan kasing khusus dan sebagainya, tetapi ini tidak begitu menarik lagi, bagian utama transformasi yang kami lakukan.