Memahami dan Melaksanakan Algoritma Pendaraban Karatsuba untuk Nombor Besar-tutorial js-php.cn

Understanding and Implementing the Karatsuba Multiplication Algorithm for Large Numbers

Dalam matematik pengiraan, pendaraban nombor besar dengan cekap adalah asas kepada pelbagai aplikasi, daripada kriptografi kepada pengkomputeran saintifik. Algoritma pendaraban Karatsuba ialah kaedah bahagi-dan-takluk yang meningkatkan prestasi dengan ketara berbanding pendaraban panjang tradisional untuk nombor besar. Dalam artikel ini, kami akan meneroka pelaksanaan JavaScript bagi algoritma berkuasa ini yang direka untuk mengendalikan nombor besar secara sewenang-wenangnya yang diwakili sebagai rentetan.

Masalah Pendaraban Tradisional

Kaedah pendaraban "buku sekolah" standard mempunyai kerumitan masa

(O (n^{2})) (O(n^2))

(O(n2)) , di mana

(n) (n)

(n) ialah bilangan digit dalam nombor yang didarab. Pertumbuhan kuadratik ini menjadi mahal secara pengiraan apabila bilangannya semakin besar. Algoritma Karatsuba, yang diperkenalkan oleh Anatolii Karatsuba pada tahun 1960, mengurangkan kerumitan ini kepada lebih kurang

(O (n^{1.585})) (O(n^{1.585}))

(O(n1.585)) , menjadikannya pilihan yang lebih pantas untuk input yang besar.

Cara Algoritma Karatsuba Berfungsi

Algoritma bergantung pada strategi bahagi-dan-takluk:

Bahagi: Bahagikan setiap nombor kepada dua bahagian—bahagian tinggi dan bahagian rendah.
Menakluk: Kira tiga produk utama secara rekursif: Ini melibatkan pengiraan komponen berikut untuk setiap langkah rekursif:
- $z_{0} = rendah1 \times rendah2 z_0 = teks{rendah1} kali teks{rendah2}$ z0 =rendah1×rendah2
- $z_{1} = (rendah1 tinggi1) \times (rendah2 tinggi2) z_1 = (teks{rendah1} teks{tinggi1}) kali (teks{rendah2} teks{tinggi2})$ z1=(rendah1 tinggi1)×(rendah2 tinggi2)
- $z_{2} = tinggi1 × tinggi2 z_2 = teks{tinggi1} kali teks{tinggi2}$ z2=tinggi1×tinggi2
Gabungkan: Gunakan formula:
$hasil = z_{2} ⋅ 1 0^{2 ⋅ m} (z_{1} − z_{2} − z_{0}) ⋅ 1 0^{m} z_{0} teks{hasil} = z_2 cdot 10^{2 cdot m}(z_1 - z_2 - z_0) cdot 10^m z_0$ hasil= z2⋅102⋅m (z1 −z2 −z0 )⋅10m z0
di mana $(m) (m)$ (m) ialah separuh daripada bilangan digit dalam nombor asal.

Pendekatan ini mengurangkan bilangan pendaraban rekursif daripada empat kepada tiga, meningkatkan kecekapan.

Pelaksanaan JavaScript

Di bawah ialah pelaksanaan teguh algoritma Karatsuba dalam JavaScript. Versi ini menyokong integer yang besar sewenang-wenangnya dengan mewakilinya sebagai rentetan.

darab.js

/**
 * Karatsuba multiplication algorithm for large numbers.
 * @param {string} num1 - First large number as a string.
 * @param {string} num2 - Second large number as a string.
 * @returns {string} - Product of the two numbers as a string.
 */
function karatsubaMultiply(num1, num2) {
  // Remove leading zeros
  num1 = num1.replace(/^0+/, "") || "0";
  num2 = num2.replace(/^0+/, "") || "0";

  // If either number is zero, return "0"
  if (num1 === "0" || num2 === "0") return "0";

  // Base case for small numbers (12), use Number for safe multiplication
  if (num1.length <= 12 && num2.length <= 12) {
    return (Number(num1) * Number(num2)).toString();
  }

  // Ensure even length by padding
  const maxLen = Math.max(num1.length, num2.length);
  const paddedLen = Math.ceil(maxLen / 2) * 2;
  num1 = num1.padStart(paddedLen, "0");
  num2 = num2.padStart(paddedLen, "0");

  const mid = paddedLen / 2;

  // Split the numbers into two halves
  const high1 = num1.slice(0, -mid);
  const low1 = num1.slice(-mid);
  const high2 = num2.slice(0, -mid);
  const low2 = num2.slice(-mid);

  // Helper function for adding large numbers as strings
  function addLargeNumbers(a, b) {
    const maxLength = Math.max(a.length, b.length);
    a = a.padStart(maxLength, "0");
    b = b.padStart(maxLength, "0");

    let result = "";
    let carry = 0;

    for (let i = maxLength - 1; i >= 0; i--) {
      const sum = parseInt(a[i]) + parseInt(b[i]) + carry;
      result = (sum % 10) + result;
      carry = Math.floor(sum / 10);
    }

    if (carry > 0) {
      result = carry + result;
    }

    return result.replace(/^0+/, "") || "0";
  }

  // Helper function to multiply by 10^n
  function multiplyByPowerOf10(num, power) {
    return num === "0" ? "0" : num + "0".repeat(power);
  }

  // Helper function for subtracting large numbers
  function subtractLargeNumbers(a, b) {
    const maxLength = Math.max(a.length, b.length);
    a = a.padStart(maxLength, "0");
    b = b.padStart(maxLength, "0");

    let result = "";
    let borrow = 0;

    for (let i = maxLength - 1; i >= 0; i--) {
      let diff = parseInt(a[i]) - parseInt(b[i]) - borrow;
      if (diff < 0) {
        diff += 10;
        borrow = 1;
      } else {
        borrow = 0;
      }
      result = diff + result;
    }

    return result.replace(/^0+/, "") || "0";
  }

  // Recursive steps
  const z0 = karatsubaMultiply(low1, low2);
  const z1 = karatsubaMultiply(
    addLargeNumbers(low1, high1),
    addLargeNumbers(low2, high2)
  );
  const z2 = karatsubaMultiply(high1, high2);

  // Compute the result using Karatsuba formula
  const z1MinusZ2MinusZ0 = subtractLargeNumbers(
    subtractLargeNumbers(z1, z2),
    z0
  );

  const powerMidTerm = multiplyByPowerOf10(z1MinusZ2MinusZ0, mid);
  const z2Term = multiplyByPowerOf10(z2, 2 * mid);

  // Add all terms
  const term1 = addLargeNumbers(z2Term, powerMidTerm);
  const result = addLargeNumbers(term1, z0);

  return result;
}

// Example Usage
const num1 = "1234567890123456789023454353453454354345435345435435";
const num2 = "98765432109876543210";
console.log("Product:", karatsubaMultiply(num1, num2));

Salin selepas log masuk

node multiply.js

Salin selepas log masuk

Ciri Utama Pelaksanaan

Pengoptimuman Kes Asas:
- Untuk nombor sehingga 12 digit, algoritma secara langsung menggunakan Nombor JavaScript untuk pendaraban yang cekap.
Manipulasi Rentetan untuk Ketepatan Arbitrari:
- Algoritma menggunakan operasi rentetan untuk mengendalikan nombor yang besar tanpa kehilangan ketepatan.
Fungsi Pembantu:
- Tambahan (addLargeNumbers): Mengendalikan penambahan dua nombor besar yang diwakili sebagai rentetan.
- Penolakan (tolakNombor Besar): Menguruskan penolakan dengan meminjam nombor besar.
- Kuasa 10 Pendaraban (darabByPowerOf10): Mengalih nombor dengan cekap dengan menambahkan sifar.
Reka Bentuk Rekursif:
- Algoritma membahagikan setiap input secara rekursif, menggabungkan hasil menggunakan formula Karatsuba.

Pertimbangan Prestasi

Algoritma Karatsuba mengurangkan bilangan pendaraban rekursif daripada $(O (n^{2})) (O(n^2))$ (O(n2)) kepada lebih kurang $(O (n^{1.585})) (O(n^{1.585}))$ (O(n1.585)) . Ini menjadikannya lebih pantas daripada kaedah tradisional untuk input besar. Walau bagaimanapun, overhed manipulasi rentetan boleh menjejaskan prestasi untuk input yang lebih kecil, itulah sebabnya pengoptimuman kes asas adalah penting.

Contoh Output

Untuk:

/**
 * Karatsuba multiplication algorithm for large numbers.
 * @param {string} num1 - First large number as a string.
 * @param {string} num2 - Second large number as a string.
 * @returns {string} - Product of the two numbers as a string.
 */
function karatsubaMultiply(num1, num2) {
  // Remove leading zeros
  num1 = num1.replace(/^0+/, "") || "0";
  num2 = num2.replace(/^0+/, "") || "0";

  // If either number is zero, return "0"
  if (num1 === "0" || num2 === "0") return "0";

  // Base case for small numbers (12), use Number for safe multiplication
  if (num1.length <= 12 && num2.length <= 12) {
    return (Number(num1) * Number(num2)).toString();
  }

  // Ensure even length by padding
  const maxLen = Math.max(num1.length, num2.length);
  const paddedLen = Math.ceil(maxLen / 2) * 2;
  num1 = num1.padStart(paddedLen, "0");
  num2 = num2.padStart(paddedLen, "0");

  const mid = paddedLen / 2;

  // Split the numbers into two halves
  const high1 = num1.slice(0, -mid);
  const low1 = num1.slice(-mid);
  const high2 = num2.slice(0, -mid);
  const low2 = num2.slice(-mid);

  // Helper function for adding large numbers as strings
  function addLargeNumbers(a, b) {
    const maxLength = Math.max(a.length, b.length);
    a = a.padStart(maxLength, "0");
    b = b.padStart(maxLength, "0");

    let result = "";
    let carry = 0;

    for (let i = maxLength - 1; i >= 0; i--) {
      const sum = parseInt(a[i]) + parseInt(b[i]) + carry;
      result = (sum % 10) + result;
      carry = Math.floor(sum / 10);
    }

    if (carry > 0) {
      result = carry + result;
    }

    return result.replace(/^0+/, "") || "0";
  }

  // Helper function to multiply by 10^n
  function multiplyByPowerOf10(num, power) {
    return num === "0" ? "0" : num + "0".repeat(power);
  }

  // Helper function for subtracting large numbers
  function subtractLargeNumbers(a, b) {
    const maxLength = Math.max(a.length, b.length);
    a = a.padStart(maxLength, "0");
    b = b.padStart(maxLength, "0");

    let result = "";
    let borrow = 0;

    for (let i = maxLength - 1; i >= 0; i--) {
      let diff = parseInt(a[i]) - parseInt(b[i]) - borrow;
      if (diff < 0) {
        diff += 10;
        borrow = 1;
      } else {
        borrow = 0;
      }
      result = diff + result;
    }

    return result.replace(/^0+/, "") || "0";
  }

  // Recursive steps
  const z0 = karatsubaMultiply(low1, low2);
  const z1 = karatsubaMultiply(
    addLargeNumbers(low1, high1),
    addLargeNumbers(low2, high2)
  );
  const z2 = karatsubaMultiply(high1, high2);

  // Compute the result using Karatsuba formula
  const z1MinusZ2MinusZ0 = subtractLargeNumbers(
    subtractLargeNumbers(z1, z2),
    z0
  );

  const powerMidTerm = multiplyByPowerOf10(z1MinusZ2MinusZ0, mid);
  const z2Term = multiplyByPowerOf10(z2, 2 * mid);

  // Add all terms
  const term1 = addLargeNumbers(z2Term, powerMidTerm);
  const result = addLargeNumbers(term1, z0);

  return result;
}

// Example Usage
const num1 = "1234567890123456789023454353453454354345435345435435";
const num2 = "98765432109876543210";
console.log("Product:", karatsubaMultiply(num1, num2));

Salin selepas log masuk

Hasilnya ialah:

node multiply.js

Salin selepas log masuk

Kesimpulan

Algoritma pendaraban Karatsuba ialah penyelesaian yang praktikal dan cekap untuk mendarab nombor besar. Pelaksanaan ini menunjukkan kuasa dan fleksibilitinya apabila mengendalikan input besar secara sewenang-wenangnya dalam JavaScript. Dengan keperluan yang semakin meningkat untuk aritmetik berketepatan tinggi, menguasai algoritma sedemikian boleh meningkatkan keupayaan pengiraan dalam pelbagai aplikasi.

Atas ialah kandungan terperinci Memahami dan Melaksanakan Algoritma Pendaraban Karatsuba untuk Nombor Besar. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!