Menangani angka yang sangat besar dalam bahasa yang tidak bisa?

15

Saya mencoba untuk berpikir tentang bagaimana saya akan melakukan perhitungan pada angka yang sangat besar (hingga tak terhingga - intergers no floats) jika konstruk bahasa tidak mampu menangani angka yang lebih besar dari nilai tertentu.

Saya yakin saya bukan yang pertama atau terakhir yang mengajukan pertanyaan ini, tetapi istilah pencarian yang saya gunakan tidak memberi saya algoritma untuk menangani situasi tersebut. Sebaliknya sebagian besar saran menawarkan perubahan bahasa atau perubahan variabel, atau berbicara tentang hal-hal yang tampaknya tidak relevan dengan pencarian saya. Jadi saya perlu sedikit bimbingan.

Saya akan membuat sketsa algoritma seperti ini:

  1. Tentukan panjang maks variabel integer untuk bahasa.

  2. Jika suatu angka lebih dari setengah panjang max dari variabel, pisahkan dalam array. (berikan sedikit ruang bermain)

  3. Urutan array [0] = angka paling ke kanan [n-maks] = angka paling kiri

    Ex. Bil: 29392023 Array [0]: 23, Array [1]: 20, array [2]: 39, array [3]: 29

Karena saya menetapkan setengah panjang variabel sebagai tanda titik maka saya dapat menghitung yang, sepersepuluh, seperseribu, dll. Tempatkan melalui tanda setengah sehingga jika variabel panjang maks adalah 10 digit dari 0 hingga 9999999999 maka saya tahu bahwa dengan membaginya menjadi lima digit, beri saya ruang bermain.

Jadi jika saya menambah atau mengalikan, saya dapat memiliki fungsi pemeriksa variabel yang melihat bahwa digit keenam (dari kanan) dari array [0] adalah tempat yang sama dengan digit pertama (dari kanan) dari array [1].

Membagi dan mengurangi memiliki masalah mereka sendiri yang belum saya pikirkan.

Saya ingin tahu tentang implementasi terbaik untuk mendukung jumlah yang lebih besar daripada yang bisa dilakukan oleh program.

Mallow
sumber
1
Hal pertama yang terlintas dalam pikiran adalah BigInteger Java: docs.oracle.com/javase/6/docs/api/java/math/BigInteger.html
Ivan
Apakah ini bahasa yang mungkin diketahui oleh siapa pun di sini dan dapat membuat rekomendasi khusus, atau apakah itu sesuatu yang tidak jelas dan eksklusif?
FrustratedWithFormsDesigner
Saya belum tahu bahasa apa yang saya inginkan saat ini. Saya paling tahu php tetapi saya tidak ingin melakukannya dalam bahasa itu. Lisp menarik karena dari apa yang saya baca tidak memiliki batasan panjang. Namun kekurangan pribadi saya ingin tahu cara kerjanya membuat saya ingin memiliki kebebasan untuk melakukannya dalam qbasic jika saya terjebak di sebuah pulau. (Ini untuk bersenang-senang juga, saya selalu berpikir tentang menghitung angka besar dan beberapa kalkulator online terlalu rumit untuk tugas itu.)
Mallow

Jawaban:

25

Anda mencari perpustakaan aritmatika presisi arbitrer (juga disebut "presisi ganda" atau "angka besar") untuk bahasa yang Anda gunakan. Misalnya, jika Anda bekerja dengan C Anda dapat menggunakan Perpustakaan GNU Bignum -> http://gmplib.org/

Jika Anda ingin memahami cara kerjanya, Anda juga dapat menulis perpustakaan num besar Anda sendiri dan menggunakannya. Cara paling sederhana untuk menangani ini adalah dengan array, di mana setiap elemen adalah digit dari angka yang Anda kerjakan. Setelah itu Anda perlu mengimplementasikan semua fungsi untuk menambah, mengurangi, mengalikan, membagi, eksponensial dan sebagainya.

Daniel Scocco
sumber
5
tentu saja "digit" adalah relatif, banyak perpustakaan bignum menggunakan digit pada basis 256 (byte tidak bertanda []) ke 2 ^ 64 (unsigned long [])
ratchet freak
1
Hanya memastikan saya mengerti, 'digit' bisa menjadi array basis 256 digit? Saya pikir saya mungkin salah, melakukan matematika di pangkalan 256 lebih mudah daripada pangkalan 88 tapi masih cukup tugas ... (Setidaknya ketika saya melakukannya tadi malam di selembar kertas haha)
Mallow
1
"Melakukan matematika di pangkalan 256 lebih mudah daripada pangkalan 88". Salah. Mereka sama mudahnya.
S.Lott
2
@ S.Lott: um ... ketika Anda memiliki operasi bitwise yang tersedia, melakukan matematika di pangkalan 256 jelas lebih mudah daripada pangkalan 88.
Jason S
1
Membangun add / kurangi / gandakan sendiri cukup mudah. Divisi sulit, kecuali, jika Anda menerapkannya dalam biner, di mana ia menjadi latihan dalam pengurangan bersyarat dan pergeseran bit.
Jason S
13

Ini adalah masalah yang terkenal: Aritmatika presisi sewenang-wenang

Ketika bahasa yang Anda gunakan tidak menyelesaikan masalah ini, pertama-tama coba temukan perpustakaan pihak ketiga yang melakukannya. Jika Anda tidak menemukannya atau Anda penasaran, cobalah untuk mengimplementasikannya; artikel wikipedia memiliki referensi yang bagus untuk implementasi klasik.

jgomo3
sumber
6

Ketika berhadapan dengan angka besar, mungkin salah satu keputusan desain yang paling mendasar adalah bagaimana saya akan mewakili angka besar?

Apakah itu string, array, daftar, atau kelas penyimpanan khusus (homegrown).

Setelah keputusan itu dibuat, operasi matematika yang sebenarnya dapat dipecah menjadi bagian-bagian yang lebih kecil dan kemudian dieksekusi dengan jenis bahasa asli seperti int atau integer.

Saya telah menyertakan contoh ADDITION yang sangat mendasar dalam C # .Net yang menyimpan jumlah besar yang dihasilkan sebagai string. "Angka" yang masuk juga merupakan string, jadi orang harus dapat mengirim angka yang sangat "besar". Ingatlah bahwa contohnya hanya untuk bilangan bulat agar tetap sederhana.

Bahkan dengan string ada batasan dalam jumlah karakter atau "angka" dalam angka, seperti yang ditunjukkan di sini:

Berapa panjang maksimum yang mungkin dari string .NET?

Tetapi Anda dapat menambahkan beberapa angka yang sangat besar, jauh melampaui tipe asli int32 atau int64 untuk .Net.

Bagaimanapun, ini adalah implementasi penyimpanan string.

/// <summary>
/// Adds two "integers".  The integers can be of any size string.
/// </summary>
/// <param name="BigInt1">The first integer</param>
/// <param name="BigInt2">The second integer</param>
/// <returns>A string that is the addition of the two integers passed.</returns>
/// <exception cref="Exception">Can throw an exception when parsing the individual parts     of the number.  Callers should handle. </exception>
public string AddBigInts(string BigInt1, string BigInt2)
{
    string result = string.Empty;

    //Make the strings the same length, pre-pad the shorter one with zeros
    int length = (BigInt1.Length > BigInt2.Length ? BigInt1.Length : BigInt2.Length);
    BigInt1 = BigInt1.PadLeft(length, '0');
    BigInt2 = BigInt2.PadLeft(length, '0');

    int remainder = 0;

    //Now add them up going from right to left
    for (int i = (BigInt1.Length - 1); i >= 0; i--)
    {
        //If we don't encounter a number, this will throw an exception as indicated.
        int int1 = int.Parse(BigInt1[i].ToString());
        int int2 = int.Parse(BigInt2[i].ToString());

        //Add
        int add = int1 + int2 + remainder;

        //Check to see if we need a remainder;
        if (add >= 10)
        {
            remainder = 1;
            add = add % 10;
        }
        else
        {
            remainder = 0;
        }

        //Add this to our "number"
        result = add.ToString() + result;
    }

    //Handle when we have a remainder left over at the end
    if (remainder == 1)
    {
        result = remainder + result;
    }

    return result;
}

Saya harap itu memberi Anda beberapa ide tentang implementasi Anda sendiri. Harap dicatat, bahwa kode sampel mungkin tidak dioptimalkan atau semacamnya. Ini dimaksudkan untuk memberikan beberapa ide tentang bagaimana hal itu bisa dilakukan.

Jon Raynor
sumber
Keren!! Terima kasih itu membantu menjernihkan hal-hal dengan sisa saya akan lebih rumit sedikit pun.
Mallow
-2

Yang ini bekerja lebih cepat untuk saya:

static string Add(string a, string b)
        {
            string c = null;

            if (Compare(a, b) < 0)
            {
                c = a;
                a = b;
                b = c;
            }

            StringBuilder sb = new StringBuilder();

            b = b.PadLeft(a.Length, '0');

            int r = 0;

            for (int i = a.Length - 1; i >= 0; i--)
            {
                int part = a[i] + b[i] + r - 96;

                if (part <= 9)
                {
                    sb.Insert(0, part);

                    r = 0;
                }
                else
                {
                    sb.Insert(0, part - 10);

                    r = 1;
                }
            }

            if (r == 1)
            {
                sb.Insert(0, "1");
            }

            return sb.ToString();
        }
Andranik Sargsyan
sumber
2
Situs ini adalah tentang pertanyaan konseptual dan jawaban diharapkan menjelaskan hal-hal. Melempar kesedihan alih-alih penjelasannya seperti menyalin kode dari IDE ke papan tulis: mungkin terlihat biasa dan bahkan terkadang dapat dimengerti, tetapi rasanya aneh ... hanya aneh. Papan tulis tidak memiliki kompiler
nyamuk
Situs ini adalah TUKAR, jadi kami mencoba saling membantu sebanyak mungkin. Mungkin saya harus melakukan komentar seperti itu di StackOverflow, tetapi saya mencoba membantu dengan pendekatan saya. Jika seseorang masih membutuhkan penjelasan, dia akan memintanya. Saya lakukan di sini digit tambahan matematis standar dengan digit, mulai dari akhir.
Andranik Sargsyan
Setuju dengan agas. Setidaknya jelaskan algoritme sebelum membuang kode.
Frank Hileman
Hanya membuang kode tanpa penjelasan seperti mendorong copy-past-and-go. Saya tidak melihat bagaimana itu bisa berguna dalam Rekayasa Perangkat Lunak. Mungkin di StackOverflow adalah, tetapi kedua situs sebenarnya memiliki tujuan yang sama sekali berbeda.
Laiv