Artikel

2.8: Mendarab dan Membahagi Integer (Bahagian 2)

2.8: Mendarab dan Membahagi Integer (Bahagian 2)



We are searching data for your request:

Forums and discussions:
Manuals and reference books:
Data from registers:
Wait the end of the search in all databases.
Upon completion, a link will appear to access the found materials.

Nilaikan Ungkapan Pemboleh ubah dengan Integer

Sekarang kita dapat menilai ungkapan yang merangkumi pendaraban dan pembahagian dengan bilangan bulat. Ingatlah bahawa untuk menilai ungkapan, ganti nombor sebagai pengganti pemboleh ubah, dan kemudian permudahkan.

Contoh ( PageIndex {10} ): menilai

Nilai (2x ^ 2 - 3x + 8 ) apabila (x = −4 ).

Penyelesaian

Pengganti ( teks teks {red} {- 4} ) untuk x. (2 ( textcolor {red} {- 4}) ^ {2} - 3 ( textcolor {red} {- 4}) + 8 )
Permudahkan eksponen.(2(16) - 3(-4) + 8)
Banyakkan.(32 - (-12) + 8)
Kurangkan.(44 + 8)
Tambah.(52)

Perlu diingat bahawa apabila kita menggantikan (- 4 ) dengan (x ), kita menggunakan tanda kurung untuk menunjukkan pendaraban. Tanpa tanda kurung, kelihatan seperti (2 • −4 ^ 2 - 3 • −4 + ​​8 ).

Latihan ( PageIndex {19} )

Nilai: (3x ^ 2 - 2x + 6 ) apabila (x = −3 )

Jawapan

(39)

Latihan ( PageIndex {20} )

Nilai: (4x ^ 2-x-5 ) apabila (x = −2 )

Jawapan

(13)

Contoh ( PageIndex {11} ): menilai

Nilai (3x + 4y - 6 ) apabila (x = −1 ) dan (y = 2 ).

Penyelesaian

Pengganti x = ( textcolor {red} {- 1} ) dan y = ( textcolor {blue} {2} ). (3 ( teks warna {merah} {- 1}) + 4 ( teks warna {biru} {2}) - 6 )
Banyakkan.(-3 + 8 - 6)
Permudahkan.(-1)

Latihan ( PageIndex {21} )

Nilai: (7x + 6y - 12 ) ketika (x = −2 ) dan (y = 3 )

Jawapan

(-8)

Latihan ( PageIndex {22} )

Nilai: (8x - 6y + 13 ) ketika (x = −3 ) dan (y = −5 )

Jawapan

(19)

Terjemahkan Frasa Kata ke Ungkapan Algebra

Sekali lagi, semua kerja terdahulu kami menerjemahkan kata-kata ke aljabar memindahkan kepada frasa yang merangkumi penggandaan dan pembahagi bilangan bulat. Ingat bahawa kata kunci untuk penggandaan adalah produk dan untuk pembahagian adalah sangka.

Contoh ( PageIndex {12} ): terjemahkan

Terjemahkan ke ungkapan algebra dan permudahkan jika mungkin: produk (- 2 ) dan (14 ).

Penyelesaian

Perkataan itu produk menyuruh kita membiak.

Terjemahkan.(−2)(14)
Permudahkan.−28

Latihan ( PageIndex {23} )

Terjemahkan ke ungkapan algebra dan permudahkan jika mungkin: produk (- 5 ) dan (12 )

Jawapan

(-5(12)=-60)

Latihan ( PageIndex {24} )

Terjemahkan ke ungkapan algebra dan permudahkan jika mungkin: produk (8 ) dan (- 13 )

Jawapan

(8(-13)=-104)

Contoh ( PageIndex {13} )

Terjemahkan ke ungkapan algebra dan permudahkan jika mungkin: hasil bagi (- 56 ) dan (- 7 ).

Penyelesaian

Perkataan itu sangka menyuruh kita membahagi.

Terjemahkan.−56 ÷ (−7)
Permudahkan.8

Latihan ( PageIndex {25} )

Terjemahkan ke ungkapan algebra dan permudahkan jika mungkin: hasil bagi (- 63 ) dan (- 9 )

Jawapan

(- 63 div -9 = 7 )

Latihan ( PageIndex {26} )

Terjemahkan ke ungkapan algebra dan permudahkan jika mungkin: hasil bagi (- 72 ) dan (- 9 )

Jawapan

(- 72 div -9 = 8 )

Konsep kunci

  • Pendaraban Nombor Bertanda
    • Untuk menentukan tanda produk dari dua nombor yang ditandatangani:
      Tanda SamaProduk
      Dua positif
      Dua negatif
      Positif
      Positif
      Tanda yang berbezaProduk
      Positif • negatif
      Negatif • positif
      Negatif
      Negatif
  • Pembahagian Nombor yang Ditandatangani
    • Untuk menentukan tanda bagi dua nombor yang ditandatangani:
      Tanda SamaBerkira
      Dua positif
      Dua negatif
      Positif
      Positif
      Tanda yang berbezaBerkira
      Positif • negatif
      Negatif • Positif
      Negatif
      Negatif
  • Pendaraban dengan (- 1 )
    • Mengalikan nombor dengan (- 1 ) memberikan kebalikannya: (- 1a = -a )
  • Pembahagian dengan (- 1 )
    • Membahagi nombor dengan (- 1 ) memberikan kebalikannya: (a div (-1) = -a )

Amalan Menjadi Sempurna

Gandakan bilangan bulat

Dalam latihan berikut, kalikan setiap pasangan bilangan bulat.

  1. −4 • 8
  2. −3 • 9
  3. −5(7)
  4. −8(6)
  5. −18(−2)
  6. −10(−6)
  7. 9(−7)
  8. 13(−5)
  9. −1 • 6
  10. −1 • 3
  11. −1(−14)
  12. −1(−19)

Bahagikan Integer

Dalam latihan berikut, bahagikan.

  1. −24 ÷ 6
  2. −28 ÷ 7
  3. 56 ÷ (−7)
  4. 35 ÷ (−7)
  5. −52 ÷ (−4)
  6. −84 ÷ (−6)
  7. −180 ÷ 15
  8. −192 ÷ 12
  9. 49 ÷ (−1)
  10. 62 ÷ (−1)

Permudahkan Ungkapan dengan Integer

Dalam latihan berikut, permudahkan setiap ungkapan.

  1. 5(−6) + 7(−2)−3
  2. 8(−4) + 5(−4)−6
  3. −8(−2)−3(−9)
  4. −7(−4)−5(−3)
  5. (−5)3
  6. (−4)3
  7. (−2)6
  8. (−3)5
  9. −42
  10. −62
  11. −3(−5)(6)
  12. −4(−6)(3)
  13. −4 • 2 • 11
  14. −5 • 3 • 10
  15. (8 − 11)(9 − 12)
  16. (6 − 11)(8 − 13)
  17. 26 − 3(2 − 7)
  18. 23 − 2(4 − 6)
  19. −10(−4) ÷ (−8)
  20. −8(−6) ÷ (−4)
  21. 65 ÷ (−5) + (−28) ÷ (−7)
  22. 52 ÷ (−4) + (−32) ÷ (−8)
  23. 9 − 2[3 − 8(−2)]
  24. 11 − 3[7 − 4(−2)]
  25. (−3)2−24 ÷ (8 − 2)
  26. (−4)2 − 32 ÷ (12 − 4)

Nilaikan Ungkapan Pemboleh ubah dengan Integer

Dalam latihan berikut, nilaikan setiap ungkapan.

  1. −2x + 17 apabila (a) x = 8 (b) x = −8
  2. −5y + 14 apabila (a) y = 9 (b) y = −9
  3. 10 - 3m apabila (a) m = 5 (b) m = −5
  4. 18 - 4n apabila (a) n = 3 (b) n = −3
  5. hlm2 - 5p + 5 apabila p = −1
  6. q2 - 2q + 9 apabila q = −2
  7. 2w2 - 3w + 7 apabila w = −2
  8. 3u2 - 4u + 5 apabila u = −3
  9. 6x - 5y + 15 apabila x = 3 dan y = −1
  10. 3p - 2q + 9 apabila p = 8 dan q = −2
  11. 9a - 2b - 8 apabila a = −6 dan b = −3
  12. 7m - 4n - 2 apabila m = −4 dan n = −9

Terjemahkan Frasa Kata ke Ungkapan Algebra

Dalam latihan berikut, terjemahkan ke ungkapan algebra dan permudahkan jika mungkin.

  1. Produk −3 dan 15
  2. Produk −4 dan 16
  3. Keputusan −60 dan −20
  4. Keputusan −40 dan −20
  5. Hasil bagi −6 dan jumlah a dan b
  6. Hasil bagi −7 dan jumlah m dan n
  7. Produk −10 dan perbezaan p dan q
  8. Produk −13 dan perbezaan c dan d

Matematik Setiap Hari

  1. Pasaran saham Javier memiliki 300 saham dalam satu syarikat. Pada hari Selasa, harga saham turun $ 12 sesaham. Apakah kesan keseluruhan terhadap portfolio Javier?
  2. Pengurangan berat Pada minggu pertama program diet, masing-masing lapan wanita kehilangan purata 3 paun. Berapakah jumlah perubahan berat badan bagi lapan wanita itu?

Latihan Menulis

  1. Dalam perkataan anda sendiri, nyatakan peraturan untuk mengalikan dua bilangan bulat.
  2. Dengan kata-kata anda sendiri, nyatakan peraturan untuk membahagi dua bilangan bulat.
  3. Mengapa −24 ≠ (−2)4 ?
  4. Mengapa −42 ≠ (−4)2 ?

Pemeriksaan Kendiri

(a) Setelah menyelesaikan latihan, gunakan senarai semak ini untuk menilai penguasaan anda terhadap objektif bahagian ini.

(b) Pada skala 1–10, bagaimana anda menilai penguasaan bahagian ini berdasarkan respons anda di senarai semak? Bagaimana anda boleh memperbaikinya?


Maharashtra Board 7 Kelas Matematik Penyelesaian Bab 2 Pendaraban dan Pembahagian Amalan Integer Set 8

  1. (-5) × (-7)
  2. (-9) × (6)
  3. (9) × (-4)
  4. (8) × (-7)
  5. (-124) × (-1)
  6. (-12) × (-7)
  7. (-63) × (-7)
  8. (-7) × (15)

Maharashtra Dewan Kelas 7 Matematik Bab 2 Pendaraban dan Pembahagian Amalan Integer Set 8 Soalan dan Aktiviti Inteks

Soalan 1.
Di kelas sebelumnya, kami telah belajar menambahkan dan mengurangkan bilangan bulat. Dengan menggunakan kaedah tersebut, isikan tempat kosong di bawah. (Buku teks ms 11)

  1. 5 + 7 = __
  2. 10 + (-5) = __
  3. -4 + 3 = __
  4. (-7) + (-2) = __
  5. (+8) – (+ 3) = __
  6. (+8) – (-3) = __

Soalan 2.
Tuliskan nombor di setiap tanda kurung untuk mendapatkan jawapan ‘3’ dalam setiap operasi. (Buku teks ms 11)

Penyelesaian:

Soalan 3.
Gandakan bilangan bulat yang diberi dan lengkapkan jadual yang diberikan di bawah. (Buku teks ms 12)

Penyelesaian:


Prompt Visual: Soalan 1, Akta 1

Permulaan video mendorong penonton dengan visual ini:

Berikut adalah usaha untuk membantu penonton & # 8220 melihat & # 8221 3 kumpulan 4 kotak hitam. Dalam video sebelumnya, kami mewakili kotak hitam sebagai bilangan bulat positif. Oleh itu, kami mencari penonton untuk dapat mengatakan dan mungkin menulis:

Oleh kerana saya & # 8217 pasti pelajar yang mengalikan bilangan bulat selesa dengan mengalikan 3 x 4, kami memberikan hasil ini dengan segera sebagai 12 dan menunjukkannya pada garis nombor.

Kami juga menunjukkan bahawa kami dapat menyusun semula kumpulan kami menjadi:


Gunakan Nombor Perdana dan Lakukan Pemfaktoran Perdana

Perhatikan bahawa nombor dalam simbol radikal harus sekecil mungkin. Bagaimana kita boleh melakukan ini? Kita boleh membuat kuasa dua dengan kuasa dua bilangan bulat. Begitu juga, jika ada kuadrat di akar, kita dapat mengubahnya menjadi bilangan bulat dan kemudian memindahkannya keluar dari simbol akar.

Kita bukan sahaja dapat membuat akar kuadrat dari bilangan bulat, tetapi kita juga dapat membuat bilangan bulat dari bahagian akar kuadrat. Sebagai contoh, kami mempunyai perkara berikut.

Bagaimana kita dapat mencari kuasa dengan berkesan dalam simbol akar? Kaedahnya adalah pemfaktoran utama. Faktor pemula adalah menggunakan nombor perdana untuk melakukan pembahagian.

Nombor mempunyai nombor perdana. Nombor perdana adalah nombor yang boleh dibahagi hanya dengan 1 dan nombornya. Nombor perdana merangkumi, seperti berikut.

Sebagai contoh, 7 hanya mempunyai 1 dan 7 pembahagi. Begitu juga, pembahagi untuk 11 hanya 1 dan 11. Membahagi dengan nombor lain tidak menghasilkan bilangan bulat. Sebaliknya, pembahagi 4 adalah 1, 2, dan 4. Bukan hanya 1 dan 4, tetapi 2 juga pembahagi. Oleh itu, 4 bukan nombor perdana.

Kita boleh menukar bilangan bulat (nombor semula jadi) menjadi persamaan pendaraban dengan membahagikannya dengan nombor perdana. Fahami bahawa kebalikan pengiraan pendaraban adalah pemfaktoran utama.

Apabila kita memikirkan faktorisasi utama, istilah itu sukar difahami. Walau bagaimanapun, konsep pemfaktoran utama adalah mudah jika anda memahaminya sebagai cara untuk menguraikan nombor menjadi ungkapan pendaraban. Nombor perdana tidak dapat dibahagikan lagi. Jadi, dengan nombor perdana, kita boleh menukarnya menjadi pendaraban.

Bagaimana Melakukan Pemfaktoran Perdana? Langkah membiak

Bagaimana melakukan pemfaktoran utama? Sebagai contoh, mari kita cuba memasukkan 300 menjadi nombor perdana.

Caranya adalah dengan membahagikan mengikut urutan dari nombor perdana terkecil. Nombor perdana terkecil adalah 2. Oleh itu, mari kita bahagikan 300 dengan 2. Sekiranya kita membahagi 300 dengan 2, kita boleh membahagikannya menjadi 2 dan 150. $ 300 = 2 × 150 $.

Kaedah ini membolehkan kita melakukan pemfaktoran utama sekali. Walau bagaimanapun, 150 bukan nombor perdana. Ia boleh dibahagikan lagi dengan nombor perdana. Oleh itu, mari & bahagikan lagi dengan nombor perdana. Membahagi dengan 2, kita mendapat yang berikut.

Untuk 300, bahagikan dua kali dengan 2 untuk mendapatkan 75. Iaitu, $ 300 = 2 × 2 × 75 $. Walau bagaimanapun, 75 bukan nombor perdana. Oleh itu, mari & # 8217s melakukan pemfaktoran utama.

75 tidak boleh dibahagi dengan 2. Oleh itu, seterusnya kita membahagikannya dengan 3.

Hasilnya ialah $ 300 = 2 × 2 × 3 × 25 $. Dengan cara yang sama, kita juga dapat meneruskan pemfaktoran utama. 25 bukan nombor perdana, dan boleh dibahagi dengan 5. Oleh itu, kita mendapat yang berikut

Membahagi dengan nombor perdana, akhirnya kami menemui fakta berikut.

Oleh kerana 5 adalah nombor perdana, ia tidak dapat dibahagi lebih jauh. Dalam pemfaktoran prima, hentikan pembahagian apabila nombor perdana muncul di akhir. Kemudian kumpulkan semua nombor perdana yang dibahagi dan nombor perdana terakhir. Sejak mengalikan semua nombor perdana dalam bulatan pada rajah di atas untuk mendapatkan 300, pemfaktoran prima selesai.

-Simbol untuk Pemfaktoran Perdana

Apabila kita betul-betul melakukan pemfaktoran utama, kita mesti menghitungnya dengan cekap dan pantas. Oleh itu, kita hampir tidak pernah menggunakan anak panah untuk melakukan pemfaktoran utama seperti yang ditunjukkan di atas. Sebagai gantinya, kami menggunakan simbol berikut.

Dalam penggunaannya, tulis bilangan bulat (nombor semula jadi) di dalam simbol. Juga, tulis nombor perdana di sebelah kiri simbol. Ia kelihatan seperti ini.

Dari segi penggunaan, ia sama seperti rajah anak panah sebelumnya. Kami menguraikan bilangan bulat dengan membaginya dengan nombor perdana. Sebagai contoh, pemfaktoran utama 300 akan kelihatan seperti ini.

Sekiranya nombor perdana muncul di akhir, pemfaktoran perdana selesai. Kemudian, dengan mengumpulkan semua nombor perdana, kita dapat membuat persamaan pendaraban. Maknanya sama dengan rajah anak panah. Perbezaannya ialah dengan menggunakan simbol ini, kita dapat melakukan pemfaktoran utama dengan lebih berkesan.

Jawapan untuk Pemfaktoran Perdana adalah Sama dalam Segala Urutan

By the way, faktorisasi utama dapat dikira dalam urutan apa pun. Kerana jawapan akhir akan sama. Sebagai contoh, pemfaktoran utama 300 akan memberikan jawapan yang sama walaupun urutan pembahagiannya berbeza, seperti yang ditunjukkan di bawah.

Kami telah menjelaskan sebelumnya bahawa, dalam pemfaktoran prima, kita harus membahagikan nombor prima mengikut urutan bilangannya yang lebih kecil. Ini kerana semakin kecil bilangan prima, seperti 2 atau 3, semakin mudah dibahagi, dan semakin sedikit kesilapan yang dilakukan. Namun, dalam beberapa kes, mungkin lebih baik dibahagi dengan bilangan prima yang lebih besar untuk mengelakkan salah perhitungan.

Sekiranya bilangan bulat yang ingin kita bahagikan adalah nombor genap, kita selalu boleh membaginya dengan angka 2. Sebaliknya, jika nombor ganjil, nombor kadangkala tidak jelas jika kita dapat membaginya dengan nombor perdana yang lebih kecil.

Contohnya, nombor perdana yang boleh dibahagi dengan 105. 105 boleh dibahagi dengan 3. Walau bagaimanapun, sukar untuk diperhatikan bahawa ia boleh dibahagi dengan 3. Sebaliknya, mudah diperhatikan bahawa 105 boleh dibahagi dengan 5.

Pengetahuan bahawa kita dapat melakukan pemfaktoran utama dalam urutan apa pun dapat mencegah salah perhitungan dalam matematik. Dengan menggunakan pemfaktoran perdana, kita dapat mengembalikan bilangan bulat ke persamaan pendaraban. Dalam kes ini, jangan risau tentang susunan di mana anda membahagikan dengan nombor perdana.

Keluarkan Nombor Persegi Di Simbol Radikal

Mengapa kita perlu belajar pemfaktoran utama? Ini kerana kami banyak menggunakan pemfaktoran utama dalam pengiraan punca kuasa dua.

Dalam pengiraan punca kuasa dua, ada peraturan bahawa nombor dalam simbol akar harus sekecil mungkin. Untuk melakukannya, kita mesti melakukan pemfaktoran utama. Secara khusus, kita mesti mengeluarkan nombor kuasa dua dalam simbol akar.

Seperti disebutkan sebelumnya, jika ada kotak dalam simbol radikal, kita dapat meletakkan angka di luar tanda akar.

Dengan menggunakan formula ini, kita dapat meletakkan nombor di luar pada tanda akar setelah melakukan pemfaktoran utama. Sebagai contoh, kita telah mengira bahawa pemfaktoran utama 300 menghasilkan yang berikut

Jadi bagaimana $ sqrt <300> $ dapat dikira? Pertimbangkan $ sqrt <300> $ seperti berikut untuk mengeluarkan nombor dari tanda radikal.

Sebab untuk belajar pemfaktoran utama adalah kerana ia digunakan dalam pengiraan punca kuasa dua. Apabila anda mengeluarkan nombor dalam simbol akar, setiap orang melakukan pemfaktoran utama.

Oleh itu, mengapa kita perlu mengeluarkan nombor dalam simbol radikal? Sebabnya mudah: lebih mudah memahami nombornya. Contohnya, nombor $ sqrt <300> $ sukar dijawab dengan serta-merta. Sebaliknya, $ 10 sqrt <3> $ mudah.

$ sqrt <3> ≒ 1.73 $. Oleh kerana ia 10 kali ganda, kita tahu bahawa $ 10 sqrt <3> $ adalah sekitar 17.3. Matematik adalah kajian memahami maksud nombor. Kita mesti membuat nombor mudah difahami, jadi kita mesti mengeluarkan nombor dari simbol akar.

Jangan Bahagikan Nombor Perdana Lain Daripada

Perhatikan bahawa dalam pemfaktoran perdana, kita tidak boleh menggunakan nombor bukan perdana untuk pembahagian. Sekiranya kita mencampurkan nombor bukan perdana, kita tidak dapat mengeluarkan nombor dalam tanda radikal. Sebagai contoh, apabila kita melakukan pemfaktoran utama 300, apa yang akan terjadi jika kita membahagikannya dengan 4?

4 bukan nombor perdana kerana ia boleh dibahagi dengan 2. Walau bagaimanapun, jika kita membahagi dengan 4, banyak orang membuat persamaan berikut.

Hasilnya, kami mendapat jawapan $ 5 sqrt <12> $. Jawapan ini salah, kerana kita dapat menjadikan bilangan di simbol laluan menjadi lebih kecil.

Untuk nombor bukan perdana, seperti 4, kita boleh membahagikannya dengan nombor lain. Hasilnya, kita tidak dapat menukar ke persamaan pendaraban menggunakan nombor terkecil. Oleh itu, nombor dalam tanda akar menjadi lebih besar dan menyebabkan kesalahan pengiraan. Dalam pemfaktoran prima, pastikan untuk dibahagi dengan nombor perdana.


2.8: Mendarab dan Membahagi Integer (Bahagian 2)

Diberi dua rentetan binari yang mewakili nilai dua integer, cari produk dua rentetan. Contohnya, jika rentetan bit pertama adalah & # 82201100 & # 8221 dan rentetan bit kedua adalah & # 82201010 & # 8221, output hendaklah 120.

Untuk kesederhanaan, biarkan panjang dua tali sama dan n.

A Pendekatan Naif adalah mengikuti proses yang kita belajar di sekolah. Satu demi satu mengambil semua bit nombor kedua dan kalikannya dengan semua bit nombor pertama. Akhirnya tambahkan semua pendaraban. Algoritma ini memerlukan masa O (n ^ 2).

Menggunakan Pecah dan perintah, kita dapat mengalikan dua bilangan bulat dalam kerumitan masa yang kurang. Kami membahagikan nombor yang diberikan dalam dua bahagian. Biarkan nombor yang diberi menjadi X dan Y.

Untuk kesederhanaan mari kita anggap bahawa n adalah genap

Produk XY boleh ditulis seperti berikut.

Sekiranya kita melihat formula di atas, terdapat empat pendaraban ukuran n / 2, jadi pada dasarnya kita membahagikan masalah ukuran n menjadi empat sub-masalah ukuran n / 2. Tetapi itu tidak membantu kerana penyelesaian berulang T (n) = 4T (n / 2) + O (n) adalah O (n ^ 2). Bahagian yang rumit dari algoritma ini adalah menukar dua istilah tengah ke bentuk lain sehingga hanya satu penggandaan tambahan yang mencukupi. Berikut adalah ungkapan rumit untuk dua istilah tengah.

Jadi nilai akhir XY menjadi

Dengan muslihat di atas, pengulangan menjadi T (n) = 3T (n / 2) + O (n) dan penyelesaian pengulangan ini adalah O (n 1.59).

Bagaimana jika panjang tali input berbeza dan tidak sama? Untuk menangani kes panjang yang berlainan, kami menambahkan 0 & # 8217 pada awalnya. Untuk menangani panjang ganjil, kami meletakkan lantai (n / 2) bit di kiri setengah dan siling (n / 2) bit pada separuh kanan. Jadi ungkapan untuk XY berubah menjadi berikut.

Algoritma di atas dipanggil algoritma Karatsuba dan ia boleh digunakan untuk asas apa pun.


Tanda aras

Oleh kerana banyak kaedah yang berbeza ditunjukkan dalam jawapan dan tidak ada satu pun jawapan yang benar-benar membuktikan kelebihan dari segi prestasi, saya cuba menanda arasnya sendiri. Rancangan saya adalah menulis jawapan yang mengandungi a pendek jadual dan jawapan pasti kaedah mana yang paling pantas.

Malangnya ia tidak semudah itu. (Tidak pernah.) Nampaknya prestasi formula pembundaran bergantung pada jenis data yang digunakan, penyusun dan tahap pengoptimuman.

Dalam satu kes terdapat peningkatan kelajuan sebanyak 7.5 × dari satu kaedah ke kaedah yang lain. Oleh itu, kesannya boleh berlaku bagi sesetengah orang.

Untuk bilangan bulat panjang, versi naif menggunakan jenis cast untuk mengapung dan std :: ceil sebenarnya adalah yang terpantas. Ini menarik bagi saya secara peribadi kerana saya berhasrat menggunakannya dengan size_t biasanya ditakrifkan sebagai panjang yang tidak ditandatangani.

Untuk int biasa itu bergantung pada tahap pengoptimuman anda. Untuk tahap yang lebih rendah @ penyelesaian Jwodder berprestasi terbaik. Untuk tahap tertinggi std :: ceil adalah tahap yang optimum. Dengan satu pengecualian: Untuk gabungan antara clang / unsigned @ Jwodder's masih lebih baik.

Penyelesaian daripada jawapan yang diterima tidak pernah mengatasi dua yang lain. Anda harus ingat bahawa penyelesaian @ Jwodder tidak berfungsi dengan negatif.

Hasilnya berada di bahagian bawah.


9. Selain Penambahan dan Pengurangan Integer.


Dalam bab sebelumnya, kami membincangkan perincian bagaimana komputer melakukan penambahan dan pengurangan binari. Dengan latar belakang itu, kami kini bersedia untuk meneroka operasi aritmetik yang lebih kompleks. Pendaraban dan pembahagian integer cukup primitif sehingga banyak komputer menerapkannya dalam perkakasan, tetapi cukup kompleks sehingga di banyak komputer lain yang sangat berjaya, semuanya dilakukan sepenuhnya oleh perisian. Ini memperkenalkan subjek penting, pertukaran kejuruteraan yang membawa kepada keputusan mengenai ciri mana yang akan dilaksanakan secara langsung dalam perkakasan dan yang lebih ekonomik dilakukan dalam perisian.

Pendaraban

Sebelum membincangkan pelaksanaan mesin multiplikat dan pembahagian yang cekap, sama ada dalam perkakasan atau perisian, kita mesti mundur dan membincangkan, pertama, algoritma pensil dan kertas dalam bentuk perpuluhan, dan kemudian bagaimana kita dapat melakukannya secara binari. Pertimbangkan masalah mengalikan 128 kali 512 dalam perpuluhan. Inilah cara anda mungkin diajar untuk mengatasi masalah ini dengan menggunakan pensil dan kertas:

Masalah pendaraban
1 2 8 darab
& masa 5 1 2 pengganda
2 5 6 produk separa 2 & kali 128
1 2 8 produk separa 1 & kali 128
+ 6 4 0 produk separa 5 & kali 128
6 5 5 3 6 produk


Lembaran kerja untuk melaksanakan masalah perpuluhan seperti yang ditunjukkan di atas sebenarnya adalah jejak pelaksanaan algoritma. Algoritma ini diteruskan dengan menggandakan darab pertama dengan setiap digit pengganda untuk membuat senarai produk separa. Setiap produk separa ditulis dialihkan ke satu tempat berbanding pendahulunya, sehingga digitnya yang paling tidak signifikan berada di bawah digit pengganda yang sepadan. Peralihan ini sama dengan mengalikan darab dengan sepuluh sebelum mengira setiap produk separa. Akhirnya, algoritma berakhir dengan menambahkan produk separa untuk mengira produk.

Pernyataan algoritma ini tidak bergantung pada asas nombor yang digunakan. Oleh itu, kita boleh menggunakan algoritma yang sama persis ini di pangkalan 16 atau di pangkalan 8 atau bahkan di pangkalan 2. Bahagian yang sukar dari algoritma ini dalam perpuluhan adalah mengalikan darab dengan digit pengganda. Untuk melakukan ini, pelajar sekolah rendah biasa mesti menghafal jadual pendaraban untuk asas 10. Jadual pendaraban asas 2 jauh lebih mudah.

Latihan

a) Tuliskan kod, dalam C, C ++ atau Java, untuk mengalikan dua bilangan bulat positif menggunakan algoritma perpuluhan yang anda gunakan dengan pen dan kertas. Dengan setiap lelaran, anda harus mengumpulkan satu produk separa, mengalikan darab dengan 10, dan membahagi pengganda dengan 10. Anda boleh mengekstrak digit pengganda yang paling tidak signifikan menggunakan operator mod, ditulis sebagai% dalam bahasa-bahasa ini. Gandakan kali ini darab untuk mengira sebahagian produk. Mungkin kelihatan konyol untuk menggunakan pendaraban dan pembahagian untuk membiak, tetapi satu-satunya pembahagi yang digunakan adalah 10, dan satu-satunya pengganda adalah dari 0 hingga 10, jadi kod ini menggunakan sekumpulan operasi yang terhad untuk melaksanakan operasi yang jauh lebih umum.

Algoritma Pendaraban Binari

Untuk mengalikan dua nombor binari menggunakan pensil dan kertas, kita menggunakan algoritma pendaraban yang sama yang akan kita gunakan dalam perpuluhan, tetapi kita melakukannya menggunakan aritmetik binari. Pertimbangkan, sebagai contoh, masalah mengalikan 100 10 dengan 10 10. Dalam perduaan, ini adalah 1100100 2 kali 1010 2 jika kita menyelesaikan masalah menggunakan pensil dan kertas, kita mendapat ini:

Masalah pendaraban binari
1 1 0 0 1 0 0 = 100 darab
& masa 1 0 1 0 = 10 pengganda
0 0 0 0 0 0 0 = 0 & kali 100 produk separa
1 1 0 0 1 0 0 = 1 & kali 100
0 0 0 0 0 0 0 = 0 & kali 100
+ 1 1 0 0 1 0 0 = 1 & kali 100
1 1 1 1 1 0 1 0 0 0 = 10 & kali 100 = 1000

Bengkel ini untuk algoritma binari menunjukkan produk separa yang dikira dengan mengalikan darab dengan setiap digit pengganda. Setiap produk separa ditulis digeser sehingga digit paling penting berada di bawah digit pengganda yang sepadan, dan kemudian produk separa ditambahkan untuk menghitung produk.

Tidak sukar untuk mengurangkan algoritma kertas-dan-pensil ini kepada kod mesin untuk mesin Hawk. Langkah pertama dalam pengurangan tersebut adalah mengatasinya dengan bahasa peringkat tinggi seperti C atau Java:

Algoritma pendaraban binari dalam C

Di atas, kami telah mengalihkan darab satu tempat yang tersisa di setiap lelaran sehingga kami dapat menambahkannya sebagai produk separa apabila bit pengganda yang sesuai adalah nol. Untuk setiap lelaran, kita mengalihkan pengganda satu tempat ke kanan sehingga kita selalu dapat memeriksa bit yang paling tidak signifikan daripada menguji bit yang berbeza untuk setiap lelaran. Kami menguji bit dengan menggunakan bitwise dan operator C untuk menutup semua kecuali bit yang paling tidak signifikan. Berikut adalah kod yang sama menggunakan pengendali yang lebih biasa:

Algoritma pendaraban binari dalam C menggunakan pengendali biasa

Di sini, kami menggantikan pendaraban dan pembahagian dengan dua untuk beralih, dan kami menguji untuk melihat apakah pengganda itu sama atau ganjil dengan memeriksa selebihnya selepas pembahagian dengan dua. Menggunakan multiplicaiton dan pembahagian untuk melaksanakan pendaraban tidak berguna pada mesin tanpa perkalian perkakasan, tetapi penyusun yang baik sering menggantikan peralihan dan manipulasi bit untuk pendaraban dan pembahagian dengan kuasa dua.

Algoritma ini kuno dan telah dijumpai berulang kali. Kadang-kadang disebut algoritma petani Rusia atau multiplicaton Mesir setelah dua dari banyak asal usul rakyat untuk kaedah ini.

Kod darab pertama yang diberikan di atas hanya pengendali terpakai yang terdapat di mesin Hawk. Untuk pergeseran kiri dan kanan, di mana C menggunakan & lt & lt dan & gt & gt, kami mempunyai SL dan SRU, dan untuk dan operator, di mana C menggunakan & amp, kami mempunyai AND. Ini membolehkan kita menulis semula kod C seperti berikut:

Pendaraban binari di Elang

Kod di atas mengambil 8 atau 9 arahan per lelaran gelung, bergantung pada sama ada bit pengganda adalah satu atau sifar. Kod ini ditulis dalam apa yang mungkin disebut gaya kepala-tulang, menggunakan sedikit sebanyak mungkin maklumat tambahan. Sebenarnya, sedikit kajian mengenai arahan peralihan membawa kepada beberapa pengoptimuman yang ketara.

Sebagai peraturan umum, pengoptimuman adalah sesuatu yang terakhir, tetapi calon pengoptimuman pertama adalah rutin yang dipanggil berulang kali dari banyak aplikasi yang berbeza. Subrutin untuk melakukan operasi aritmetik yang tidak dilakukan dalam perkakasan adalah calon yang sangat baik untuk ini. Jelas, kecepatan rutin penggandaan dapat memberikan pengaruh penting pada berbagai aplikasi. Oleh itu, kami akan meneroka kemungkinan mengoptimumkan rutin ini dengan lebih menarik daripada yang kami anggap mengoptimumkan rutin lain yang jarang digunakan.

Semua arahan peralihan di Hawk menetapkan kod keadaan, jadi setelah melakukan instrukiton SRU di hujung gelung, kita dapat menguji untuk melihat apakah darab telah dikurangkan menjadi sifar, menghilangkan keperluan untuk arahan TESTR di bahagian atas gelung dalam semua kecuali lelaran pertama. Kami boleh menguji lebih daripada ini, kerana operator shift juga menetapkan bit bawa dalam kod keadaan untuk melaporkan bit yang dipindahkan dari operan, jadi arahan SRU, dengan jumlah peralihan satu juga memberitahu kami jika operan itu genap atau ganjil sebelum peralihan. Ini membawa kita kepada kod pendaraban tanpa tanda yang lebih cepat berikut:

Pendaraban binari lebih cepat di Hawk

Versi yang diperbaiki ini memerlukan sama ada 5 atau 6 arahan setiap lelaran, jadi ia akan berjalan sekitar 30% lebih cepat daripada kod asal. Tambahan pula, ia menggunakan satu register yang kurang kerana cara bit pengganda diuji. Satu kos pengoptimuman ini adalah bahawa lebih sukar untuk menulis komen seperti C kerana bahasa C tidak lagi menangkap apa yang dilakukan oleh beberapa kod di atas dengan tepat. Kod ini sama baiknya dengan yang anda harapkan dari kod bahasa perhimpunan yang baik, tetapi pengoptimuman lebih lanjut dapat dilakukan. Pertimbangkan perkara berikut:

Pendaraban binari yang lebih pantas untuk Hawk

Versi baru ini mengambil 4 atau 6 arahan per lelaran, sedikit lebih pantas setiap lelaran daripada kod sebelumnya. Selanjutnya, pendua arahan kembali menyimpan beberapa arahan setiap panggilan. Adakah perubahan ini benar-benar membawa kepada peningkatan prestasi pada CPU sebenar mesti ditentukan oleh pengujian empirikal. Secara bersama, perubahan ini menghancurkan struktur kawalan bersih yang asli, mencegah penggunaan gaya ulasan bahasa tingkat tinggi. Pengoptimuman yang menghasilkan kod yang hampir tidak dapat dibaca hanya dibenarkan dalam kod kritikal prestasi.

Pengoptimuman ini berfungsi menuju jalan buntu. Sama seperti kunci untuk operasi rentetan pantas di Hawk adalah bekerja dengan blok aksara, kunci untuk pendaraban cepat adalah dengan beroperasi di pangkalan nombor yang lebih tinggi daripada 2. Untuk Hawk, pangkalan 16 berfungsi dengan baik. Bab 13 manual Hawk memberikan kod darab bilangan bulat tanpa tanda yang mempunyai kos terburuk sebanyak 2.8 arahan per bit untuk mengira produk 32-bit kod ini bahkan kurang dapat dibaca daripada mana-mana kod di atas, tetapi jika kelajuan adalah objek, ia adalah pemenang yang jelas.

Latihan

b) Balikkan syiling untuk menghasilkan pendarab 8-bit rawak dan pengganda 4-bit rawak. Gandakan mereka menggunakan algoritma pendaraban binari kertas dan pensil, kemudian periksa karya anda dengan menukar pengganda, darab dan produk menjadi perpuluhan untuk pengesahan.

c) Tulis semula algoritma pendaraban binari dalam C agar berfungsi di pangkalan 16. Ini hanya melibatkan perubahan yang sangat kecil pada kod yang diberikan di atas: Anda mesti membenarkan pengganda digit mempunyai lebih daripada 2 nilai yang mungkin (sifar dan satu) dan anda mesti mengubah semua merujuk kepada radix dari 2 hingga 16 (atau secara bergantian, ubah semua peralihan satu-bit ke peralihan 4-bit).

d) Apa yang berlaku dengan kod pendaraban binari Hawk jika anda mengalikan nombor bersama-sama yang menghasilkan hasil 2 32 atau lebih besar. Sebagai contoh, apa yang berlaku jika anda mengira 125,000 kuasa dua menggunakan kod ini? 125,000 hampir 2 17, jadi jawapannya hampir 2 34.

Pendaraban Binari dalam Perkakasan

Dalam kod pendaraban binari yang diberikan di atas, mengalikan dua nombor 32-bit mengambil 32 shift dan hingga 32 tambah. Kita boleh melakukan semua ini secara selari dengan menggunakan 31 penambah. Inilah cara skema selari berfungsi untuk dua nombor 3-bit a dan b untuk memberikan produk 6-bit p.

Perkakasan pendaraban untuk pengganda 3-bit

Litar ini tidak dioptimumkan. Baris penambah teratas dapat dihilangkan, dan penambah paling kanan di setiap baris dapat diganti dengan penambah setengah. Jumlah pintu logik yang diperlukan dianggarkan seperti berikut:

Mengira kos pengganda cepat
Satu penambah penuh 12
32 bit setiap perkataan & masa 32
gerbang setiap penambah 32-bit 384
31 penambah untuk menambah 32 produk separa & masa 31
Subtotal: Kos penambahan sebahagian produk 11904
dan gerbang untuk mengira produk separa 32
32 produk separa & masa 32
Subtotal: Kos pengiraan sebahagian produk 1024
Anggaran jumlah gerbang untuk pendaraban pantas 12928

Ini agak tidak menggalakkan. 12000 gerbang lebih dari cukup untuk membina keseluruhan CPU. Sebaliknya, diperlukan lebih dari 2000 gerbang untuk melaksanakan keseluruhan unit logik aritmetik Hawk dan shifter, dan ini adalah pusat bagi kebanyakan pengiraan. Menambah satu fungsi tambahan dengan menggunakan tujuh kali jumlah perkakasan nampaknya bukan pendekatan yang sangat ekonomik untuk reka bentuk komputer. Oleh itu, hanya sebilangan kecil tetapi komputer berprestasi tertinggi yang merangkumi pengganda berkelajuan tinggi yang beroperasi dengan cara brute-force ini.

Sebilangan besar komputer yang mempunyai perkakasan berganda melakukan pendaraban menggunakan unit aritmetik-logik yang sama seperti yang mereka gunakan untuk penambahan, mengitar data melalui unit aritmetik-logik sebanyak yang diperlukan untuk menghitung produk. Inilah sebabnya mengapa, apabila anda melihat data untuk kelajuan pelbagai petunjuk pada komputer sebenar, adalah biasa bahawa pendaraban bilangan bulat adalah 10 atau lebih kali lebih lambat daripada penambahan bilangan bulat. Pada Intel Pentium, yang diperkenalkan pada tahun 1993, perkakasan dapat melaksanakan dua arahan tambah integer secara selari pada 1/10 waktu yang diperlukan untuk melaksanakan satu arahan darab bilangan bulat.

Pendaraban pantas oleh Pemalar

Oleh kerana kelajuan penggandaan perkakasan yang perlahan pada kebanyakan komputer, penulis penyusun telah lama diminta untuk mengelakkan penggunaan petunjuk darab setiap kali mereka dapat menemui urutan pergeseran pendek dan menambahkan arahan yang akan melakukan perkara yang sama. Pengoptimuman ini dapat dinyatakan dengan mudah dalam bahasa seperti C, C ++ atau Java:

Pengoptimuman untuk mengelakkan pendaraban
asli penggantian
a * 2 a & lt & lt 1
a * 3 (a & lt & lt 1) + a
a * 4 a & lt & lt 2
a * 5 (a & lt & lt 2) + a
a * 6 ((a & lt & lt 1) + a) & lt & lt 1
a * 7 (a & lt & lt 3) - a
a * 8 a & lt & lt 3
a * 9 (a & lt & lt 3) + a
a * 10 ((a & lt & lt 2) + a) & lt & lt 1

Jangan menulis jenis kod ini dalam program C atau Java anda kecuali tujuan anda adalah menulis kod yang tidak dapat difahami oleh siapa pun. Biarkan penyusun melakukan pengoptimuman untuk anda. Sebaliknya, jika anda menulis bahasa pemasangan atau menulis penyusun, anda perlu mengetahui pengoptimuman ini. Sebagai tambahan, jika anda ingin menulis kod pantas, adalah berguna untuk memahami apa yang akan dilakukan oleh penyusun yang baik terhadap kod anda.

Secara umum akan ada satu produk parsial untuk ditambahkan untuk masing-masing dalam perwakilan binari pengganda, ditambah operator shift yang diperlukan untuk menyelaraskan produk separa. Pada Pentium, di mana penggandaan bilangan bulat mengambil masa sekitar sepuluh kali sepanjang pergeseran atau penambahan sederhana, penyusun yang baik biasanya menggunakan campuran pergeseran dan menambahkan petunjuk setiap kali pengganda tetap mempunyai lima atau kurang satu bit.

Kadang-kadang, bagaimanapun, kita dapat melakukan yang lebih baik lagi, seperti yang digambarkan untuk pendaraban dengan tujuh dalam jadual di atas. Dalam kes itu, kita mungkin telah menggunakan (((a & lt & lt1) + a) & lt & lt1) + a, menambahkan tiga istilah yang sesuai dengan 3 satu bit dalam pengganda. Sebaliknya, dalam jadual di atas, kita didarabkan dengan lapan dan kemudian tolak.

Cara lain yang boleh kita gunakan adalah memfaktorkan nombor dan mengalikan dengan setiap faktor berturut-turut. Sebagai contoh, untuk mengalikan dengan 100, kita dapat mengalikan dengan 10 dua kali berturut-turut, atau kita dapat mengalikan dengan 5 dua kali berturut-turut dan kemudian mengalikan hasilnya dengan 4.

Pengoptimuman alternatif untuk pendaraban dengan 100
a * 100 (((a & lt & lt 1) + a) & lt & lt 3) + a) & lt & lt 2
a * 10 * 10 t = ((a & lt & lt 2) + a) & lt & lt 1
((t & lt & lt 2) + t) & lt & lt 1
a * 5 * 5 * 4 t = ((a & lt & lt 2) + a)
((t & lt & lt 2) + t) & lt & lt 2

Manakah yang paling pantas di mesin tertentu? Secara umum, memeriksa kod bahasa tahap tinggi hanya membenarkan tekaan terpelajar. Arkitek komputer klasik menggunakan kira-kira satu arahan bagi setiap pengendali, dan apabila pendaftaran untuk mendaftar operasi tersedia, penyerahan kepada pemboleh ubah sementara yang digunakan untuk hasil perantaraan mungkin bebas. Untuk mesin seperti itu, yang penting ialah jumlah pengendali dalam ungkapan tersebut. Ini mendorong kita untuk meneka bahawa pendaraban binari dengan 100 akan mengalikan dengan mengalikan dengan 5 dua kali dan kemudian dengan 4, mengambil 3 shift dan 2 tambah, sementara Mengalikan dengan 10 dua kali berturut-turut akan lebih perlahan, mengambil 4 shift dan 2 tambah.

Perkara pertama yang dapat kita simpulkan dari anggaran prestasi di atas adalah bahawa semua kaedah pendaraban di atas dengan 100 akan lebih cepat daripada perkakasan yang berlipat ganda pada mesin seperti Pentium. Angka menunjukkan bahawa pendaraban dengan sepuluh dua kali berturut-turut mungkin sedikit lebih perlahan, tetapi dengan perbezaan hanya satu operasi antara anggaran terpantas dan paling lambat kita, apa yang sebenarnya harus kita simpulkan adalah bahawa pendekatan yang berbeza ini serupa.

Untuk mengurangkannya kepada kod mesin, kita mesti melihat repertoar arahan shift yang tersedia. Hawk mempunyai dua arahan shift kiri, MOVSL, yang melakukan register untuk mendaftar bergerak ditambah shift, dan ADDSL, yang mengalihkan kandungan satu register dan kemudian menambahkan register lain ke dalamnya. Kod bahasa pemasangan SL benar-benar ADDSL dengan daftar kedua ditetapkan ke sifar, menunjukkan bahawa tidak ada yang perlu ditambahkan. Instruksi perubahan dan penambahan yang serupa dimasukkan dalam beberapa seni bina yang dirancang selepas akhir tahun 1970-an pada awal tahun 1980-an, sebuah kumpulan di Hewlett Packard adalah yang pertama menerangkan, secara terperinci, bagaimana memanfaatkan sepenuhnya instruksi ini. Inilah cara kami dapat menggunakannya di Hawk:

Pendaraban dengan pemalar di Hawk
SL R3,1 R3 = R3 * 2 = R3 & lt & lt 1
ADDSL R3, R3,1 R3 = R3 * 3 = (R3 & lt & lt 1) + R3
SL R3,2 R3 = R3 * 4 = R3 & lt & lt 2
ADDSL R3, R3,2 R3 = R3 * 5 = (R3 & lt & lt 2) + R3
SL
ADDSL
R3,1
R3, R3,1
R3 = R3 * 6 = R3 * 2 * 3
NEG
ADDSL
R1, R3
R3, R1,3
R3 = R3 * 7 = (R3 & lt & lt 3) - R3
SL R3,3 R3 = R3 * 8 = R3 & lt & lt 3
ADDSL R3, R3,2 R3 = R3 * 9 = (R3 & lt & lt 3) + R3
SL
ADDSL
R3,1
R3, R3,2
R3 = R3 * 10 = R3 * 2 * 5


Arahan Hawk ADDSL membolehkan kita mengalikan dengan pelbagai pemalar kecil hanya dalam satu atau dua arahan. Pendaraban dengan 11 mengambil tiga arahan, tetapi terdapat juga tiga urutan arahan untuk didarab dengan semua bilangan bulat yang lebih besar hingga 38 dan bagi banyak di atasnya. Sebilangan besar ini didokumentasikan dalam Bab 10 manual CPU Hawk.

Latihan

e) Tukarkan setiap tiga algoritma yang diberikan di atas untuk didarab dengan 100 menjadi urutan instrukiton Hawk yang dikodkan dengan ketat yang menghitung R3 = R3 * 100. Ranking mengikut urutan kepantasan. (Perhatikan bahawa mungkin ada seri, dan anggap anda dapat menggunakan R1 sebagai daftar tambahan.)

f) Tulis kod elang untuk mengalikan R3 dengan 55.

g) Tulis kod elang untuk mengalikan R3 dengan 60.

h) Tulis kod elang untuk mengalikan R3 dengan 47.

i) Apakah pengganda malar terkecil untuk Hawk yang memerlukan urutan 4 arahan? (Semua urutan yang diberikan dalam manual Hawk hanya mempunyai 3 arahan.)

Mengapa Tiada Arahan Berganda di Elang

Kami sekarang telah cukup memahami untuk memahami mengapa Hawk dan beberapa seni bina komputer berprestasi tinggi 32-bit moden yang lain tidak mempunyai sokongan perkakasan untuk pendaraban bilangan bulat. Jawapannya terletak pada kekerapan program aplikasi yang sebenarnya perlu digandakan. Kajian berskala besar mengenai program sebenar menunjukkan bahawa sebahagian besar operasi darab dalam kebanyakan kod sebenar melibatkan pendaraban dengan pemalar kecil. pendaraban pemboleh ubah dengan pemboleh ubah jauh lebih jarang.

Oleh kerana kami mempunyai urutan arahan yang sangat pendek untuk didarabkan dengan pemalar kecil yang paling biasa, dan kerana kami mempunyai subrutin yang relatif cepat untuk kejadian yang jarang berlaku apabila perlu mengalikan dua pemboleh ubah, ada sedikit kelebihan untuk pelaksanaan perkalian perkalian.

Katakan perkakasan sangat murah sehingga kita dengan mudah mampu mendedikasikan ribuan gerbang ke unit gandaan perkakasan cepat. Satu persoalan kejuruteraan yang penting adalah, apa kegunaan bersaing yang dapat kita buat dari pintu-pintu logik tersebut? Pendaraban perkakasan yang cepat mungkin mempercepat pengiraan sebanyak beberapa peratus. Bolehkah kita menggunakan gerbang tersebut untuk memberi kesan yang lebih baik di tempat lain dalam CPU? Mungkin kita dapat menggunakan gerbang tersebut untuk membangun CPU kedua, berpotensi menggandakan kelajuan komputer, atau menggunakan gerbang tersebut untuk membangun lebih banyak daftar atau membangun memori cache yang mempercepat semua rujukan memori.

Bahagian

Untuk membahagi nombor dengan yang lain menggunakan pensil dan kertas, kami menggunakan algoritma pembahagian panjang klasik yang diajar secara tradisional di sekolah rendah. Seperti pendaraban pensil dan kertas, algoritma pembahagian ini melibatkan pembinaan dan pengisian lembaran kerja semasa pengiraan berjalan. Pertimbangkan masalah membahagi 128 menjadi 65538:

Masalah pembahagian
5 1 2 sangka
pembahagi 1 2 8 ) 6 5 5 3 8 dividen
& ndash 6 4 0 = 5 & kali 128
1 5 3 8
& ndash 1 2 8 = 1 & kali 128 produk separa
2 5 8
& ndash 2 5 6 = 2 & kali 128
2 baki

Pembahagian panjang melibatkan satu siri pengurangan dari dividen. Nilai yang dikurangkan disebut produk separa kerana ia adalah produk separa yang akan kita tambah dalam mengalikan hasil bagi pembahagi untuk mendapatkan dividen (dikurang selebihnya). Anda boleh mengesahkannya dengan membandingkan dengan masalah pendaraban yang diberikan sebelumnya dalam bab ini. Setiap produk separa adalah hasil daripada digit bagi kali ganda pembahagi. Bahagian sulit dengan pembahagian panjang perpuluhan adalah belajar mengira digit bagi. Sekiranya kita melakukan ini secara binari, bahagian itu menjadi lebih mudah kerana hanya ada dua pilihan untuk setiap digit.

Bahagian Perduaan

Cara klasik untuk membahagi satu nombor binari dengan nombor yang lain adalah dengan mengalihkan kedua-dua bahagian dan dividen ke kiri pada setiap langkah, bukannya menahannya secara statik dan mengalihkan sebahagian produk ke kanan. Kita mulakan dengan dividen 32-bit dengan 32 bit yang paling tidak signifikan dari register 64-bit, kemudian setelah 32 langkah shift-and-subtract, selebihnya berada pada 32 bit yang tinggi dan hasil bagi 32 bit yang rendah. Kita boleh menulisnya dalam C pada mesin yang menyokong jenis int menggunakan 32 bit dan panjang panjang menggunakan 64 bit:

Algoritma pembahagian binari dalam C

Kod yang pendek tetapi sukar ini menghitung selebihnya dan hasilnya, tidak kira yang diperlukan. Versi C tidak dapat mengembalikan keduanya, tetapi mengembalikan keduanya mudah dalam bahasa perhimpunan.

Untuk menulis kod Hawk yang setara, kita memerlukan cara untuk menukar nombor 64-bit satu tempat ke kiri. Kami akan menyimpan kuantiti 64-bit dalam dua daftar dan kemudian menggunakan aspek sekunder arahan peralihan untuk membantu: Di Hawk (dan pada kebanyakan mesin lain), shift menggunakan bit bawa untuk melaporkan bit yang dipindahkan dari hasilnya. Selepas pergeseran kiri satu bit, bendungan memegang bit tanda lama. Oleh itu, untuk pergeseran kiri yang panjang, kita perlu menambahkan bawaan ke dalam bit rendah pada separuh hasil yang tinggi. Terdapat banyak cara untuk melakukan ini di Hawk:

Peralihan kiri 64-bit di Hawk


Versi pertama di atas menggunakan cabang bersyarat untuk menguji bawaan setelah mengalihkan separuh nombor yang rendah, dan kemudian secara eksplisit menambahkannya ke separuh tinggi jika diperlukan. The Hawk mempunyai arahan khas untuk menambahkan jumlah penjumlahan dari dua daftar, ADDC. Versi kedua menggunakan ini untuk menggantikan cawangan dan kenaikan bersyarat. Perhatikan bahawa menambahkan nombor untuk dirinya sendiri menggesernya ke satu tempat, sehingga ADDC dapat bergeser ketika menambah jumlahnya. Ini memberikan versi terakhir dan terpantas. Untuk kelengkapan, berikut adalah pergeseran kanan 64-bit yang pantas menggunakan arahan khas yang disebut ADJUST:

Pergeseran kanan 64-bit di Hawk

Pergeseran ketepatan tinggi ini memberi kami alat yang kami perlukan untuk kod algoritma pembahagi di Hawk:

Bahagian Perduaan di Elang


Di sini, kami telah menyebut separuh tinggi daftar kerja 64-bit kami sebagai baki dan separuh rendah sebagai hasil bagi, kerana itulah yang akhirnya mereka pegang. Semasa kod berulang, bit dividen dialihkan keluar dari daftar hasil ke baki sebelum setiap produk separa dikurangkan.

Kami membuat satu perubahan dalam organisasi gelung ketika kami beralih dari kod C asal ke kod yang diberikan di atas. Daripada menjadikan kiraan gelung naik dari 0 hingga 32, kami memulakan pemboleh ubah kawalan gelung pada 32 dan dikurangkan menjadi sifar. Pengoptimuman ini memungkinkan kami menguji penghentian dengan memeriksa kod keadaan setelah penurunan, menghilangkan perlunya instruksi perbandingan di badan gelung.

Terdapat pengoptimuman tambahan yang dapat dilakukan pada gelung apa pun, yang disebut loop unrolling. Dalam kes umum, penggulungan gelung melibatkan mereplikasi badan gelung, termasuk ujian untuk penghentian gelung. Ini memperbesar badan gelung dan menghilangkan arahan cabang per replika. Semasa membongkar gelung pasti, di mana bilangan pengulangan badan gelung terbahagi secara merata menjadi bilangan lelaran, kita dapat menyimpan lebih banyak lagi dengan menghilangkan ujian pendua untuk penghentian gelung.

Secara amnya, pengulangan gelung mempunyai kesan terbesar pada gelung dengan badan yang sangat kecil, dan algoritma pembahagi yang diberikan di sini adalah contoh yang baik. Inilah hasilnya, yang diterapkan pada kod C di atas:

Pembahagian binari dengan putaran gelung di C

Melepaskan gelung satu langkah mengurangkan bilangan lelaran menjadi 16, menghilangkan separuh daripada arahan yang digunakan untuk meningkatkan dan menguji penghitung gelung dan separuh arahan cabang kembali ke bahagian atas gelung. Melepaskan gelung 4 langkah mengurangkan bilangan lelaran menjadi 8 sambil mengurangkan bahagian atas sekali lagi. Melepaskan gelung sebanyak 32 kali sepenuhnya akan menghilangkan pemboleh ubah kawalan gelung dan arahan cabang yang berkaitan dengan perbelanjaan penduaan skala besar gelung.

Latihan

j) Tuliskan kod Hawk untuk pergeseran kiri 96-bit dan untuk pergeseran kanan 96-bit, menyimpan operan dalam daftar 3, 4 dan 5, paling tidak penting 32-bit terlebih dahulu.

k) Tulis versi baru kod pembahagian Hawk yang diberikan di sini dengan badan gelung tidak digulung satu langkah seperti dalam kod C yang diberikan di atas.

Ditandai Berkali dan Membahagi

Kaedah yang paling jelas untuk menangani pendaraban dan pembahagian yang ditandatangani adalah dengan mengingat tanda semua operan dan kemudian mengambil nilai mutlaknya terlebih dahulu. Setelah mengira produk dengan nilai mutlak, hasilnya kemudiannya akan ditolak sekiranya operan itu bertentangan. Ini digambarkan di sini untuk pendaraban, tetapi sama mudahnya untuk pembahagian.

Pendekatan naif untuk pendaraban bertanda di C

Satu-satunya masalah dengan pendekatan ini adalah bahawa ia tidak rumit. Selagi kita menggunakan nombor pelengkap dua, kita boleh memanfaatkan tafsiran nilai tempat mudah bagi digit binari nombor pelengkap dua. Untuk bit 0 hingga 30 daripada nombor pelengkap 32-bit dua, berat bit i adalah 2 i, sama dengan berat bagi nombor perduaan sederhana. Untuk bit yang paling ketara, bit tanda, beratnya ditolak, jadi berat bit tanda adalah & ndash2 31. Ini membawa kepada fakta yang luar biasa bahawa, apabila mengalikan bilangan bulat pelengkap dua ditandatangani, produk separa akhir harus dikurangkan untuk memberikan hasil bertanda yang betul yang betul.

Untuk menggunakan fakta ini, kami mengekodkan algoritma darab kami untuk menggunakan gelung pasti dan bukan gelung tak tentu, melakukan 31 langkah darab di dalam gelung dan kemudian mengendalikan produk separa yang dihitung dari bit tanda di luar gelung, mengurangkan di mana semua produk separa lain telah ditambah. Berikut adalah contoh berlipat ganda, dikodkan menggunakan pergeseran kiri untuk pengganda dan produk:

Pendaraban yang ditandatangani pantas di Hawk

Kod di atas ringkas, tetapi dapat dipercepat dengan semua kaedah yang telah kita bincangkan. Sebagai contoh, gelung mungkin sebahagiannya tidak digulung untuk mengurangkan bilangan lelaran atau sepenuhnya tidak digulung untuk menghilangkan pembilang gelung. Pertimbangkan, sebagai contoh, menggunakan unrolling 3 arah, di mana gelung akan berulang 10 kali dengan 3 langkah darab di badan gelung, dan kemudian satu lagi langkah mengalikan di luar badan gelung sebelum langkah terakhir yang mengurangkan darab jika pengganda adalah negatif.

Latihan

l) Tulis kod Hawk untuk rutin pendaraban yang naif yang memanggil rutin pendaraban tanpa tanda yang diberikan sebelumnya.

m) Tuliskan kod C, C ++ atau Java untuk rutin pemisah yang ditandatangani naif yang memanggil sesuatu yang serupa dengan rutin pembahagi yang tidak ditandatangani yang diberikan sebelumnya.

n) Ubah suai kod untuk rutin pendaraban yang ditandatangani yang diberikan di sini supaya ia mengira produk 64-bit dalam daftar 3 dan 4. Perhatikan bahawa ini adalah pekerjaan yang mudah: yang perlu anda lakukan hanyalah mengganti dua peralihan daftar bebas 3 dan 4 dengan satu peralihan 64-bit.

o) Ubah suai kod untuk rutin pendaraban yang ditandatangani yang diberikan di sini untuk menggunakan 15 lelaran di mana setiap lelaran merangkumi pengulangan gelung.

p) Ubah suai kod untuk darab bertanda yang diberikan di sini untuk melakukan pendaraban tanpa tanda, dan kemudian bandingkan dengan kod darab yang tidak ditandatangani yang diberikan sebelumnya. Mana yang lebih cepat, dan mengapa?

Aritmetik Berketepatan Tinggi

Seperti yang telah dinyatakan, seni bina Hawk merangkumi sokongan untuk pergeseran panjang yang terdiri daripada sejumlah pergeseran 32-bit yang lebih pendek. Arahan sokongan khas yang sama yang memungkinkan ini juga berguna untuk penambahan dan pengurangan ketepatan tinggi. Oleh itu, jika ada masalah yang memerlukan penggunaan nombor 128-bit, misalnya, menggunakan register 4 hingga 7 untuk menahan satu nombor dan register 8 hingga 11 untuk menahan yang lain, kita dapat menambahkan atau mengurangkan dua nombor ini sebagai berikut:

Penambahan dan pengurangan 128-bit di Hawk


Terdapat dua cara untuk membina rutin penggandaan berketepatan tinggi. Salah satunya ialah dengan mengambil rutin penggandaan binari sederhana dan memperluasnya, menggunakan peralihan berbilang daftar dan penambahan berbilang daftar. Yang lain adalah membina rutin berketepatan tinggi dari pelbagai aplikasi rutin berketepatan rendah. Diberikan penggandaan 32-bit yang tidak ditandatangani, di mana ab dan cd adalah kuantiti 64-bit, dengan a dan c menjadi separuh yang paling signifikan dari masing-masing dan b dan d separuh yang paling signifikan, produk ab & kali cd adalah & kali c & kali2 64 + a & kali d & kali2 32 + b & kali c & kali2 32 + b & kali d.

Perhatikan bahawa peralihan dengan gandaan 32 bit, sama dengan pendaraban dengan kuasa 2 32, dilakukan secara sepele dengan berpindah ke (atau menambah) daftar bernombor tinggi yang sesuai dalam susunan daftar yang memegang setiap hasil ketepatan berganda. Hasilnya, setiap produk di sini dapat dikira menggunakan penggandaan 32-bit yang menghasilkan produk 64-bit, jadi hanya jumlah akhir yang memerlukan petunjuk penambahan yang panjang. Algoritma pendaraban ketepatan yang diperluas ini didokumentasikan secara menyeluruh oleh Charles Babbage pada abad ke-19, walaupun ia melakukannya dalam perpuluhan.

Latihan

q) Tulis kod Hawk untuk pergeseran kanan 128-bit.

r) Tulis kod Hawk untuk pergeseran kiri 128-bit.

s) Tulis kod Hawk untuk bilangan bulat tak bertanda 64 bit darab, menghasilkan produk 128-bit. Terdapat dua cara yang jelas untuk melakukan ini, satu menggunakan pergeseran panjang dan menambah untuk setiap 64 lelaran, dan satu menggunakan 4 panggilan ke rutin penambahan 32-bit.

Aritmetik Perpuluhan Berkod Binari

Walaupun aritmetik binari mudah, itu bukan satu-satunya alternatif. Sebilangan besar komputer yang dibina pada tahun 1940-an dan 1950-an menggunakan perpuluhan, dan perpuluhan tetap biasa hari ini kerana beberapa bahasa pengaturcaraan, terutama COBOL, memerlukannya. Benar, COBOL adalah bahasa kuno, tetapi berjuta-juta baris kod yang ditulis dalam COBOL tetap menjadi pusat sistem maklumat pengurusan korporat dari kebanyakan syarikat besar di Amerika Syarikat, jadi sokongan yang cekap untuk bahasa ini tidak dapat diabaikan. Selain itu, banyak instrumen makmal menggunakan perpuluhan kerana output utamanya adalah untuk paparan perpuluhan, dan ketika instrumen ini memiliki antaramuka komputer, data biasanya dikirim dalam bentuk perpuluhan. Perwakilan nombor dalaman yang digunakan pada kebanyakan kalkulator poket juga perpuluhan.

Bagaimana nombor perpuluhan dimanipulasi pada komputer binari? Terdapat dua skema umum, perpuluhan berkod binari dan tiga lebihan. Kedua-duanya menggunakan 4 bit per digit perpuluhan, tetapi sistem pengkodan berbeza:

Perwakilan digit perpuluhan
BCD perpuluhan Lebihan 3
0000 0 0011
0001 1 0100
0010 2 0101
0011 3 0110
0100 4 0111
0101 5 1000
0110 6 1001
0111 7 1010
1000 8 1011
1001 9 1100


Perpuluhan berkod binari atau BCD menggunakan perwakilan binari semula jadi untuk setiap digit perpuluhan, sementara lebihan 3 menambah tiga pada nilai binari sederhana setiap digit. Sebab ini berguna akan menjadi lebih jelas dalam sekejap, tetapi satu kelebihan daripadanya ialah lebihan tiga sistem adalah simetri dalam arti bahawa nombor 5 dan ke atas ditunjukkan oleh pelengkap nombor di bawah 5. Ini menjadikan pelengkap 10 perwakilan nombor bertanda berfungsi dengan baik, jika diandaikan bahawa nilai digit perpuluhan paling signifikan 5 atau lebih besar mewakili nombor negatif.

Bahagian yang sukar dalam merancang penambah perpuluhan adalah memikirkan kapan untuk menghasilkan pelaksanaan setiap kedudukan digit perpuluhan. Kami melakukan ini apabila jumlah dua digit lebih besar daripada 10. Kita dapat membina penambah perpuluhan secara langsung, dengan litar untuk membandingkan digit jumlah dengan 10, tetapi ada cara yang lebih mudah. Caranya, yang diketahui sejak tahun 1950-an, adalah dengan bias nombor supaya pilihan binari sederhana dari setiap kedudukan digit adalah tepat. Kami melakukan ini dengan menambahkan 6 pada setiap digit BCD jumlahnya, atau secara bergantian, dengan menggunakan perwakilan lebihan-3 di mana 3 tambahan disertakan dalam setiap digit. Sudah tentu, setelah ini dilakukan, pembetulan mesti dibuat terhadap hasilnya. Berikut adalah contoh masalah penambahan, yang dilakukan dengan nombor BCD 2-digit 8-bit:

Penambahan BCD
1 1 1 bawa bit
0 1 0 0 0 1 0 1 tambah = 45
0 1 0 0 0 1 1 0 augend = 46
+ 0 1 1 0 0 1 1 0 pukul enam
1 1 1 1 0 0 0 1 jumlah awal
& ndash01 1 0 0 0 0 0 pembetulan
1 0 0 1 0 0 0 1 jumlahnya = 91

Di sini jumlah awal untuk digit perpuluhan yang menghasilkan kurs adalah betul, tetapi jumlah untuk digit yang tidak menghasilkan kurs dihentikan sebanyak 6. Untuk memperbaikinya, kami tolak 6 dari digit yang tidak menghasilkan kurs. Dengan perwakilan lebihan-tiga, pembetulan yang diperlukan hanya sedikit berbeza: Kami tolak 3 dari digit yang tidak menghasilkan pembawa dan tambahkan tiga pada digit yang berlaku.

Medan bawa BCD dalam kata status pemproses dari Hawk mencatat pelaksanaan setiap digit perpuluhan setelah setiap arahan penambahan. Ideanya dipinjam dari Intel 8080. Satu-satunya penggunaan untuk bidang ini adalah untuk menyokong BCD dan kelebihan-3 aritmetik.

Sokongan untuk aritmetik BCD dalam kata status pemproses Hawk
31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 09 08 07 06 05 04 03 02 01 00
BCD bawa N Z V C


Medan bawa BCD digunakan oleh arahan ADJUST untuk melakukan penyesuaian yang sesuai setelah arahan ADD awal untuk menyelesaikan BCD atau jumlah lebihan-3, seperti yang digambarkan di sini:

Penambahan BCD dan Excess-3 di Hawk

Di sini, kelebihan kelebihan-3 harus jelas: Dengan BCD, kita mesti menyimpan pemalar 66666666 16 dalam daftar, dan kita mesti selalu menambahkan pemalar ini ke salah satu operasi kita sebelum setiap penambahan. Dengan kelebihan 3, kerana 6 tambahan dimasukkan ke dalam nilai sebelum penambahan, yang perlu kita lakukan hanyalah membuat pembetulan yang sedikit lebih kompleks setelah setiap jumlah.

Latihan

t) Tulis kod Hawk untuk mengambil pelengkap nombor BCD 10 dan kemudian terangkan cara mengesan jika hasilnya positif atau negatif.

u) Tuliskan kod Hawk untuk mengambil pelengkap nombor 10 yang melebihi 3 dan kemudian terangkan bagaimana untuk mengesan sama ada hasilnya positif atau negatif.

v) Tulis kod Hawk untuk menukar dari lebihan 3 ke BCD dan dari BCD menjadi lebihan 3.

w) Nilai apa yang ditambahkan atau dikurangkan dari setiap digit perpuluhan oleh ADJUST. Arahan EX3? Anda mungkin perlu menggunakan beberapa contoh untuk mengetahui perkara ini.

Aritmetik Titik Tetap Perduaan

Aritmetik terapung adalah ciri umum komputer moden, tetapi pada awal zaman komputer, tidak jelas bahawa ada keperluan untuk itu. John Von Neumann terkenal mengatakan "pengaturcara yang baik harus dapat menjaga intinya," ketika seseorang bertanya kepadanya tentang nilai perkakasan floating point. Bagaimana anda menyimpan titik di kepala anda? Jawapannya sangat mudah. Anda menggunakan aritmetik menggunakan bilangan bulat, tetapi bukannya menghitung, katakanlah, bilangan bulat inci, anda mengira bilangan bulat inci pecahan. Sekiranya anda bekerja di pangkalan 10, anda mungkin bekerja dalam seperseratus inci. Sekiranya anda bekerja dalam binari, anda mungkin menggunakan 128 inci inci.

Nombor binari 32-bit yang dinyatakan sebagai kiraan bilangan bulat dari 128 inci boleh difikirkan seperti berikut:

Nombor titik tetap dengan ketepatan 1/128
24 23 22 21 20 19 18 14 16 15 14 13 12 11 10 09 08 07 06 05 04 03 02 01 00 -1 -2 -3 -4 -5 -6 -7
Bahagian integer Pecahan


Bit pecahan titik tetap yang diberikan di atas telah dinomborkan semula, jadi daripada mempertimbangkan bit yang paling penting menjadi bit 31, ia adalah bit 24, dan bukannya mempertimbangkan bit yang paling tidak signifikan menjadi bit 0, ia adalah bit & ndash7. Ini kerana bit yang paling tidak signifikan mempunyai berat 2 & ndash7 dalam sistem nilai tempat, atau 1/128, dan bit yang paling ketara mempunyai nilai 2 24. Adalah berguna untuk menghitung bit sehingga tempat seseorang diberi nombor 0. Apabila kita menulis nombor di atas kertas, inilah yang dimaksudkan dengan intinya. Itulah sebabnya kami mengelakkan penggunaan istilah titik perpuluhan di sini, kerana titik tidak bergantung pada asas nombor & mdash di mana-mana asas nombor, namun, ia menandakan tempat seseorang, atau garis pemisah antara bahagian integer dari nombor dan bahagian pecahan.

Pertimbangkan nombor perduaan 0.1000000 ini adalah 1/2 atau 64/128. Begitu juga, 0.0100000 adalah 1/4 atau 32/128 dalam sistem nombor titik tetap yang digariskan di atas. Sekiranya kita ingin mewakili 0.1 10, kita tidak dapat melakukannya dengan tepat dalam sistem ini yang paling dekat dengan kita adalah 0.0001100, iaitu 12/128 atau 0.9375, di sisi rendah, dan 0.0001101, yang 13/128 atau 0.1015625, di sisi tinggi. Masalah asas yang kita hadapi adalah bahawa tidak ada perwakilan tepat sepersepuluh dalam binari, sama seperti tidak ada perwakilan tepat 1/3 dalam perpuluhan. Yang boleh kita harapkan adalah pendekatan yang baik.

Peraturan untuk menangani aritmetik titik tetap binari adalah peraturan yang biasa digunakan untuk menangani pecahan perpuluhan. Semasa menambah atau mengurangkan dua nombor titik tetap, mula-mula geserkannya untuk menyelaraskan titik, dan kemudian tambah atau tolak. Semasa mengalikan, darab pertama dan kemudian hitung digit kiri titik pada pengganda dan darab dan kemudian hitung jumlahnya untuk menentukan ke mana titik masuk dalam produk.

Pengaturcara C yang menggunakan penekanan semula nombor titik tetap di sini akan melakukan aritmetik seperti berikut:

Aritmetik titik tetap dalam C

Sayangnya, bahasa seperti C dan Java tidak memberi bantuan kepada pengaturcara ketika melakukan aritmetik titik tetap.Oleh itu, terserah kepada pengaturcara untuk mengingat untuk mengalihkan semua pemalar dengan tepat, atau mengkodkannya dengan bias bawaan yang betul, dan terserah kepada pengaturcara untuk mengingat untuk mengalihkan operan ke kiri atau ke kanan jika diperlukan. Ini adalah sesuatu yang difikirkan oleh John Von Neumann yang dapat dilakukan oleh pengaturcara, tetapi jelas pada awal tahun 1960-an bahawa pengaturcara mengalami kesukaran untuk melakukan ini. Perkakasan atau perisian terapung menghilangkan keperluan untuk ini.

Latihan

x) Memandangkan pembahagi dan dividen mempunyai mata di tempat yang sama, di mana titik bagi hasil? Di manakah titik yang tinggal? Sebagai contoh yang konkrit, pertimbangkan kemungkinan kedua-dua pembahagi dan dividen mempunyai 7 tempat selepas itu.

y) Berikan kod Hawk untuk membagi nombor titik tetap pelengkap 2 yang diberikan dalam daftar 3 menjadi bahagian integernya, dalam daftar 3, dan bahagian pecahannya, dalam daftar 4. Nombor awal harus mempunyai 7 tempat selepas titik. Bahagian pecahan hasilnya akan mempunyai satu bit untuk tanda dan 31 bit selepas titik.


2.8: Mendarab dan Membahagi Integer (Bahagian 2)

Ketahui cara membahagi bilangan bulat dalam bahasa Perhimpunan MIPS!

Indeks Kursus

  1. Pengenalan dan Marikh
  2. Daftar
  3. Hello Majlis!
  4. Mencetak Watak
  5. Mencetak Integer
  6. Mencetak Pelampung
  7. Mencetak Berganda
  8. Menambah Integer
  9. Menolak Integer
  10. Menggandakan bilangan bulat
  11. Menggandakan bilangan bulat
  12. Menggandakan Integer sll
  13. Membahagi Integer bahagian 1
  14. Membahagi Integer bahagian 2
  15. Pengenalan Fungsi
  16. Hujah Fungsi dan Nilai Pulangan
  17. Menyimpan Daftar ke Tumpukan
  18. Prosedur Bersarang
  19. Mendapatkan Input Input Pengguna
  20. Mendapatkan Input Pengguna
  21. Mendapatkan Input Pengguna berganda
  22. Mendapatkan Teks Dari Pengguna
  23. Sekiranya pernyataan Arahan bercabang
  24. Memeriksa Jika Nombor Kurang daripada Slt Lain
  25. Arahan Pseudo bercabang
  26. Semasa Gelung di MIPS
  27. Susunan
  28. Mencetak Array dengan Loop Sementara
  29. Penyusun Array
  30. Aritmetik Titik Terapung
  31. Lebih lanjut mengenai Aritmetik Floating Point
  32. Sekiranya Penyataan dengan Terapung dan Ganda
  33. Pengenalan kepada Rekursi
  34. Program Faktorial Rekursif
  35. Manipulasi Bit
  36. Rata-rata Program
  37. Susunan 2D
  38. Pelaksanaan Array 2D

Penerangan Kursus

Sama ada anda sedang bersiap untuk kursus bahasa Assembly atau anda hanya berminat untuk belajar Assembly, siri tutorial ini akan membimbing anda langkah demi langkah untuk menjadi pengaturcara Assembly MIPS yang mahir.


Nota Sains Komputer Plus One Bab 2 Perwakilan Data dan Algebra Boolean

Sistem Nombor:
Ini adalah kaedah sistematik untuk mewakili nombor dengan cara yang berbeza. Setiap sistem nombor mempunyai Pangkalannya sendiri, iaitu angka dan bilangan simbol atau digit yang digunakan.

  1. Digit Paling Penting (MSD): Digit dengan berat paling banyak disebut MSD. MSD juga dipanggil Left Most Digit (LMD)
  2. Digit Significant Least (LSD): Digit dengan berat paling sedikit disebut LSD. LSD juga dipanggil Right Most Digit (RMD)
    • cth: 106: Berikut MSD: 1 dan LSD: 6
    • 345.78: Berikut MSD: 3 dan LSD: 8
  3. Binary Digit juga disebut sedikit.
  4. Berat setiap digit nombor dapat ditunjukkan oleh kekuatan asasnya.

Nombor penukaran:
Secara amnya, untuk menukar nombor perpuluhan menjadi sistem nombor lain (binari atau oktal atau heksadesimal) lakukan perkara berikut. Bagilah nombor berturut-turut dengan asas sistem nombor yang anda mahu tukar dan tuliskan baki dari bawah ke atas.

Untuk menukar pecahan perpuluhan menjadi sistem nombor yang lain. Banyakkan nombor dengan asas sistem nombor yang anda mahu tukar kemudian bahagian integer dan bahagian pecahan dipisahkan lagi darabkan bahagian pecahan dengan asas dan lakukan langkah berulang kali hingga bahagian pecahan menjadi sifar. Akhirnya tuliskan bahagian integer dari atas ke bawah.

Perpuluhan hingga Perduaan:
Bagilah nombor dengan asas 2 berturut-turut dan tuliskan baki dari bawah ke atas.

Pecahan perpuluhan hingga binari:
darab nombor dengan asas 2 maka bahagian integer dan bahagian pecahan dipisahkan lagi darabkan bahagian pecahan dengan asas 2 dan lakukan langkah berulang kali sehingga bahagian pecahan menjadi sifar. Akhirnya tuliskan bahagian integer dari atas ke bawah.

Perpuluhan hingga Oktal:
Bagilah nombor dengan pangkalan 8 berturut-turut dan tuliskan baki dari bawah ke atas.

Pecahan perpuluhan hingga oktal:
darab nombor dengan asas 8 maka bahagian integer dan bahagian pecahan dipisahkan lagi darabkan bahagian pecahan dengan asas 8 dan lakukan langkah berulang kali sehingga bahagian pecahan menjadi sifar. Akhirnya tuliskan bahagian integer dari atas ke bawah.
cth: (55)10 = ()8

(0.140625)10 = (0.11)8

Perpuluhan hingga Perpuluhan:
Bagilah nombor dengan asas 16 berturut-turut dan tuliskan baki dari bawah ke atas.

Pecahan perpuluhan hingga heksadesimal:
darab nombor dengan asas 16 maka bahagian integer dan bahagian pecahan dipisahkan lagi darabkan bahagian pecahan dengan asas 16 dan lakukan langkah berulang kali sehingga bahagian pecahan menjadi sifar. Akhirnya tuliskan bahagian integer dari atas ke bawah.

Menukarkan nombor dari sistem nombor menjadi perpuluhan: Untuk ini darabkan setiap digit dengan berat yang sesuai dan jumlahkan.

Penukaran perduaan hingga perpuluhan:
Untuk ini kalikan setiap bit dengan berat yang sesuai dan jumlahkan. Berat adalah kekuatan 2.

Menukar pecahan binari ke perpuluhan

101.101 = 1 × 2 2 + 0 × 2 1 + 1 × 2 0 + 1 × 2 -1 + 0 × 2 -2 + 1 × 2 -3
= 4 + 0 + 1 + 1/2 + 0 + 1/8
= 5 + 0.5 + 0.125
(101.101)2 = (5.625)10

Penukaran Oktal hingga perpuluhan:
Untuk ini kalikan setiap bit dengan berat yang sesuai dan jumlahkan. Berat adalah kekuatan 8.
Cth: (1007)8 =()10?

1 × 8 3 + 0 × 8 2 + 0 × 8 1 + 7 × 8 0
= 512 + 0 + 0 + 7
=(519)10
Menukar pecahan oktal ke perpuluhan (600.005)8 =()10?

= 6 × 8 2 + 0 × 8 1 + 0 × 8 0 + 0 × 8 -1 + 0 × 8 -2 + 5 × 8 -3
= 384 + 0 + 0 + 0 + 0 + 0.009765625
= (384.009765625)10

Penukaran heksadesimal hingga perpuluhan:
Untuk ini kalikan setiap bit dengan berat yang sesuai dan jumlahkan. Berat adalah kekuatan 16.
Cth: (100)16 = ()10?

= 1 × 16 2 + 0 × 16 1 + 0 × 16 0
= 256 + 0 + 0
= (256)10
Menukar pecahan Heksadesimal menjadi perpuluhan (60A.4)8 =()10?

= 6 x 16 2 + 0 x 16 1 + 10 x 16 0 + 4 x 16 -1
= 1536 + 0 + 0 + .25
= (1536.25)10

Penukaran Oktal ke binari:
Tukarkan setiap digit oktal menjadi setara binari 3 bitnya. Pertimbangkan jadual berikut

Penukaran heksadesimal hingga binari:
Tukar setiap digit Heksadesimal menjadi setara binari 4 bitnya. Pertimbangkan jadual berikut

1010 1011 1100 (ABC)16=(101010111100)2

Penukaran binari ke oktal
Bahagikan nombor perduaan kepada kumpulan 3 bit bermula dari kanan ke kiri (Tetapi di bahagian pecahan mula membahagi dari kiri ke kanan). Masukkan sifar yang diperlukan di sebelah kiri (atau sebelah kanan sekiranya bahagian pecahan) jika diperlukan dan tuliskan setara oktal yang sesuai.
cth: (10100110)2= ()8?
Masukkan satu sifar di sebelah kiri untuk membentuk kumpulan 3 bit

(10100110)2= (246)8

Penukaran binari ke Heksadesimal:
Bahagikan nombor perduaan kepada kumpulan 4 bit bermula dari kanan ke kiri (Tetapi di bahagian pecahan mula membahagi dari kiri ke kanan). Masukkan sifar yang diperlukan di sebelah kiri (atau sebelah kanan sekiranya bahagian pecahan) jika diperlukan dan tuliskan setara Heksadesimal yang sesuai.
cth: (100100110)2 = ()16?
Masukkan 3 sifar di sebelah kiri untuk membentuk kumpulan 4 bit

(100100110)2 = (126)16

Penukaran Oktal ke Heksadesimal:
Pertama menukar nombor oktal menjadi binari (lihat 1.6.7), kemudian ubah binari ini menjadi heksadesimal (juga lihat 1.6.10)
cth: Tukar (67)8 = ( )16
Langkah I: Pertama menukar nombor ini menjadi setara binari untuk melakukan perkara berikut:

Langkah II: Seterusnya ubah nombor ini menjadi setara heksadesimal untuk ini lakukan perkara berikut.

Jadi jawapannya adalah (67)8 = ( 37)16

Penukaran heksadesimal hingga oktal:
Pertama menukar Heksadesimal ke binari (lihat 1.6.8), kemudian rahsia binari ini menjadi oktal (juga lihat 1.6.9)
cth: Tukar (A1)16 = ( )8?
Langkah I: Pertama menukar nombor ini menjadi setara binari. Untuk ini, lakukan perkara berikut

Langkah II. Seterusnya tukar nombor ini menjadi setara oktal. Untuk ini, lakukan perkara berikut.
Jadi jawapannya adalah (A1)16 = (241)8

Perwakilan data:
Data yang disimpan dalam memori komputer adalah dalam bentuk binari.

Perwakilan bilangan bulat
Terdapat tiga cara untuk mewakili bilangan bulat dalam komputer. Ia adalah seperti berikut:

  1. Tanda dan Perwakilan Magnitud (SMR)
  2. Perwakilan Pelengkap 1
  3. Perwakilan Pelengkap 2

1. SMR:
Biasanya nombor mempunyai tanda dan magnitud dua bahagian, misalnya: Pertimbangkan nombor + 5. Di sini + adalah tanda dan 5 adalah besarnya. Dalam SMR Bit yang paling ketara (MSB) digunakan untuk mewakili tanda. Sekiranya MSB adalah 0 tanda adalah + ve dan MSB adalah 1 tanda adalah -ve. cth: Sekiranya komputer mempunyai ukuran perkataan adalah 1 bait maka

Di sini MSB digunakan untuk tanda maka baki 7 bit digunakan untuk mewakili magnitud. Jadi kita boleh, mewakili 2 7 = 128 nombor. Tetapi ada nombor negatif dan positif. Jadi 128 + 128 = 256 nombor. Nombor adalah 0 hingga +127 dan 0 hingga -127. Di sini sifar diulang. Oleh itu, kita boleh mewakili 256 & # 8211 1 = 255 nombor.

2. Perwakilan Pelengkap 1:
Untuk mendapatkan pelengkap nombor perduaan 1, ganti setiap 0 dengan 1 dan setiap 1 dengan 0. Nombor negatif ditunjukkan dengan pelengkap 1 tetapi nombor + ve tidak mempunyai pelengkap 1,
cth:
(i) Untuk mencari pelengkap 1 -21
+21 = 00010101
Untuk mendapatkan pelengkap 1, ubah semua 0 hingga 1 dan. Semua 1 hingga 0.
-21 = 11101010
Pelengkap -1 1 adalah 11101010

(ii) Cari pelengkap 1 & # 8217 dari +21. Nombor positif ditunjukkan dengan menggunakan SMR.
+21 = 00010101 (Tidak perlu mengambil pelengkap 1 & # 8217s)

3. Perwakilan Pelengkap 2:
Untuk mendapatkan pelengkap nombor perduaan 2, tambah 1 pada pelengkap nombornya + nombor ve tidak mempunyai pelengkap nombor 2.
cth: Untuk mencari pelengkap 2 dari -21
+21 = 00010101
Mula-mula ambil pelengkap 1 untuk perubahan ini semua 1 hingga 0 dan semua 0 hingga 1

Pelengkap 2 -21 ialah 1110 1011

Perwakilan nombor titik terapung:
Nombor nyata terdiri daripada bahagian integer dan pecahan dan mewakili dengan menggunakan kaedah Exponent dan Mantissa. Kaedah ini juga digunakan untuk mewakili nombor yang terlalu besar dan juga bilangan yang terlalu kecil.
Cth: .0000000000000000000000001 dapat diwakili dengan mudah sebagai 1 × 10 -25. Di sini T adalah Mantissa dan -25 adalah eksponen.

Komputer dengan panjang 32 bit perkataan digunakan 24 bit untuk mantissa dan 8 bit selebihnya digunakan untuk menyimpan eksponen.

Perwakilan watak:
1. ASCII (Kod Piawai Amerika untuk Pertukaran Maklumat):
Ini adalah kod 7 bit yang digunakan untuk mewakili alfanumerik dan beberapa watak khas dalam memori komputer. Ia diperkenalkan oleh pemerintah A.S. Setiap watak di papan kekunci mempunyai nombor yang unik.

Cth: Kod ASCII ‘a’ adalah 97, apabila anda menekan ‘a’ di papan kekunci, isyarat bersamaan dengan 1100001 (Setara binari 97 adalah 1100001) dihantar ke memori komputer. 2 7 = 128, oleh itu kita hanya dapat mewakili 128 aksara dengan menggunakan ASCII. Tidak cukup untuk mewakili semua watak papan kekunci standard.

2. EBCDIC (Kod Pertukaran Perpuluhan Berkod Perduaan Diperpanjang):
Ini adalah kod 8 bit yang diperkenalkan oleh IBM (Mesin Perniagaan Antarabangsa). 2 8 = 256 aksara dapat ditunjukkan dengan menggunakan ini.

3. ISCII (Kod Piawai India untuk Pertukaran Maklumat):
Ia menggunakan 8 bit untuk mewakili data dan diperkenalkan oleh jawatankuasa standardisasi dan diadopsi oleh Bureau of Indian Standards (BIS).

4. Unicode:
Batasan untuk menyimpan lebih banyak watak diselesaikan dengan pengenalan Unicode. Ia menggunakan 16 bit sehingga 2 16 = 65536 aksara (iaitu semua watak bahasa bertulis di dunia) dapat disimpan dengan menggunakan ini.

Aritmetik binari:
Tambahan binari:
Peraturan untuk menambah dua bit

cth: Cari jumlah nombor perduaan 110011 dan 100001.

Pengurangan binari:
Peraturan untuk mengurangkan digit binari dari digit lain.

Kurangkan menggunakan pelengkap 1:
Langkah-langkahnya diberikan di bawah:

Langkah 1: Tambahkan 0s di sebelah kiri subtrahend, untuk membuat dua nombor dengan bilangan bit yang sama.
Langkah 2: Cari pelengkap subtrahend 1.
Langkah 3: Tambahkan pelengkap dengan minuend.
Langkah 4: Jika ada bawaan, abaikan bawaan, hasilnya positif kemudian tambahkan bawaan 1 ke hasilnya.
cth: Kurangkan 1101 dari 111100 menggunakan kaedah pelengkap 1.
Langkah 1: Masukkan dua Os di sebelah kiri 1101. Oleh itu subtrahend adalah 001101.
Langkah 2: Pelengkap 1 dari 001101 adalah 110010
Langkah 3: Tambahkan ini ke minuend.

Langkah 4: Abaikan bawaan hasilnya positif dan tambahkan tambah bawaan 1 hingga 101110

Oleh itu hasilnya adalah 101111.

Pengurangan menggunakan pelengkap 2:
Langkah-langkahnya diberikan di bawah:
Langkah 1: Tambahkan 0s di sebelah kiri subtrahend, untuk membuat dua nombor dengan bilangan bit yang sama.
Langkah 2: Cari pelengkap subtrahend 2.
Langkah 3: Tambahkan pelengkap dengan minuend.
Langkah 4: Sekiranya ada bawaan, abaikan bawaan, hasilnya positif.
cth: Kurangkan 1101 dari 111100 menggunakan kaedah pelengkap 2.
Langkah 1: Masukkan dua 0s di sebelah kiri 1101. Oleh itu subtrahend adalah 001101.
Langkah 2: Cari pelengkap 2 dari 001101.
Pelengkap 1 ialah 110010.
Pelengkap 2 ialah 110010 + 1 = 110011
Langkah 3: Tambahkan ini ke minuend.

Langkah 4: Abaikan hasilnya positif. Oleh itu hasilnya adalah 101111.

Pengenalan algebra Boolean:
Nama Boolean Algebra diberikan untuk menghormati ahli matematik Inggeris George Boole. Algebra Boolean memperkatakan dua keadaan benar atau salah sebaliknya Ya atau Tidak dan berangka sama ada 0 atau 1.

Kuantiti bernilai binari:
Keputusan logik yang memberikan nilai YA atau TIDAK adalah keputusan binari, Pernyataan yang memberikan nilai YA atau TIDAK (BENAR atau SALAH) adalah pernyataan logik atau fungsi kebenaran. Pemboleh ubah yang boleh memberikan nilai BENAR atau SALAH (1 atau 0) adalah pemboleh ubah logik

Pengendali Boolean dan gerbang logik:
Pengendali Logik adalah DAN, ATAU dan TIDAK. Gerbang logik adalah peranti fizikal (litar elektronik) yang dapat melakukan operasi logik pada satu atau lebih input logik dan menghasilkan satu output logik. Jadual mewakili set f semua nilai yang mungkin dan hasil yang sesuai dalam pernyataan disebut jadual kebenaran.
1. Operator OR dan pintu OR:
Pengendali OR memberikan 1 salah satu daripada operan adalah 1. Sekiranya kedua-dua operan 0, ia menghasilkan 0. Jadual kebenaran X OR Y adalah

Gerbang ATAU logik diberikan di bawah.

Jadual kebenaran dan pintu bagi ungkapan Boolean Y = A + B + C

2. Operator AND dan pintu AND:
Operator AND memberikan 1 jika dan hanya jika kedua-dua operan itu adalah 1. Jika salah satu daripada operan itu adalah 0, ia menghasilkan 0 Jadual kebenaran X AND Y adalah

Pintu logik AND diberikan di bawah.

Jadual kebenaran dan pintu bagi ungkapan Boolean Y = A. B. C

3. Operator NOT dan pintu NOT:
Ia menghasilkan sebaliknya. NOT pintu juga dipanggil penyongsang. Ini adalah pengendali yang tidak berubah yang bermaksud ia hanya mempunyai satu input dan satu output. Jadual kebenaran NOT X adalah

Postulat asas algebra Boolean:
Aljabar Boolean terdiri daripada beberapa undang-undang asas. Undang-undang ini disebut postulat.
Postulat 1: Prinsip 0 dan 1
Sekiranya A ≠ 0, maka A = 1 dan A 1, maka A = 0

Prinsip Dualitas:
Apabila menukar OR (+) menjadi AND (.), DAN (.) Ke OR (+), 0 hingga 1 dan 1 hingga 0 dalam ungkapan Boolean kita akan mendapat hubungan Boolean lain yang merupakan dwi dari yang pertama, ini adalah prinsip dualitas.

Teori asas algebra Boolean:
Terdapat beberapa peraturan standard dan diterima dalam setiap teori, peraturan ini dikenal sebagai aksioma teori.

Undang-undang identiti:
Sekiranya X adalah pemboleh ubah Boolean, undang-undang menyatakan bahawa

  1. 0 + X = X
  2. 1 + X = 1 (ini adalah undang-undang identiti aditif)
  3. 0. X = 0
  4. 1. X = X (ini adalah undang-undang identiti pendaraban)

Berikut adalah jadual kebenaran

Undang-undang tidak berkuasa:
Undang-undang ini menyatakan bahawa

Undang-undang pelanggaran:
Ini menyatakan bahawa
( overline < overline < mathrm>> = mathrm)
Pujian pujian bagi nombor adalah nombor itu sendiri.

Undang-undang percuma:
Undang-undang ini menyatakan bahawa

Jadual kebenaran diberikan di bawah

Undang-undang komutatif:
Undang-undang ini memungkinkan untuk mengubah kedudukan pemboleh ubah dalam OR dan AND

Jadual kebenaran diberikan di bawah

Undang-undang bersekutu:
Ia membolehkan pengelompokan pemboleh ubah secara berbeza

Jadual kebenaran diberikan di bawah

Undang-undang pengedaran:
Undang-undang ini membenarkan pengembangan pendaraban berbanding penambahan dan juga membenarkan operasi penambahan berbanding pendaraban.

Jadual kebenaran diberikan di bawah

Undang-undang penyerapan:
Ini adalah sejenis undang-undang distributif di mana dua pemboleh ubah digunakan dan hasilnya akan menjadi salah satunya

Jadual kebenaran diberikan di bawah

Teorema De Morgan:
Teorema pertama Demorgan menyatakan bahawa
( overline < mathrm+ mathrm> = overline < mathrm> cdot overline < mathrm>)
iaitu. pujian jumlah dua pemboleh ubah sama dengan produk pujian mereka.

Teorema kedua menyatakan bahawa
( overline < mathrm. < mathrm>> = overline < mathrm> + overline < mathrm>)
iaitu. Pujian bagi produk dari dua pemboleh ubah sama dengan jumlah pujian bagi pemboleh ubah tersebut.

Reka bentuk litar untuk ungkapan Boolean sederhana:
Dengan menggunakan gerbang asas seperti gerbang AND, OR dan NOT, kita dapat membuat litar logik.

Pintu universal:
Dengan menggunakan gerbang NAND dan NOR sahaja kita dapat membuat gerbang lain maka gerbang ini disebut gerbang Universal.

Pintu NAND:
Output pintu AND dibalikkan oleh pintu NOT adalah gerbang NAND

Pintu NOR:
Keluaran gerbang ATAU terbalik oleh gerbang TIDAK adalah gerbang NOR.


Prompt Visual # 3: Giliran Anda!

Jeda video dan biarkan penonton menggunakan pengetahuan mereka nombor positif dibahagi dengan nombor negatif menggunakan pembahagian partitif dalam arahan visual berikut:

10 ÷ (-5) = ___

atau

10 dibahagikan kepada -5 kumpulan memberikan hasil ___ setiap kumpulan

Luangkan masa untuk penonton terlibat dalam pembahagian partitif sebelum menunjukkan baki animasi video atau gambar pegun berikut.

Sekali lagi, kita mesti ambil perhatian bahawa kita ingin menentukan nilai kuantiti yang akan dikongsi di antara 5 kumpulan bercas negatif atau -5 kumpulan.

Dengan pembahagian 10 secara adil di antara kumpulan -5, kita melihat bahawa setiap kumpulan akan mengandungi 2 negatif atau -2.

Bagaimana dengan mendekati masalah yang sama menggunakan pembahagian petikan:

10 ÷ (-5) = ___

atau

10 dibahagikan kepada kumpulan -5 memberikan hasil kumpulan ___

Dengan menggunakan pemahaman konseptual kita yang dibina melalui petunjuk visual sebelumnya, kita sekarang dapat mengenali bahawa kerana ada 0 kumpulan -5 yang dapat kita buat dari +10 yang diberikan, kita mesti menggunakan kumpulan yang dikenakan daya negatif.

Oleh kerana saya dapat membuat 2 kumpulan +5, saya tahu saya juga dapat mewakili dua kumpulan yang sama dengan -2 kumpulan -5.

Di sana anda memilikinya! Memahami pembahagian integer secara konseptual melalui perwakilan konkrit dan visual. Di bilik darjah saya, saya meminta pelajar menggunakan jubin berwarna atau memautkan kiub untuk memanipulasi bahan secara fizikal untuk konsep sepenuhnya idea yang sangat penting ini yang sering didekati dengan menggunakan peraturan dan prosedur sahaja.

Adakah anda menggunakannya di bilik darjah atau di rumah? Bagaimana & # 8217dapatkan? Hantar di komen!


Tonton videonya: Mendarab dan membahagi nombor integer (Ogos 2022).