Penjelasan aritmatika dengan ketepatan sewenang-wenang

Saya mencoba mempelajari C dan menemukan ketidakmampuan untuk bekerja dengan angka yang BENAR-BENAR besar (mis., 100 digit, 1000 digit, dll.). Saya sadar bahwa ada perpustakaan untuk melakukan ini, tetapi saya ingin mencoba menerapkannya sendiri.

Saya hanya ingin tahu apakah ada yang memiliki atau dapat memberikan penjelasan yang sangat mendetail dan bodoh tentang aritmatika presisi-arbitrer.

Ini semua masalah penyimpanan yang memadai dan algoritme untuk memperlakukan angka sebagai bagian yang lebih kecil. Anggaplah Anda memiliki kompiler di mana an inthanya bisa 0 hingga 99 dan Anda ingin menangani angka hingga 999999 (kami hanya akan mengkhawatirkan bilangan positif di sini agar tetap sederhana).

Anda melakukannya dengan memberikan setiap angka tiga intdan menggunakan aturan yang sama yang (seharusnya) Anda pelajari di sekolah dasar untuk penjumlahan, pengurangan, dan operasi dasar lainnya.

Dalam pustaka presisi arbitrer, tidak ada batasan tetap pada jumlah tipe dasar yang digunakan untuk merepresentasikan angka kita, apa pun yang dapat ditampung oleh memori.

Penambahan misalnya 123456 + 78:

12 34 56
      78
-- -- --
12 35 34

Bekerja dari ujung yang paling tidak signifikan:

• bawaan awal = 0.
• 56 + 78 + 0 carry = 134 = 34 dengan 1 carry
• 34 + 00 + 1 carry = 35 = 35 dengan 0 carry
• 12 + 00 + 0 carry = 12 = 12 dengan 0 carry

Faktanya, ini adalah bagaimana penambahan biasanya bekerja pada level bit di dalam CPU Anda.

Pengurangan serupa (menggunakan pengurangan jenis dasar dan meminjam alih-alih membawa), perkalian dapat dilakukan dengan penjumlahan berulang (sangat lambat) atau perkalian silang (lebih cepat) dan pembagian lebih rumit tetapi dapat dilakukan dengan menggeser dan mengurangi angka-angka terlibat (divisi panjang yang akan Anda pelajari sebagai seorang anak).

Saya sebenarnya telah menulis perpustakaan untuk melakukan hal-hal semacam ini menggunakan kekuatan maksimum sepuluh yang dapat dimasukkan ke dalam bilangan bulat ketika dikuadratkan (untuk mencegah luapan saat mengalikan dua intbersama, seperti 16-bit intyang dibatasi ke 0 hingga 99 hingga menghasilkan 9.801 (<32.768) saat dikuadratkan, atau 32-bit intmenggunakan 0 hingga 9.999 untuk menghasilkan 99.980.001 (<2.147.483.648)) yang sangat memudahkan algoritme.

Beberapa trik yang harus diperhatikan.

1 / Saat menjumlahkan atau mengalikan angka, alokasikan terlebih dahulu ruang maksimum yang dibutuhkan kemudian kurangi nanti jika Anda merasa jumlahnya terlalu banyak. Misalnya, menambahkan dua angka 100- "digit" (dimana digit adalah int) tidak akan pernah memberi Anda lebih dari 101 digit. Mengalikan angka 12 digit dengan angka 3 digit tidak akan menghasilkan lebih dari 15 digit (tambahkan jumlah digit).

2 / Untuk kecepatan tambahan, normalkan (kurangi penyimpanan yang diperlukan untuk) nomor hanya jika benar-benar diperlukan - perpustakaan saya memiliki ini sebagai panggilan terpisah sehingga pengguna dapat memutuskan antara kecepatan dan masalah penyimpanan.

3 / Penjumlahan bilangan positif dan negatif adalah pengurangan, dan mengurangi bilangan negatif sama dengan menjumlahkan positif yang setara. Anda dapat menyimpan cukup banyak kode dengan meminta metode tambah dan kurang memanggil satu sama lain setelah menyesuaikan tanda.

4 / Hindari mengurangi angka besar dari angka kecil karena Anda selalu mendapatkan angka seperti:

         10
         11-
-- -- -- --
99 99 99 99 (and you still have a borrow).

Sebagai gantinya, kurangi 10 dari 11, lalu negasikan:

11
10-
--
 1 (then negate to get -1).

Berikut adalah komentar (diubah menjadi teks) dari salah satu perpustakaan tempat saya harus melakukan ini. Sayangnya, kode itu sendiri memiliki hak cipta, tetapi Anda mungkin dapat memilih informasi yang cukup untuk menangani empat operasi dasar. Asumsikan berikut ini -adan -bmewakili angka negatif dan adan badalah angka nol atau positif.

Untuk penjumlahan , jika tanda berbeda, gunakan pengurangan negasi:

-a +  b becomes b - a
 a + -b becomes a - b

Untuk pengurangan , jika tanda berbeda, gunakan penjumlahan dari negasi:

 a - -b becomes   a + b
-a -  b becomes -(a + b)

Juga penanganan khusus untuk memastikan kita mengurangi angka kecil dari besar:

small - big becomes -(big - small)

Perkalian menggunakan matematika tingkat awal sebagai berikut:

475(a) x 32(b) = 475 x (30 + 2)
               = 475 x 30 + 475 x 2
               = 4750 x 3 + 475 x 2
               = 4750 + 4750 + 4750 + 475 + 475

Cara di mana ini dicapai melibatkan mengekstraksi masing-masing digit dari 32 satu per satu (mundur) kemudian menggunakan add untuk menghitung nilai yang akan ditambahkan ke hasil (awalnya nol).

ShiftLeftdan ShiftRightoperasi digunakan untuk mengalikan atau membagi dengan cepat LongIntdengan nilai bungkus (10 untuk matematika "nyata"). Pada contoh di atas, kita tambahkan 475 ke nol 2 kali (digit terakhir 32) untuk mendapatkan 950 (hasil = 0 + 950 = 950).

Kemudian kita geser ke kiri 475 untuk mendapatkan 4750 dan geser kanan 32 untuk mendapatkan 3. Tambahkan 4750 ke nol sebanyak 3 kali untuk mendapatkan 14250 kemudian tambahkan hasil 950 untuk mendapatkan 15200.

Pergeseran kiri 4750 untuk mendapatkan 47500, geser kanan 3 untuk mendapatkan 0. Karena pergeseran kanan 32 sekarang menjadi nol, kita selesai dan, sebenarnya 475 x 32 sama dengan 15200.

Pembagian juga rumit tetapi berdasarkan aritmatika awal (metode "gazinta" untuk "masuk ke"). Pertimbangkan pembagian panjang berikut untuk 12345 / 27:

       457
   +-------
27 | 12345    27 is larger than 1 or 12 so we first use 123.
     108      27 goes into 123 4 times, 4 x 27 = 108, 123 - 108 = 15.
     ---
      154     Bring down 4.
      135     27 goes into 154 5 times, 5 x 27 = 135, 154 - 135 = 19.
      ---
       195    Bring down 5.
       189    27 goes into 195 7 times, 7 x 27 = 189, 195 - 189 = 6.
       ---
         6    Nothing more to bring down, so stop.

Oleh karena 12345 / 27itu 457dengan sisa 6. Memeriksa:

  457 x 27 + 6
= 12339    + 6
= 12345

Ini diimplementasikan dengan menggunakan variabel draw-down (awalnya nol) untuk menurunkan segmen 12345 satu per satu hingga lebih besar atau sama dengan 27.

Kemudian kita cukup mengurangi 27 dari itu sampai kita mendapatkan di bawah 27 - jumlah pengurangan adalah ruas yang ditambahkan ke garis atas.

Ketika tidak ada lagi segmen untuk diturunkan, kami mendapatkan hasil kami.

Ingatlah bahwa ini adalah algoritme yang cukup mendasar. Ada cara yang jauh lebih baik untuk melakukan aritmatika kompleks jika bilangan Anda sangat besar. Anda dapat melihat sesuatu seperti GNU Multiple Precision Arithmetic Library - secara substansial lebih baik dan lebih cepat daripada perpustakaan saya sendiri.

Itu memang memiliki kesalahan yang agak disayangkan karena itu akan keluar begitu saja jika kehabisan memori (kesalahan yang agak fatal untuk perpustakaan tujuan umum menurut saya) tetapi, jika Anda bisa melihat melewati itu, itu cukup bagus dalam apa yang dilakukannya.

Jika Anda tidak dapat menggunakannya untuk alasan lisensi (atau karena Anda tidak ingin aplikasi Anda keluar begitu saja tanpa alasan yang jelas), Anda setidaknya bisa mendapatkan algoritme dari sana untuk diintegrasikan ke dalam kode Anda sendiri.

Saya juga menemukan bahwa badan-badan di MPIR (garpu GMP) lebih setuju untuk diskusi tentang perubahan potensial - mereka tampak seperti kelompok yang lebih ramah pengembang.

Meskipun menemukan kembali roda sangat baik untuk pengembangan dan pembelajaran pribadi Anda, ini juga merupakan tugas yang sangat besar. Saya tidak ingin menghalangi Anda karena ini adalah latihan yang penting dan yang telah saya lakukan sendiri, tetapi Anda harus menyadari bahwa ada masalah halus dan kompleks di tempat kerja yang ditangani oleh paket yang lebih besar.

Misalnya perkalian. Secara naif, Anda mungkin berpikir tentang metode 'anak sekolah', yaitu tulis satu angka di atas angka lainnya, kemudian lakukan perkalian panjang seperti yang Anda pelajari di sekolah. contoh:

      123
    x  34
    -----
      492
+    3690
---------
     4182

tetapi metode ini sangat lambat (O (n ^ 2), n adalah jumlah digit). Sebagai gantinya, paket bignum modern menggunakan transformasi Fourier diskrit atau transformasi Numerik untuk mengubahnya menjadi operasi O (n ln (n)).

Dan ini hanya untuk bilangan bulat. Ketika Anda masuk ke fungsi yang lebih rumit pada beberapa jenis representasi nyata dari angka (log, sqrt, exp, dll.), Semuanya menjadi lebih rumit.

Jika Anda menyukai latar belakang teoretis, saya sangat merekomendasikan membaca bab pertama dari buku Yap, "Masalah Mendasar Aljabar Algoritmik" . Seperti yang telah disebutkan, pustaka gmp bignum adalah pustaka yang sangat baik. Untuk bilangan real, saya telah menggunakan mpfr dan menyukainya.

Jangan menemukan kembali roda: mungkin akan berubah menjadi persegi!

Gunakan pustaka pihak ketiga, seperti GNU MP , yang telah dicoba dan diuji.

Anda melakukannya dengan cara yang pada dasarnya sama seperti yang Anda lakukan dengan pensil dan kertas ...

• Angka tersebut akan direpresentasikan dalam buffer (array) yang dapat mengambil ukuran sewenang-wenang (yang berarti menggunakan mallocdan realloc) sesuai kebutuhan
• Anda menerapkan aritmatika dasar sebanyak mungkin menggunakan struktur yang didukung bahasa, dan menangani carry dan memindahkan titik radix secara manual
• Anda menjelajahi teks analisis numerik untuk menemukan argumen yang efisien untuk menangani fungsi yang lebih kompleks
• Anda hanya menerapkan sebanyak yang Anda butuhkan.

Biasanya Anda akan menggunakan sebagai unit dasar komputasi

• byte berisi 0-99 atau 0-255
• Kata 16 bit mengandung layu 0-9999 atau 0--65536
• 32 bit kata yang mengandung ...
• ...

seperti yang ditentukan oleh arsitektur Anda.

Pilihan basis biner atau desimal bergantung pada keinginan Anda untuk efisiensi ruang maksimum, keterbacaan manusia, dan tidak adanya dukungan matematika Binary Coded Decimal (BCD) pada chip Anda.

Anda bisa melakukannya dengan matematika tingkat SMA. Padahal algoritma yang lebih canggih digunakan dalam kenyataan. Jadi misalnya untuk menambahkan dua angka 1024-byte:

unsigned char first[1024], second[1024], result[1025];
unsigned char carry = 0;
unsigned int  sum   = 0;

for(size_t i = 0; i < 1024; i++)
{
    sum = first[i] + second[i] + carry;
    carry = sum - 255;
}

Hasil harus lebih besar one placejika penambahan untuk menjaga nilai maksimum. Lihat ini :

9
   +
9
----
18

TTMath adalah perpustakaan yang bagus jika Anda ingin belajar. Itu dibangun menggunakan C ++. Contoh di atas memang konyol, tetapi begitulah cara penjumlahan dan pengurangan dilakukan secara umum!

Referensi yang baik tentang subjek adalah Kompleksitas komputasi operasi matematika . Ini memberi tahu Anda berapa banyak ruang yang diperlukan untuk setiap operasi yang ingin Anda terapkan. Misalnya, jika Anda memiliki dua N-digitbilangan, maka Anda perlu 2N digitsmenyimpan hasil perkaliannya.

Seperti yang dikatakan Mitch , ini bukanlah tugas yang mudah untuk diterapkan! Saya sarankan Anda melihat TTMath jika Anda tahu C ++.

Salah satu referensi utama (IMHO) adalah TAOCP Volume II Knuth. Ini menjelaskan banyak algoritma untuk merepresentasikan angka dan operasi aritmatika pada representasi ini.

@Book{Knuth:taocp:2,
   author    = {Knuth, Donald E.},
   title     = {The Art of Computer Programming},
   volume    = {2: Seminumerical Algorithms, second edition},
   year      = {1981},
   publisher = {\Range{Addison}{Wesley}},
   isbn      = {0-201-03822-6},
}

Dengan asumsi bahwa Anda ingin menulis kode integer yang besar sendiri, ini dapat sangat mudah dilakukan, diucapkan sebagai seseorang yang baru-baru ini (meskipun di MATLAB.) Berikut adalah beberapa trik yang saya gunakan:

• Saya menyimpan setiap digit desimal sebagai angka ganda. Ini membuat banyak operasi menjadi sederhana, terutama keluaran. Meskipun memerlukan lebih banyak penyimpanan daripada yang Anda harapkan, memori di sini murah, dan perkalian sangat efisien jika Anda dapat menggabungkan sepasang vektor secara efisien. Alternatifnya, Anda dapat menyimpan beberapa digit desimal secara ganda, tetapi berhati-hatilah karena konvolusi untuk melakukan perkalian dapat menyebabkan masalah numerik pada bilangan yang sangat besar.

• Simpan sedikit tanda secara terpisah.

• Penambahan dua angka pada dasarnya adalah soal menjumlahkan digit, lalu periksa carry di setiap langkah.

• Perkalian sepasang angka paling baik dilakukan sebagai konvolusi diikuti dengan langkah bawa, setidaknya jika Anda memiliki kode konvolusi cepat di ketuk.

• Bahkan ketika Anda menyimpan angka sebagai string digit desimal individu, pembagian (juga mod / rem ops) dapat dilakukan untuk mendapatkan sekitar 13 digit desimal sekaligus dalam hasil. Ini jauh lebih efisien daripada pembagian yang hanya bekerja pada 1 digit desimal pada satu waktu.

• Untuk menghitung pangkat integer dari sebuah integer, hitung representasi biner dari eksponen. Kemudian gunakan operasi kuadrat berulang untuk menghitung daya sesuai kebutuhan.

• Banyak operasi (pemfaktoran, uji primalitas, dll.) Akan mendapatkan keuntungan dari operasi powermod. Artinya, saat Anda menghitung mod (a ^ p, N), kurangi hasil mod N pada setiap langkah eksponen di mana p telah diekspresikan dalam bentuk biner. Jangan menghitung a ^ p terlebih dahulu, lalu mencoba menguranginya mod N.

Berikut adalah contoh sederhana (naif) yang saya lakukan di PHP.

Saya mengimplementasikan "Add" dan "Multiply" dan menggunakannya sebagai contoh eksponen.

http://adevsoft.com/simple-php-arbitrary-precision-integer-big-num-example/

Kode snip

// Add two big integers
function ba($a, $b)
{
    if( $a === "0" ) return $b;
    else if( $b === "0") return $a;

    $aa = str_split(strrev(strlen($a)>1?ltrim($a,"0"):$a), 9);
    $bb = str_split(strrev(strlen($b)>1?ltrim($b,"0"):$b), 9);
    $rr = Array();

    $maxC = max(Array(count($aa), count($bb)));
    $aa = array_pad(array_map("strrev", $aa),$maxC+1,"0");
    $bb = array_pad(array_map("strrev", $bb),$maxC+1,"0");

    for( $i=0; $i<=$maxC; $i++ )
    {
        $t = str_pad((string) ($aa[$i] + $bb[$i]), 9, "0", STR_PAD_LEFT);

        if( strlen($t) > 9 )
        {
            $aa[$i+1] = ba($aa[$i+1], substr($t,0,1));
            $t = substr($t, 1);
        }

        array_unshift($rr, $t);
     }

     return implode($rr);
}