Jika suatu perangkat keras tidak mendukung operasi modulus atau divisi, dibutuhkan lebih banyak siklus CPU untuk mensimulasikan modulus / divisi dengan perangkat lunak. Apakah ada cara yang lebih cepat untuk menghitung pembagian dan modulus jika operan adalah 10?
Dalam proyek saya, saya sering perlu menghitung bilangan bulat bilangan bulat 10. Secara khusus, saya sedang mengerjakan PIC16F dan perlu menunjukkan angka pada LCD. Ada 4 digit untuk didukung, jadi ada 4 panggilan ke modulus dan fungsi pembagian (implementasi perangkat lunak). Yaitu, seperti berikut:
digit = number % 10; // call to an expensive function
number /= 10; // call to an expensive function
somehow_lit_segments();
digit = number % 10; // call to an expensive function
number /= 10; // call to an expensive function
somehow_lit_segments();
digit = number % 10; // call to an expensive function
number /= 10; // call to an expensive function
somehow_lit_segments();
digit = number % 10; // call to an expensive function
number /= 10; // call to an expensive function
somehow_lit_segments();
Ada area lain yang menggunakan kode serupa.
Jawaban:
Berikut ini adalah algoritma biner ke BCD yang saya gunakan beberapa tahun lalu berdasarkan yang ditemukan di sini . Saya menggunakan BCD eksternal untuk 7 seg display driver sehingga hasilnya dapat ditulis ke port yang tepat secara langsung sebagai paket BCD untuk output.
Ini cukup cepat jika Anda memiliki pengganda perangkat keras di PIC, saya menggunakan PIC18F97J60. Jika Anda tidak memiliki pengganda perangkat keras pada PIC Anda, pertimbangkan untuk menggunakan shift + add untuk perkaliannya.
Ini mengambil int 16bit yang tidak ditandatangani dan mengembalikan BCD yang dikemas dengan 5 digit, dapat dimodifikasi dan dibuat lebih cepat untuk 4 digit. Ini menggunakan shift + tambahan untuk perkiraan pembagian dengan 10 tetapi mengingat kisaran input terbatas itu tepat untuk penggunaan ini. Anda mungkin ingin mengemas hasil secara berbeda juga agar sesuai dengan cara Anda menggunakan hasilnya.
sumber
Dengan asumsi bilangan bulat bertanda, pembagian dan perkalian dapat dibentuk dari bit shift. Dan dari divisi (integer) dan multiplikasi, modulo dapat diturunkan.
Untuk mengalikan dengan 10:
Membagi dengan 10 lebih sulit. Saya tahu beberapa algoritma pembagian. Jika saya ingat dengan benar, ada cara untuk membaginya dengan 10 dengan cepat menggunakan bit shift dan pengurangan, tetapi saya tidak dapat mengingat metode yang tepat. Jika itu tidak benar, maka ini adalah algoritma pembagian yang mengelola <130 siklus . Saya tidak yakin mikro apa yang Anda gunakan, tetapi Anda bisa menggunakannya dalam beberapa cara, bahkan jika Anda harus porting.
EDIT: Seseorang berkata di Stack Overflow , jika Anda dapat mentolerir sedikit kesalahan dan memiliki register sementara yang besar, ini akan bekerja:
Dengan asumsi Anda memiliki pembagian dan perkalian, modulo sederhana:
sumber
Anda dapat mengonversi dari biner ke BCD yang dikemas tanpa pembagian apa pun menggunakan algoritma dabble ganda . Hanya menggunakan shift dan menambahkan 3 .
Misalnya mengonversi 243 10 = 11110011 2 menjadi biner
Algoritma ini sangat efisien ketika tidak ada pembagi perangkat keras yang tersedia. Terlebih lagi hanya shift kiri sebanyak 1 yang digunakan, jadi ini cepat bahkan ketika barrel shifter tidak tersedia
sumber
Bergantung pada jumlah digit yang Anda butuhkan, Anda mungkin dapat menggunakan metode brute force (
d
- nomor input,t
- string ASCII keluaran):Anda juga bisa mengubah multiple ifs menjadi loop, dengan kekuatan sepuluh diperoleh dengan perkalian atau tabel pencarian.
sumber
Catatan aplikasi ini menjelaskan algoritma untuk aritmatika BCD, termasuk konversi dari biner ke BCD dan sebaliknya. Appnote adalah oleh Atmel, yang merupakan AVR, tetapi algoritma yang dijelaskan adalah prosesor-independen.
sumber
Saya tidak memiliki jawaban yang baik, tetapi ada diskusi yang bagus tentang situs saudara Stack Overflow kami tentang topik yang sama persis tentang optimasi divisi dan modulo.
Apakah Anda memiliki cukup memori untuk mengimplementasikan tabel pencarian?
Hackers Delight memiliki makalah tentang algoritma pembagian optimal.
sumber
Pernahkah Anda mempertimbangkan untuk memegang nilai itu sebagai BCD sepanjang waktu (menggunakan subrutin "BCD increment" dan "BCD add" khusus sederhana), daripada menahan nilai itu dalam bentuk biner dan mengonversi ke BCD sesuai kebutuhan (menggunakan konversi yang lebih sulit dipahami " dari biner ke BCD "subroutine)?
Pada satu waktu, semua komputer menyimpan semua data sebagai angka desimal (roda gigi sepuluh posisi, tabung vakum kode dua-dari-lima, BCD, dll.), Dan warisan itu masih ada sampai sekarang. (lihat Mengapa chip jam waktu nyata menggunakan BCD ).
sumber
The PICList adalah sumber daya yang luar biasa bagi orang-orang pemrograman prosesor PIC.
Konversi BCD
Sudahkah Anda mempertimbangkan untuk menggunakan subrutin biner-ke-BCD yang dicoba dan diuji secara khusus yang dioptimalkan untuk PIC16F?
Secara khusus, orang-orang di PICList telah menghabiskan banyak waktu untuk mengoptimalkan konversi biner ke BCD pada PIC16F. Rutinitas tersebut (masing-masing tangan dioptimalkan untuk ukuran tertentu) dirangkum di "Metode Microcontoller Radix Conversion Math PIC" http://www.piclist.com/techref/microchip/math/radix/index.htm
divisi integer dan mod
Pada CPU seperti PIC16F, subrutin yang khusus untuk dibagi dengan konstanta seringkali jauh lebih cepat daripada tujuan umum "membagi variabel A dengan variabel B". Anda mungkin ingin meletakkan konstanta Anda (dalam hal ini, "0,1") dalam "Pembuatan Kode untuk Penggandaan / Divisi Konstan" http://www.piclist.com/techref/piclist/codegen/constdivmul.htm atau periksa rutinitas kalengan dekat http://www.piclist.com/techref/microchip/math/basic.htm .
sumber
Diberikan penggandaan perangkat keras 8x8, seseorang dapat menghitung divmod-10 dari nomor ukuran sewenang-wenang dengan menggunakan rutin yang menghitungnya untuk nomor 12-bit dalam kisaran 0-2559 melalui prosedur:
Saya akan menyarankan menulis rutin divmod yang MSB nomornya akan berada di W, dan LSB ditunjuk oleh FSR; rutin harus menyimpan hasil bagi dalam FSR dengan post-decrement dan meninggalkan sisanya di W. Untuk membagi panjang 32-bit dengan 10, orang kemudian akan menggunakan sesuatu seperti:
Langkah divmod-6 akan sangat mirip, kecuali menggunakan konstanta 85 dan 6 daripada 51 dan 10. Dalam kedua kasus, saya berharap divmod10_step akan menjadi 20 siklus (ditambah empat untuk panggilan / pengembalian) sehingga divmod10 pendek akan menjadi sekitar 50 siklus dan divmod10 panjang akan menjadi sekitar 100 (jika satu kasus khusus langkah pertama, seseorang bisa menghemat beberapa siklus).
sumber
ini mungkin bukan yang tercepat tetapi merupakan cara sederhana.
sumber