Bagaimana pembagian terjadi di komputer kita?

Bagaimana pembagian terjadi di dalam komputer digital? Apa algoritma untuk itu?

Saya telah mencari dengan keras di google tetapi belum mendapatkan hasil yang memuaskan. Harap berikan sangat jelas algoritma / flowchart untuk algoritma pembagian dengan ilustrasi sampel.

algoritma divisi dalam desain digital dapat dibagi menjadi dua kategori utama. divisi lambat dan divisi cepat.

Saya sarankan Anda membaca tentang bagaimana biner penambahan dan pengurangan pekerjaan jika Anda belum terbiasa dengan konsep-konsep ini.

Divisi lambat

Metode lambat sederhana semua pekerjaan dengan cara berikut: Kurangi denominator dari pembilang. Lakukan ini secara rekursif dengan hasil masing-masing pengurangan sampai sisanya kurang dari penyebut. Jumlah iterasi adalah hasil bagi bilangan bulat, dan jumlah yang tersisa adalah sisanya.

Contoh:

7/3:

1. $$7-3=4$$
2. $$4-3=1$$
3. $$1 < 3$$

Jadi jawabannya adalah 2 dengan sisa 1. Untuk membuat jawaban ini sedikit lebih relevan, di sini adalah beberapa latar belakang. pengurangan biner melalui penambahan negatif dilakukan misalnya: 7-3 = 7 + (-3). Hal ini dicapai dengan menggunakan komplemen dua nya. Setiap angka biner ditambahkan menggunakan serangkaian penambah penuh:

Di mana setiap 1-bit penambah penuh akan dilaksanakan sebagai berikut:

Divisi cepat

Sedangkan metode lebih lambat dari divisi mudah dimengerti, membutuhkan iterasi berulang-ulang. Ada ada berbagai "cepat" algoritma, tetapi mereka semua bergantung pada estimasi.

Mempertimbangkan metode Goldschmidt:

Saya akan menggunakan yang berikut ini:

Metode ini berfungsi sebagai berikut:

1. Multiply N dan D dengan fraksi F sedemikian rupa bahwa D mendekati 1.
2. Ketika D mendekati 1, N mendekati Q

Metode ini menggunakan perkalian biner melalui penambahan berulang, yang juga digunakan di zaman modern AMD CPU.

Hardware untuk divisi floating point merupakan bagian dari unit logika yang juga melakukan perkalian; ada modul hardware multiplier yang tersedia. Angka floating point, mengatakan A dan B, dibagi (membentuk A / B) oleh

1. membusuk angka floating point ke tanda (+1 atau -1), mantissa ( "a" dan "b", dan (binary tipe integer) eksponen
2. tanda hasilnya adalah (1) jika dan hanya jika keduanya tanda-tanda yang sama, lain (-1)
3. eksponen dikurangi (eksponen B dikurangkan dari eksponen A) untuk membentuk eksponen hasilnya

4. Mantisa (biner digit nomor) adalah bilangan biner fixed-point antara 1/2 dan 1; itu berarti bahwa digit pertama setelah titik biner adalah '1', diikuti oleh nol dan satu ... sebagai langkah pertama, tabel pencarian menemukan timbal balik akurat hingga enam bit (hanya ada 32 kemungkinan, ini adalah meja kecil)

5. $${a \over b} = {{a * reciprocal(b)}\over b * reciprocal(b)}$$

6. $$d == 1 +\epsilon$$ $$d * (2-d) = ( 1+ \epsilon) \times (1-\epsilon) = 1 - \epsilon ^2$$ Ini menyiratkan bahwa 'satu' akurat lima bit kami dalam penyebut akan menjadi sepuluh bit akurat setelah satu pasang perkalian lagi, dua puluh bit akurat setelah dua, dan empat puluh bit akurat setelah tiga. Lakukan seperti banyak iterasi dari mengalikan pembilang dan penyebut oleh (2 - denominator) sebagai hasilnya presisi Anda membutuhkan.
7. pembilang, sekarang penyebut adalah persis '1', adalah mantissa dari hasil, dan dapat dikombinasikan dengan tanda sebelumnya dihitung dan eksponen.
8. IEEE floating point memungkinkan beberapa pengecualian (nomor denormalized, NAN, mereka harus ditangani oleh operasi logis lainnya.

Menariknya, bug pembagian Pentium lama (sangat bernilai berita pada tahun 1994) disebabkan oleh kesalahan pencetakan yang membuat nilai tabel timbal balik yang salah untuk langkah (4). Kertas awal, "Sebuah Metode Divisi Menggunakan Multplier Paralel", Domenico Ferrari, IEEE Trans. Elektron. Comput. EC-16 / 224-228 (1967), menjelaskan metode ini, seperti halnya "Sistem IBM / Model 360 91: Unit Eksekusi Floating-Point" IBM J. Res. Dev. 11 : 34-53 (1967).

Ada beberapa metode yang sangat berbeda untuk divisi, tergantung pada nomor yang akan ditangani. Untuk bilangan bulat, metode shift-dan-kurangi diberikan oleh orang lain akan bekerja dengan baik. Untuk angka floating point, bagaimanapun, mungkin lebih cepat untuk menghitung pertama kebalikan dari penyebut dan kemudian kalikan bahwa kali pembilang Anda.

Perhitungan kebalikan dari penyebut tidak begitu buruk; ini dilakukan dengan menyempurnakan pendekatan yang berurutan. Biarkan g menjadi tebakan Anda untuk 1 / d. Untuk perkiraan yang lebih baik, gunakan g '= g (2-gd). Ini menyatu secara kuadrat, sehingga Anda menggandakan digit presisi pada setiap peningkatan.

Contoh: hitung kebalikan dari 3,5.

Tebakan awal Anda adalah 0,3. Anda menghitung 0,3 * 3,5 = 1,15. Dugaan Anda disesuaikan adalah 0,3 * (2-1,15) = 0,285. Sudah cukup dekat! Ulangi proses, dan Anda mendapatkan 0.2857125, dan ketiga mencoba mendapat ,2857142857.

Ada beberapa jalan pintas. Dalam floating point, Anda dapat mengekstrak kekuatan sepuluh atau kekuatan dari dua, tergantung pada dasar jumlah mesin Anda. Dan, untuk kecepatan dengan mengorbankan penggunaan memori yang lebih besar, Anda dapat menggunakan tabel pra-dihitung untuk angka dalam kisaran 1 sampai b (di mana b adalah bilangan basis Anda) untuk mendapatkan menebak bahwa segera dekat dengan yang dibutuhkan timbal balik dan simpan satu atau dua langkah penyempurnaan.

Perlu diingat bahwa, seperti dengan perkalian dan Kolmogorov 1960 malu oleh muridnya Anatoly Karatsuba, Anda tidak pernah tahu kapan metode yang lebih cepat atau lebih baik akan ditemukan. Jangan pernah menyerahkan rasa ingin tahu Anda.

Komputer tidak melakukan penambahan berulang ke nomor kalikan - itu akan sangat lambat. Sebagai gantinya, ada beberapa algoritma multiplikasi cepat. Periksa: http://en.wikipedia.org/wiki/Karatsuba_algorithm