Perkalian integer cepat menggunakan tabel

Saya ingin memberi tahu pembaca tentang trik pemrograman yang saya temui dalam beberapa jenis buku terjemahan yang berisi pilihan trik seperti itu di waktu-waktu yang jauh ketika itu belum ditemukan bukan hanya byte, tetapi menakutkan untuk mengatakan stack, dan Dijkstra yang hebat belum mengutuk operator GOTO (sic, dalam huruf besar).

Saya sangat menyukai trik ini karena kesederhanaan dan keanggunannya sehingga sudah dalam milenium ini saya dengan senang hati memberi tahu siswa tentang hal itu dalam bentuk tugas berikut.

Bayangkan bahwa dalam proses kembali dari Bulan pada tahun 2030, Anda tiba-tiba menemukan bahwa komputer Anda tidak melakukan operasi penggandaan bilangan bulat dengan benar, dan ini pasti akan menyebabkan kecelakaan saat pendaratan.

Dalam cerita ini tidak ada yang luar biasa istimewa. Mari kita ingat, misalnya, masalah apa yang pernah terjadi dengan prosesor Pentium , dan pada saat Anda dikirim ke bulan, Anda belum mencapai substitusi impor penuh. Secara umum, perlu untuk memeriksa apakah prosesor dibor khusus.

Tapi to the point. Anda sangat perlu menerapkan perkalian secara terprogram agar dapat bekerja dengan cepat dalam waktu nyata dan sesuai dengan sumber daya yang tersedia.

Dari kursus aritmatika sekolah, kita ingat bahwa angka multivalued dapat dikalikan dengan kolom, dan hasil dari penggandaan angka individu dapat diambil dari tabel perkalian.

Tetapi hanya jika angkanya dipilih pendek (misalnya, 0 dan 1), tabel perkalian akan pendek dan kolom panjang, dan perhitungannya akan memakan banyak waktu.

Sebaliknya, jika kita mengambil angka panjang (misalnya, dari 0 hingga 65535), maka untuk aritmatika 16-bit
hasilnya diambil langsung dari tabel, dan kolom tidak ada. Namun, ukuran tabel Pythagoras klasik ternyata sekitar 17GB (4 * 65536 * 65536), jika kita memperhitungkan simetri sehubungan dengan diagonal, maka setengahnya sekitar 8.5GB.

Mungkin agak terlalu banyak.

Kencangkan dan ingat aljabar.

$$$(a + b) ^ 2 = a ^ 2 + b ^ 2 + 2ab$(1)

$$$(a - b) ^ 2 = a ^ 2 + b ^ 2 - 2ab$(2)

Kurangi (2) dari (1)

$$$(a + b) ^ 2 - (a - b) ^ 2 = 4ab$

dan selanjutnya

$$$a b = ((a + b) ^ 2 - (a - b) ^ 2) / 4$

Jadi, memiliki tabel kuadrat dalam array sqr, kita dapatkan

a * b = (sqr [a + b] - sqr [a - b]) / 4 (*)

Ukuran tabel 8 * (65535 + 65535) adalah sekitar 8,4MB, yang mungkin sudah dapat diterima.

Ukuran elemen tabel 8 byte disebabkan oleh fakta bahwa untuk maksimum a dan b, kuadrat dari jumlah mereka dari 4 byte tidak cocok - 2 bit tidak cukup.

Selanjutnya, saya akan menjelaskan beberapa perbaikan, yang tidak ada dalam buku ini. Saya datang sendiri ketika saya sudah menulis catatan ini.

Perhatikan bahwa dua bit paling tidak signifikan dari sebuah persegi genap selalu 00, dan kotak ganjil selalu 01. Di sisi lain, untuk setiap pasangan angka, jumlah dan selisihnya memiliki paritas yang sama.
Oleh karena itu, dalam rumus kami (*), proses pengurangan dalam tanda kurung tidak dapat memiliki tanda hubung,
terkait dengan dua bit paling tidak signifikan. Oleh karena itu, isi elemen dari tabel kuadrat
Anda dapat memajukan dua bit ke kanan dan dengan demikian menghemat setengah memori.

Akhirnya kita punya

a * b = sqr4 [a + b] - sqr4 [a - b] (**)

di mana sqr4 adalah tabel kuadrat yang dimodifikasi.

Dalam contoh kami, ukurannya sekitar 4,2 MB.

Di bawah ini untuk menggambarkan pendekatan ini, teks program Lua disertakan.

function create_multiplier(N) -- N     local sqr4 = {} --   for i = 1, 2 * N - 1 do local temp = 0 for j = 1, i - 1 do --    temp = temp + i - 1 --    end -- ..  "" sqr4[i] = math.floor(temp / 4) --  2  end return --   () function (i, j) if i < j then i, j = j, i end return sqr4[1 + i + j] - sqr4[1 + i - j] end end N = 256 mpy = create_multiplier(N) for i = 0, N - 1 do for j = 0, N - 1 do if i * j ~= mpy(i,j) then print("", i, j, i * j, mpy(i,j)) end end end print(" .") 

Untuk prosesor modern, tampaknya masuk akal untuk memiliki ukuran digit yang merupakan kelipatan dari ukuran byte agar mudah diakses. Dengan digit 1-byte, ukuran tabel hanya 1022 byte, yang memungkinkan trik ini digunakan dalam prosesor 8-bit yang tidak memiliki multiplikasi perangkat keras.

Saya akan berterima kasih kepada semua pembaca dari catatan ini untuk koreksi dan komentar.