Saya perlu menghitung ekspresi yang terlihat seperti:, di
A*B - C*D
mana tipenya: signed long long int A, B, C, D;
Setiap angka bisa sangat besar (tidak meluap tipenya). Walaupun A*B
bisa menyebabkan overflow, pada saat yang sama ekspresi A*B - C*D
bisa sangat kecil. Bagaimana saya bisa menghitungnya dengan benar?
Sebagai contoh:, di MAX * MAX - (MAX - 1) * (MAX + 1) == 1
mana MAX = LLONG_MAX - n
dan n - beberapa bilangan alami.
c++
c
integer-overflow
NGix
sumber
sumber
A - C
bisa meluap. Apakah ini masalah untuk dipertimbangkan atau Anda tahu bahwa ini tidak akan terjadi dengan data Anda?Jawaban:
Sepertinya ini terlalu sepele. Tetapi
A*B
apakah itu yang bisa meluap.Anda bisa melakukan yang berikut, tanpa kehilangan presisi
Dekomposisi ini dapat dilakukan lebih lanjut .
Seperti yang ditunjukkan @Gian, kehati-hatian mungkin perlu dilakukan selama operasi pengurangan jika jenisnya tidak ditandai lama.
Misalnya, dengan kasus yang Anda miliki dalam pertanyaan, hanya perlu satu iterasi,
sumber
C*D
A,B,C,D
yang negatif? BukankahE
atauF
akan lebih besar?Solusi paling sederhana dan paling umum adalah dengan menggunakan representasi yang tidak bisa meluap, baik dengan menggunakan perpustakaan integer panjang (misalnya http://gmplib.org/ ) atau mewakili menggunakan struct atau array dan menerapkan semacam perkalian panjang ( yaitu memisahkan setiap angka menjadi dua bagian 32bit dan melakukan perkalian seperti di bawah ini:
Dengan asumsi hasil akhirnya cocok dalam 64 bit Anda sebenarnya tidak benar-benar membutuhkan sebagian besar bit R3 dan tidak ada R4
sumber
Perhatikan bahwa ini bukan standar karena bergantung pada wrap-around signed-overflow. (GCC memiliki flag compiler yang memungkinkan ini.)
Tetapi jika Anda hanya melakukan semua perhitungan
long long
, hasil penerapan rumus secara langsung:(A * B - C * D)
akan akurat selama hasil yang benar sesuai dengan along long
.Berikut ini penyelesaian yang hanya bergantung pada perilaku yang ditentukan implementasi dari casting integer yang tidak ditandatangani ke integer yang ditandatangani. Tetapi ini dapat diharapkan bekerja pada hampir setiap sistem saat ini.
Ini melemparkan input ke
unsigned long long
tempat perilaku overflow dijamin akan dibungkus oleh standar. Mengembalikan ke integer yang ditandatangani di bagian akhir adalah bagian yang ditentukan implementasi, tetapi akan bekerja di hampir semua lingkungan saat ini.Jika Anda membutuhkan solusi yang lebih bertele-tele, saya pikir Anda harus menggunakan "aritmatika panjang"
sumber
long long
.Ini seharusnya bekerja (saya pikir):
Inilah derivasi saya:
sumber
Anda dapat mempertimbangkan menghitung faktor umum terbesar untuk semua nilai Anda, dan kemudian membaginya dengan faktor itu sebelum melakukan operasi aritmatika Anda, lalu mengalikannya lagi. Ini mengasumsikan bahwa faktor tersebut ada, namun (misalnya, jika
A
,B
,C
danD
kebetulan relatif prima, mereka tidak akan memiliki faktor umum).Demikian pula, Anda dapat mempertimbangkan mengerjakan skala log, tetapi ini akan sedikit menakutkan, tergantung pada ketepatan numerik.
sumber
long double
tersedia. Dalam hal ini, tingkat presisi yang dapat diterima dapat dicapai (dan hasilnya dapat dibulatkan).Jika hasilnya cocok dengan int panjang yang panjang maka ekspresi A * BC * D tidak apa-apa karena melakukan mod aritmatika 2 ^ 64, dan akan memberikan hasil yang benar. Masalahnya adalah untuk mengetahui apakah hasilnya cocok dengan int panjang. Untuk mendeteksi ini, Anda dapat menggunakan trik berikut ini menggunakan ganda:
Masalah dengan pendekatan ini adalah bahwa Anda dibatasi oleh ketelitian mantissa dari ganda (54bits?) Sehingga Anda perlu membatasi produk A * B dan C * D hingga 63 + 54 bit (atau mungkin sedikit kurang).
sumber
kemudian
sumber
Anda bisa menulis setiap angka dalam array, setiap elemen menjadi digit dan melakukan perhitungan sebagai polinomial . Ambil polinomial yang dihasilkan, yang merupakan array, dan hitung hasilnya dengan mengalikan masing-masing elemen array dengan 10 pangkat posisi dalam array (posisi pertama menjadi yang terbesar dan yang terakhir menjadi nol).
Jumlahnya
123
dapat dinyatakan sebagai:yang baru saja Anda buat array
[1 2 3]
.Anda melakukan ini untuk semua angka A, B, C dan D, dan kemudian Anda mengalikannya sebagai polinomial. Setelah Anda memiliki polinomial yang dihasilkan, Anda hanya merekonstruksi nomor dari itu.
sumber
Meskipun
signed long long int
tidak akan bertahanA*B
, dua dari mereka akan melakukannya. JadiA*B
bisa didekomposisi menjadi pohon istilah eksponen yang berbeda, ada yang pas satusigned long long int
.Sama untuk
C*D
.Mengikuti dengan cara yang lurus, subraksi dapat dilakukan untuk setiap pasangan
AB_i
danCD_i
juga, menggunakan carry bit tambahan (akurat integer 1-bit) untuk masing-masing. Jadi jika kita mengatakan E = A * BC * D Anda mendapatkan sesuatu seperti:Kami melanjutkan dengan mentransfer bagian atas
E_10
keE_20
(bergeser sebesar 32 dan menambah, lalu menghapus bagian atasE_10
).Sekarang Anda dapat menyingkirkan bit carry
E_11
dengan menambahkannya dengan tanda yang benar (diperoleh dari bagian non-carry) keE_20
. Jika ini memicu overflow, hasilnya tidak akan cocok.E_10
sekarang memiliki cukup 'ruang' untuk mengambil bagian atas dariE_00
(shift, tambah, hapus) dan carry bitE_01
.E_10
mungkin lebih besar sekarang lagi, jadi kami ulangi transfer keE_20
.Pada titik ini,
E_20
harus menjadi nol, jika tidak hasilnya tidak akan sesuai. Bagian atasE_10
kosong karena transfer juga.Langkah terakhir adalah mentransfer bagian bawah
E_20
ke dalamE_10
lagi.Jika harapan yang
E=A*B+C*D
sesuai dengansigned long long int
palka, kita sekarang milikisumber
Jika Anda tahu hasil akhir diwakili dalam tipe integer Anda, Anda dapat melakukan perhitungan ini dengan cepat menggunakan kode di bawah ini. Karena standar C menentukan bahwa aritmatika yang tidak ditandatangani adalah modulo aritmatika dan tidak meluap, Anda dapat menggunakan tipe yang tidak ditandatangani untuk melakukan perhitungan.
Kode berikut mengasumsikan ada tipe unsigned dengan lebar yang sama dan tipe yang ditandatangani menggunakan semua pola bit untuk mewakili nilai (tidak ada representasi trap, minimum dari tipe yang ditandatangani adalah negatif dari setengah modulus dari tipe unsigned). Jika ini tidak berlaku dalam implementasi C, penyesuaian sederhana dapat dilakukan untuk rutin ConvertToSigned untuk itu.
Berikut ini menggunakan
signed char
danunsigned char
untuk menunjukkan kode. Untuk implementasi Anda, ubah definisiSigned
menjaditypedef signed long long int Signed;
dan definisiUnsigned
menjaditypedef unsigned long long int Unsigned;
.sumber
Anda bisa mencoba memecah persamaan menjadi komponen yang lebih kecil yang tidak meluap.
Jika komponen masih meluap Anda dapat memecahnya menjadi komponen yang lebih kecil secara rekursif dan kemudian bergabung kembali.
sumber
K
danJ
, mengapa tidakN
danM
. Juga, saya pikir Anda memecah persamaan menjadi potongan-potongan yang lebih besar . Karena langkah 3 Anda sama dengan pertanyaan OP, kecuali lebih rumit(AK-CJ)
->(AB-CD)
Saya mungkin tidak membahas semua kasus tepi, saya juga belum menguji ini dengan keras tetapi ini menerapkan teknik yang saya ingat menggunakan di tahun 80-an ketika mencoba melakukan matematika integer 32-bit pada cpu 16-bit. Pada dasarnya Anda membagi 32 bit menjadi dua unit 16-bit dan bekerja dengannya secara terpisah.
Cetakan:
yang menurut saya itu berfungsi.
Saya yakin saya telah melewatkan beberapa seluk-beluk seperti menonton tanda overflow dll. Tapi saya pikir intinya ada
sumber
Demi kelengkapan, karena tidak ada yang menyebutkannya, beberapa kompiler (misalnya GCC) benar-benar memberi Anda integer 128 bit saat ini.
Dengan demikian solusi yang mudah adalah:
sumber
AB-CD = (AB-CD) * AC / AC = (B/C-D/A)*A*C
. BaikB/C
atauD/A
bisa meluap, sehingga menghitung(B/C-D/A)
pertama. Karena hasil akhir tidak akan meluap sesuai dengan definisi Anda, Anda dapat dengan aman melakukan penggandaan yang tersisa dan menghitung(B/C-D/A)*A*C
mana yang merupakan hasil yang diperlukan.Catatan, jika input Anda bisa sangat kecil juga,
B/C
atauD/A
bisa meluap. Jika memungkinkan, manipulasi yang lebih kompleks mungkin diperlukan sesuai dengan inspeksi input.sumber
Pilih
K = a big number
(mis.K = A - sqrt(A)
)Mengapa?
Perhatikan bahwa Karena A, B, C dan D adalah angka besar, maka
A-C
danB-D
angka kecil.sumber
A-C+B-D
adalah angka kecil. Karena A, B, C dan D adalah angka besar, maka AC adalah angka kecil.A - sqrt(A)
:)