Ketika saya semakin terlibat dengan teori di balik pemrograman, saya menemukan diri saya terpesona dan tercengang oleh hal-hal yang tampaknya sederhana .. Saya menyadari bahwa pemahaman saya tentang sebagian besar proses fundamental dibenarkan melalui logika sirkuler

T : Bagaimana cara kerjanya?

A : Karena ya!

Aku benci realisasi ini! Saya suka pengetahuan, dan di atas semua itu saya suka belajar, yang mengarahkan saya ke pertanyaan saya (meskipun itu luas).

Pertanyaan:

Bagaimana operator matematika dasar dinilai dengan bahasa pemrograman?

Bagaimana metode saat ini ditingkatkan?

Contoh

var = 5 * 5; 

Interpretasi saya:

$num1 = 5; $num2 = 5; $num3 = 0;
while ($num2 > 0) {
    $num3 = $num3 + $num1;
    $num2 = $num2 - 1;
}
echo $num3;

Ini tampaknya sangat tidak efisien. Dengan Faktor yang lebih tinggi, metode ini sangat lambat sedangkan metode standar bawaannya instan. Bagaimana Anda mensimulasikan multiplikasi tanpa iterasi penambahan?

var = 5 / 5;

Bagaimana ini dilakukan? Saya tidak bisa memikirkan cara untuk benar-benar membaginya menjadi 5 bagian yang sama.

var = 5 ^ 5; 

Iterasi iterasi penambahan? Interpretasi saya:

$base = 5;
$mod = 5;
$num1 = $base;
while ($mod > 1) {

    $num2 = 5; $num3 = 0;
    while ($num2 > 0) {
        $num3 = $num3 + $num1;
        $num2 = $num2 - 1;
    }
    $num1 = $num3;
    $mod -=1;
}
echo $num3;

Sekali lagi, ini sangat tidak efisien, namun saya tidak dapat memikirkan cara lain untuk melakukan ini. Pertanyaan yang sama ini meluas ke semua fungsi terkait matematika yang ditangani secara otomatis.

Untuk benar-benar memahami cara kerja aritmatika di dalam komputer, Anda harus memprogram dalam bahasa assembly. Lebih disukai yang dengan ukuran kata kecil dan tanpa instruksi perkalian dan pembagian. Sesuatu seperti 6502.

Pada 6502, hampir semua aritmatika dilakukan dalam register yang disebut Akumulator. (Register adalah lokasi memori khusus di dalam prosesor yang dapat diakses dengan cepat.) Jadi, untuk menambahkan dua angka, Anda memuat angka pertama ke dalam Akumulator, lalu menambahkan angka kedua ke dalamnya.

Tapi itu terlalu menyederhanakan. Karena 6502 adalah prosesor 8-bit, ia hanya dapat menangani angka dari 0 hingga 255. Sebagian besar waktu Anda ingin dapat bekerja dengan angka yang lebih besar. Anda harus menambahkan ini dalam potongan, 8 bit sekaligus. Prosesor memiliki bendera Carry yang disetel ketika hasil penambahan dua angka melebihi Accumulator. Prosesor menambahkan bahwa ketika melakukan penambahan, sehingga dapat digunakan untuk "membawa 1" dengan asumsi Anda mulai dengan byte urutan terendah dari sebuah angka. Pengaya multi-byte pada 6502 terlihat seperti ini:

1. Hapus carry flag (CLC)
2. Memuat byte urutan terendah dari nomor pertama (LDA, load akumulator)
3. Tambahkan byte urutan terendah dari nomor kedua (ADC, tambahkan dengan carry)
4. Menyimpan byte hasil urutan terendah (STA, store akumulator)
5. Ulangi langkah 2-4 dengan byte urutan yang lebih tinggi
6. Jika pada akhirnya, carry diatur, Anda telah meluap; mengambil tindakan yang sesuai, seperti menghasilkan pesan kesalahan (BCS / BCC, cabang jika carry di set / hapus)

Pengurangan serupa kecuali Anda mengatur carry pertama, gunakan instruksi SBC, bukan ADC, dan pada akhirnya carry jelas jika ada underflow.

Tapi tunggu! Bagaimana dengan angka negatif? Nah, dengan 6502 ini disimpan dalam format yang disebut pelengkap dua. Dengan asumsi angka 8-bit, -1 disimpan sebagai 255, karena ketika Anda menambahkan 255 ke sesuatu, Anda mendapatkan yang lebih sedikit di Accumulator (plus carry). -2 disimpan sebagai 254 dan seterusnya, hingga -128, yang disimpan sebagai 128. Jadi untuk bilangan bulat yang ditandatangani, setengah rentang 0-255 byte digunakan untuk angka positif dan setengah untuk angka negatif. (Konvensi ini memungkinkan Anda hanya memeriksa bit angka yang tinggi untuk melihat apakah angka itu negatif.)

Anggap saja seperti jam 24 jam: menambahkan 23 ke waktu akan menghasilkan waktu satu jam sebelumnya (pada hari berikutnya). Jadi 23 adalah modular jam setara dengan -1.

Ketika Anda menggunakan lebih dari 1 byte, Anda harus menggunakan angka yang lebih besar untuk negatif. Misalnya, bilangan bulat 16-bit memiliki rentang 0-65536. Jadi 65535 digunakan untuk mewakili -1, dan seterusnya, karena menambahkan 65535 ke nomor berakibat kurang satu (plus carry).

Pada 6502 hanya ada empat operasi aritmatika: tambah, kurangi, kalikan dua (bergeser ke kiri), dan bagi dengan dua (bergeser ke kanan). Perkalian dan pembagian dapat dilakukan hanya dengan menggunakan operasi ini ketika berhadapan dengan biner. Sebagai contoh, pertimbangkan mengalikan 5 (biner 101) dan 3 (biner 11). Seperti dengan perkalian panjang desimal, kita mulai dengan digit kanan pengali dan kalikan 101 dengan 1, memberikan 101. Kemudian kita menggeser multiplikasi dan kiri 1010 dengan 1, memberikan 1010. Kemudian kita tambahkan hasil ini bersama-sama, memberikan 1111, atau 15. Karena kita hanya mengalikan 1 atau 0, kita tidak benar-benar mengalikan; setiap bit dari pengali hanya berfungsi sebagai flag yang memberitahu kita apakah akan menambahkan multiplicand (bergeser) atau tidak.

Divisi analog dengan divisi panjang manual menggunakan pembagi percobaan, kecuali dalam biner. Jika Anda membaginya dengan konstanta, adalah mungkin untuk melakukan ini dengan cara yang analog dengan pengurangan: alih-alih membaginya dengan X, Anda mengalikannya dengan rendemen prakalkulasi 1 / X yang menghasilkan hasil yang diinginkan ditambah dengan luapan. Bahkan hari ini, ini lebih cepat daripada pembagian.

Sekarang coba lakukan matematika titik-mengambang dalam rakitan, atau ubah angka titik-mengambang menjadi format output yang bagus dalam rakitan. Dan ingat, ini tahun 1979 dan kecepatan clock adalah 1 MHz, jadi Anda harus melakukannya seefisien mungkin.

Banyak hal masih berjalan seperti ini hari ini, kecuali dengan ukuran kata yang lebih besar dan register yang lebih banyak, dan tentu saja sebagian besar matematika dilakukan oleh perangkat keras sekarang. Tapi itu masih dilakukan dengan cara fundamental yang sama. Jika Anda menambahkan jumlah shift dan menambahkan yang diperlukan untuk penggandaan, misalnya, itu berkorelasi lebih baik dengan jumlah siklus yang diperlukan untuk instruksi perkalian perangkat keras pada prosesor awal yang memiliki instruksi seperti itu, seperti 6809, di mana ia dilakukan dalam mikrokode dalam banyak cara yang sama Anda akan melakukannya secara manual. (Jika Anda memiliki anggaran transistor yang lebih besar, ada cara yang lebih cepat untuk melakukan pergantian dan penambahan, sehingga prosesor modern tidak melakukan operasi ini secara berurutan dan dapat melakukan penggandaan hanya dalam satu siklus tunggal.)

Pada akhirnya, operasi aritmatika dasar dilakukan dalam perangkat keras. Lebih khusus lagi, dalam CPU (atau sebenarnya, bagian daripadanya)

Dengan kata lain, ini sirkuit elektronik. Tetapkan bit yang sesuai sebagai input dan Anda akan mendapatkan bit yang sesuai sebagai output. Ini adalah kombinasi dari gerbang logika dasar.

http://en.wikipedia.org/wiki/Adder_%28electronics%29

http://en.wikipedia.org/wiki/Binary_multiplier

Ini semua ditutupi dengan kesabaran yang mendalam dalam The Art of Computer Programming karya Don Knuth.

Algoritma yang efisien untuk menambah, mengurangi, mengalikan, dan membagi semuanya dijelaskan secara rinci lengkap.

Anda dapat membaca hal-hal seperti ini yang mencakup pembagian dengan baik.

http://research.microsoft.com/pubs/151917/divmodnote.pdf

Ini dilakukan dalam hitungan detik oleh sirkuit elektronik. Google 'pengganda perangkat keras' dll. Untuk detailnya. CPU modern adalah hasil yang sangat kompleks dari perbaikan berkesinambungan selama beberapa dekade.

BTW, Karena Anda tidak memperbanyak dengan penambahan berulang, mengapa Anda membayangkan komputer melakukannya?

Ini tidak dimaksudkan untuk menjadi jawaban menyeluruh dengan cara apa pun, tetapi harus memberi Anda beberapa ide bagaimana hal-hal diterapkan. Seperti yang mungkin Anda ketahui, angka direpresentasikan dalam biner. Misalnya komputer dapat mewakili angka 5 sebagai 00000101. Operasi yang sangat mendasar yang dapat dilakukan komputer adalah bergeser ke kiri, yang akan menghasilkan 00001010 yang merupakan desimal 10. Jika itu shifter benar dua kali akan menjadi 00010100 (desimal 20). Setiap kali kita menggeser digit kiri 1 kali kita menggandakan jumlahnya. Katakanlah saya memiliki angka x dan saya ingin mengalikannya dengan 17. Saya bisa menggeser x ke kiri 4 kali dan kemudian menambahkan x ke hasilnya (16x + x = 17x). Ini akan menjadi cara yang efisien untuk mengalikan angka dengan 17. Ini akan memberi Anda wawasan tentang bagaimana komputer dapat mengalikan angka besar tanpa hanya menggunakan penambahan berulang.

Division dapat menggunakan kombinasi penjumlahan, pengurangan, bergeser ke kanan, bergeser ke kiri, dll. Ada juga banyak trik untuk menaikkan angka ke eksponen.

Ketika saya masih kecil, saya belajar bagaimana melipatgandakan dan membaginya dengan pena dan kertas, tanpa membuang waktu dengan terlalu banyak tambahan. Belakangan saya mengetahui bahwa akar kuadrat juga bisa dihitung.

Di universitas saya belajar bagaimana menghitung operasi trigonometri dan logaritmik dengan selusin perkalian, divisi, dan penambahan. Mereka menyebutnya seri Taylor.

Sebelum itu, ayah saya memberi saya sebuah buku di mana operasi rumit itu sudah dihitung untuk ratusan nilai dan disajikan dalam tabel. Ada juga beberapa penjelasan untuk memperkirakan kesalahan ketika Anda menginginkan sinus nilai antara dua nilai yang dihitung.

Unit integer, unit floating point, GPU dan DSP hanya menerapkan semua teknik lama pada silikon.

Saya akan mencoba memberi Anda gambaran tentang bagaimana sirkuit digital dirancang untuk memecahkan masalah pemrosesan digital dengan menggunakan masalah yang Anda ajukan: bagaimana CPU menerapkan penambahan dan perkalian.

Pertama, mari kita ajukan pertanyaan langsung: bagaimana bahasa pemrograman secara efisien mengevaluasi perkalian dan penambahan. Jawabannya sederhana, mereka mengkompilasinya menjadi banyak dan menambah instruksi. Misalnya, kode berikut:

a = 1 + 1;
b = a * 20;

hanya dikompilasi untuk sesuatu seperti:

ADD 1 1  a
MUL a 20 b

(perhatikan, bahwa perakitan di atas adalah untuk CPU imajiner yang tidak ada, demi kesederhanaan).

Pada titik ini Anda menyadari bahwa jawaban di atas hanya menggeser masalah dan menyelesaikannya dengan sihir perangkat keras. Pertanyaan lanjutannya adalah bagaimana cara kerja sihir perangkat keras itu?

Mari kita lihat masalah yang lebih sederhana: penambahan.

Pertama-tama kita melakukan masalah yang biasa, menambahkan dalam basis 10 angka biasa:

 17
+28

Langkah pertama adalah menambahkan 7 dan 8. Tetapi ini menghasilkan 15 yang lebih dari satu digit. Jadi kami membawa 1:

(1)
 17
+28
= 5

Sekarang kita tambahkan 1, 1 dan 2 bersama-sama:

 17
+28
=45

Jadi dari ini kita mendapatkan aturan berikut:

1. ketika hasil penambahan lebih dari satu digit, kami mempertahankan digit paling tidak signifikan dan meneruskan digit paling signifikan ke depan

2. jika kita memiliki angka yang dibawa ke dalam kolom kita, kita menambahkannya bersama dengan angka yang kita tambahkan

Sekarang saatnya menafsirkan aturan di atas dalam basis 2 - aljabar boolean.

Jadi dalam aljabar boolean, menambahkan 0 dan 1 bersama-sama = 1. Menambahkan 0 dan 0 = 0. Dan menambahkan 1 dan 1 = 10 yang lebih dari satu digit sehingga kami membawa 1 maju.

Dari sini kita dapat membuat tabel kebenaran:

a b  |  sum  carry
-------------------
0 0  |   0     0
0 1  |   1     0
1 0  |   1     0
1 1  |   0     1

Dari ini, kita dapat membangun dua sirkuit / persamaan boolean - satu untuk output jumlah dan satu untuk output carry. Cara yang paling naif adalah mencantumkan semua input. Tabel kebenaran apa pun, tidak peduli seberapa besar dan kompleks dapat disajikan kembali dalam bentuk ini:

(AND inputs in first row) OR (AND of inputs in second row) OR ...

Ini pada dasarnya adalah jumlah dari bentuk produk. Kami hanya melihat output yang menghasilkan 1 dan mengabaikan 0s:

sum = (NOT a AND b) OR (a AND NOT b)

Mari ganti DAN ATAU dan BUKAN dengan simbol bahasa pemrograman agar lebih mudah dibaca:

sum = (!a & b) | (a & !b)

Pada dasarnya, kami telah mengonversi tabel seperti ini:

a b  |  sum  equation
-------------------
0 0  |   0   
0 1  |   1   (!a & b)
1 0  |   1   (a & !b)
1 1  |   0   

Ini dapat langsung diimplementasikan sebagai sirkuit:

                _____
 a ------------|     |
    \          | AND |-.     ____
     \  ,-NOT--|_____|  \   |    |
      \/                 `--| OR |----- sum
      /\        _____    ,--|____|
     /  `-NOT--|     |  /
    /          | AND |-`
 b ------------|_____|

Pembaca yang jeli pada saat ini akan memperhatikan bahwa logika di atas sebenarnya dapat diimplementasikan sebagai gerbang tunggal - gerbang XOR yang dengan mudah memiliki perilaku yang diperlukan oleh tabel kebenaran kami:

                _____
 a ------------|     |
               | XOR |---- sum
 b ------------|_____|

Tetapi jika perangkat keras Anda tidak memberi Anda gerbang XOR, langkah-langkah di atas adalah bagaimana Anda akan mendefinisikan dan mengimplementasikannya dalam hal gerbang AND, ATAU dan BUKAN.

Bagaimana Anda akan mengubah gerbang logika menjadi perangkat keras aktual tergantung pada perangkat keras yang Anda miliki. Mereka dapat diimplementasikan dengan menggunakan berbagai mekanisme fisik selama mekanisme tersebut menyediakan semacam perilaku switching. Gerbang logika telah diimplementasikan dengan segala sesuatu mulai dari semburan air atau embusan udara (fluidics) hingga transisitor (elektronik) hingga kelereng yang jatuh. Ini adalah topik besar dalam haknya sendiri jadi saya akan mengabaikannya dan mengatakan bahwa mungkin untuk menerapkan gerbang logika sebagai perangkat fisik.

Sekarang kita melakukan hal yang sama untuk membawa sinyal. Karena hanya ada satu kondisi di mana sinyal pembawa benar, persamaannya sederhana:

carry = a & b

Jadi, bawa barang sederhana:

                _____
 a ------------|     |
               | AND |---- carry
 b ------------|_____|

Menggabungkan mereka bersama-sama kita dapatkan apa yang dikenal sebagai setengah penambah:

                _____
 a ------;-----|     |
         |     | XOR |---- sum
 b --;---|-----|_____|
     |   |      _____
     |   '-----|     |
     |         | AND |---- carry
     '---------|_____|

Persamaan untuk sirkuit di atas dengan cara terlihat seperti ini:

sum = a ^ b
carry = a & b

Setengah penambah kehilangan sesuatu. Kami telah menerapkan aturan pertama - jika hasilnya lebih dari satu digit daripada meneruskan, tapi kami belum menerapkan aturan kedua - jika ada carry tambahkan bersama-sama dengan angka.

Jadi untuk mengimplementasikan penambah penuh, sirkuit tambahan yang dapat menambahkan angka yang lebih dari satu digit, kita perlu mendefinisikan tabel kebenaran:

a b c  |  sum  carry
---------------------
0 0 0  |   0     0
0 0 1  |   1     0
0 1 0  |   1     0
0 1 1  |   0     1
1 0 0  |   1     0
1 0 1  |   0     1
1 1 0  |   0     1
1 1 1  |   1     1

Persamaan untuk jumlah sekarang:

sum = (!a & !b & c) | (!a & b & !c) | (a & !b & !c) | (a & b & c)

Kita bisa melalui proses yang sama untuk memfaktorkan dan menyederhanakan persamaan dan menafsirkannya sebagai rangkaian, dll. Seperti yang telah kita lakukan di atas, tetapi saya pikir jawaban ini terlalu panjang.

Sekarang Anda harus mendapatkan ide tentang bagaimana logika digital dirancang. Ada trik lain yang belum saya sebutkan seperti peta Karnaugh (digunakan untuk menyederhanakan tabel kebenaran) dan kompiler logika seperti espresso (sehingga Anda tidak perlu memperhitungkan persamaan boolean dengan tangan) tetapi dasarnya adalah apa yang saya miliki diuraikan di atas:

1. Mengurai masalah sampai Anda dapat bekerja pada level bit tunggal (digit).

2. Tentukan output yang Anda inginkan menggunakan tabel kebenaran.

3. Konversikan tabel menjadi persamaan boolean dan sederhanakan persamaan tersebut.

4. Menafsirkan persamaan sebagai gerbang logika.

5. Ubah sirkuit logika Anda menjadi sirkuit perangkat keras nyata dengan menerapkan gerbang logika.

Begitulah masalah mendasar (atau lebih tepatnya, level rendah) benar-benar diselesaikan - banyak dan banyak tabel kebenaran. Karya kreatif yang sebenarnya adalah dalam penguraian tugas yang kompleks seperti decoding MP3 ke bit level sehingga Anda dapat mengerjakannya dengan tabel kebenaran.

Maaf saya tidak punya waktu untuk menjelaskan cara menerapkan perkalian. Anda dapat mencoba mengambil celah dengan mencari tahu aturan berapa lama perkalian bekerja kemudian menafsirkannya dalam biner kemudian mencoba untuk memecahnya ke tabel kebenaran. Atau Anda dapat membaca Wikipedia: http://en.wikipedia.org/wiki/Binary_multiplier

instruksi aritmatika dasar dilakukan dengan instruksi perakitan yang sangat efisien.

Instruksi yang lebih kompleks (atau abstrak) dapat dilakukan bersamaan dengan mekanisme looping atau ditangani dalam std libs.

Ketika Anda belajar matematika di perguruan tinggi, Anda akan mulai mempelajari hal-hal seperti Lambda Calculus dan notasi Big-O. Semua ini, dan banyak lagi, digunakan oleh programmer untuk mengevaluasi dan membuat algoritma yang efisien. Bagaimanapun, hal-hal dasar biasanya dilakukan pada level rendah seperti dalam perakitan atau dalam c dengan pointer.

Pengantar yang bagus untuk topik ini adalah "Kode" oleh Charles Petzold.

Dapatkan buku seperti Fundamentals of Digital Logic ... , yang menurut saya masih cukup standar untuk siswa Freshman / Sophomore EE, dan kerjakan sesuai kebutuhan Anda (ed: biayanya kecil, jadi cari edisi bekas atau sebelumnya dari saya t). Itu akan membawa Anda melalui penambahan dan pengganda, dan memberi Anda cukup latar belakang untuk mulai memahami beberapa prinsip di balik apa yang dilakukan perangkat keras.

Jawaban Anda akan, dalam jangka pendek, menjadi "karena cocok dengan sekian banyak logika sederhana untuk membangkitkan perilaku kompleks ini" bukannya "karena itu benar."

Jika Anda ingin mencoba memahami semua prinsip tentang bagaimana program dikompilasi dan dijalankan, lakukan itu bersama-sama, sehingga Anda akhirnya dapat melihat bagaimana semuanya bertemu di tengah.

Ada banyak jawaban bagus di sini. Anda mulai dengan ide yang tepat juga: operasi rumit seperti multiplikasi dibangun dari operasi yang lebih sederhana. Seperti yang Anda duga, ada cara mengalikan yang lebih cepat tanpa instruksi perkalian daripada menggunakan serangkaian tambahan. Setiap perkalian dapat diimplementasikan sebagai jumlah dari perkalian yang lebih kecil, atau sebagai kombinasi dari pergeseran dan penambahan. Contoh:

a = 5 + 5 + 5 + 5 + 5;           // 5*5, but takes 5 operations
b = (5 << 2) + 5;                // 5*5 in only 2 operations
c = (41 << 4) + (41 << 2) + 41   // 41*21 in 4 operations

Divisi juga dapat dipecah menjadi operasi yang lebih kecil. XOR (^) adalah instruksi bawaan pada setiap prosesor yang pernah saya lihat, tetapi meskipun demikian dapat diimplementasikan sebagai kombinasi dari AND, OR, dan NOT.

Saya punya perasaan, bahwa jawaban spesifik akan kurang memuaskan bagi Anda daripada gagasan umum tentang jenis instruksi yang disediakan prosesor dan bagaimana instruksi tersebut dapat digabungkan ke dalam operasi yang lebih kompleks. Tidak ada yang lebih baik untuk rasa ingin tahu seperti itu daripada dosis bahasa rakitan yang sehat. Berikut adalah pengantar yang sangat mudah didekati untuk bahasa assembly MIPS.

Berikut adalah cara prosesor modern dapat menerapkan multiplikasi dua bilangan bulat 64 bit:

Anda tahu bagaimana melakukan perkalian tangan panjang. Untuk mengalikan dua angka 10 digit, Anda akan mengalikan satu angka 10 digit dengan masing-masing dari 10 digit angka lainnya, tulis hasil 11 digit satu di bawah yang lain dan bergeser, lalu tambahkan semua nomor.

Prosesor modern melakukan ini dengan semua 64 demi 64 bit. Namun, perkalian dua angka bit tunggal sangat sederhana: 1 x 1 = 1, semua produk lainnya nol. Ini diimplementasikan dengan logis dan. Dan tidak seperti produk desimal, di mana hasilnya bisa dua digit, produk biner angka bit tunggal selalu satu bit.

Jadi sekarang Anda memiliki 64 baris 64 bit yang perlu ditambahkan. Tapi 64 penambahan angka 64 bit adalah slooooooow. Jadi prosesor menggunakan penambah 3/2 atau penambah 7/3: Jika Anda menambahkan 3 angka bit tunggal, hasilnya bisa 0, 1, 2 atau 3, yang cocok menjadi dua bit. Jika Anda menambahkan 7 angka bit tunggal, hasilnya adalah angka dari 0 hingga 7, yang dapat diwakili oleh 3 bit. IBM mengklaim bahwa mereka dapat membuat penambah 7/3 dengan hanya 18 sirkuit primitif (dokumentasi PowerPC), saya yakin Intel dan ARM dapat melakukan ini juga.

Anda memiliki 4096 bit, kelompokkan menjadi 600 grup 7 bit pada posisi bit yang sama, dan gunakan sekitar 600 7/3 adders untuk mengurangi hasil dari 4096 bit menjadi kurang dari 2.000. Kemudian Anda melakukan hal yang sama lagi, dan lagi, sampai Anda berakhir dengan pasang bit yang dapat dimasukkan ke penambah penuh biasa.