Phép nhân số nguyên lớn trong Python

Phép nhân số nguyên lớn là một quy trình phổ biến trong giải quyết vấn đề có sự trợ giúp của máy tính. Nhân các số lớn không chỉ khó mà còn tốn thời gian và dễ sai sót

Trong bài này, chúng ta sẽ xem xét hai cách tiếp cận để nhân các số lớn. phương pháp trường lớp và phương pháp chia để trị

Phép nhân số nguyên lớn

Phép nhân số nguyên lớn sử dụng phép nhân cấp trường

Ở trường, chúng tôi học kỹ thuật nhân truyền thống. Số bị nhân được nhân với từng chữ số của số bị nhân trong kỹ thuật đó và một phần kết quả của mỗi phép nhân được thêm vào bằng cách thực hiện chuyển dịch thích hợp. Phương pháp này còn được gọi là Phương pháp nhân truyền thống

Ví dụ sau minh họa cách thực hiện phép nhân ở trường tiểu học theo cả cách của người Mỹ và người Anh

Phép nhân ma trận truyền thống

Cách tiếp cận này đơn giản để nắm bắt, nhưng nó tốn thời gian và không hiệu quả. Nếu phép nhân có n chữ số và phép nhân có m chữ số thì độ phức tạp của phép nhân sẽ là O(mn)

Kỹ thuật này cần thời gian bậc hai, không đủ cho các số lớn. Hãy xem xét một phương pháp nhân thuận tiện hơn

Nhân số nguyên lớn bằng phương pháp chia để trị

Có hai cách để thực hiện phép nhân số nguyên lớn bằng phép chia và trị. Phương pháp đầu tiên – chúng tôi gọi là phương pháp câm – không cải thiện thời gian chạy. Phương pháp thứ hai – chúng tôi gọi là phương pháp thông minh – thực hiện tốt hơn phương pháp truyền thống để nhân số nguyên

Cách tiếp cận ngu ngốc

Hãy để chúng tôi đại diện cho số D là D = dn-1dn-2. . . d2d1d0. Mỗi chữ số di là chữ số có nghĩa nhỏ thứ i trong số D. Giá trị của mỗi vị trí được đưa ra bởi,

d0 = 100 vị trí

d1 = 101 vị trí

d2 = 102 vị trí

.

dn – 1 = 10n – 1 vị trí

Theo giá trị vị trí,

45 = 4*101 + 5*100

23 = 2*101 + 3*100

Với mọi giá trị thực a, b, c và d,

(a + b)*(c + d) = (a*c + a*d + b*c + b*d)

Vì vậy, 45 * 23    =   (4*101 + 5*100) * (2*101 + 3*100)

=   (4 *2) *102 + (4*3 + 5*2) *101 + (5*3) *100

= 800 + 220 + 15

= 1035

Hãy rút ra công thức nhân hai số có hai chữ số mỗi số. Xét C = A * B. Nếu chúng ta coi A = a1a0 và B = b1b0 thì

C = A * B = c2102 + c1101 + c0100

Ở đâu,

c2 = a1 * b1

c1 = a1* b0 + a0* b1

c0 = a0 * b0

Phương pháp này thực hiện bốn phép nhân, giống như phương pháp thông thường. Điều này cũng ngớ ngẩn như phép nhân ở trường tiểu học. Thuật toán cho phương pháp này được mô tả dưới đây

Algorithm DC_DUMB_MULTIPLICATION(A, B)
// Description : Perform multiplication of large numbers using divide and conquer strategy.
// Input : Number A and B, where A = an-1…a1a0, 
B = bn-1.. b1b0
// Output : Multiplication of A and B as C, i.e. C = A * B

if |a| == 1 or |b| == 1 then
    return A * B
else
    n ← max(|A|, |B|)	// returns maximum number digits
    c2 ← DC_DUMB_MULTIPLICATION(a1, b1)
    c0 ← DC_DUMB_MULTIPLICATION(a0, b0)
    x ← DC_DUMB_MULTIPLICATION(a1, b0)
    y ← DC_DUMB_MULTIPLICATION(a0, b1)
    c1 ← x + y
    return c2*10n + c1 * 10n/2+ c0
end

Thí dụ. Nhân 2345 với 678 bằng phương pháp chia để trị

Giải pháp

Kích thước của cả hai toán hạng phải bằng nhau, do đó, nhập số 0 vào số nhân

A = 2345 và B = 0678

A = a1a0 = 2345, do đó a1 = 23 và a0 = 45

B = b1b0 = 0678, do đó b1 = 06 và b0 = 78

C = A * B =c2104 + c1102 + c0100

c2 = a1 * b1

= 23 * 06

= 138

c1 = a1*b0 + a0*b1

= (23*78) + (45 * 06)

= 2064

c0 = a0 * b0

=(45 * 78)

= 3510

C = c2102 + c1101 + c0100

= 138*104 + 2064*102 + 3510

= 15, 89, 910

Cách tiếp cận thông minh

Cách tiếp cận DC trước đây thực hiện bốn phép nhân. Hãy lập công thức lại để giảm số phép nhân xuống còn ba

Cách tiếp cận đầu tiên

Theo cách tiếp cận ngu ngốc,

c2 = a1 * b1

c1 = a1*b0 + a0*b1 …(1)

c0 = a0*b0

Cách tiếp cận thứ hai

Hãy để chúng tôi viết lại c1 như,

c1 = (a1 + a0) * (b1 + b0) – (c2 + c0)

= (a1b1 + a1b0 + a0b1 + a0b0) – (a1b1 + a0b0)

= a1*b0 + a0*b1 …(2)

Phương trình (1) và Phương trình (2) giống nhau, nhưng phương pháp tính toán c1 thứ hai chỉ liên quan đến một phép nhân thay vì hai như yêu cầu trong phương pháp thứ nhất

Với A = a1a0 = 2345,

do đó, a1 = 23 và a0 = 45 và

B = b1b0 = 0678,

do đó, b1 = 06 và b0 = 78

c2 = a1 * b1

= 23 * 06

= 138

c0 = a0*b0

= (45 * 78)

= 3510

c1 = (a1 + a0) * (b1 + b0) – (c2 + c0)

= (23 + 45) * (06 + 78) – (138 + 3510)

= 68 * 84 – 3648

= 2064

Nó giống như c1 = (a1*b0 + a0*b1) của phương pháp nhân câm, nhưng chỉ thực hiện một phép nhân chứ không phải hai

C = c2 * 104 + c1 * 102 + c0

= 1380000 + 206400 + 3510 = 15, 89, 910

Công thức này dẫn đến cùng một kết quả, chỉ với ba phép nhân

Sự khái quát

Nếu kích thước của số nguyên là n chữ số, thì chúng ta có thể khái quát phép nhân thành,

C = c210n + c110n/2 + c0

Trong đó, c2 = a1 * b1

c0 = a0*b0

c1 = (a1 + a0) * (b1 + b0) – (c2 + c0)

Điều này có thể được giải quyết bằng cách áp dụng đệ quy cho đến khi n tiến tới 1

Algorithm DC_CLEVER_MULTIPLICATION(A, B)
// Description : Perform multiplication of large numbers using divide and conquer strategy.
// Input : Number A and B, where A = an-1…a1a0, and B = bn-1...b1b0
// Output : Multiplication of A and B as C, i.e. C = A * B

if |a| == 1 or |b| == 1 then
    return  A * B
else
    n ← max(|A|, |B|)	
    c2 ← DC_ CLEVER_MULTIPLICATION(a1, b1)
    c0 ← DC_ CLEVER_MULTIPLICATION(a0, b0)
    x ← DC_ CLEVER_MULTIPLICATION(a1 + a0, b1 + b0)
    return c2*10n + (x – c2 – c0) * 10n/2 + c0
end

Phân tích độ phức tạp

Với số nguyên n chữ số ta phải thực hiện 3 phép nhân các số nguyên cỡ (n/2). Phương trình tái phát cho vấn đề này được đưa ra là,

T(n) = 3T(n/2), nếu n > 1

T(n) = 1, nếu n = 1

Bằng chứng

T(n) = 3T(n/2) … (3)

Hãy để chúng tôi giải quyết sự lặp lại này bằng cách tiếp cận lặp đi lặp lại. Thay thế n bởi n/2 trong phương trình (3)

T(n/2) = 3T(n/4) … (4)

Đặt giá trị này vào phương trình (3),

T(n) = 3(3T(n/4)) = 32T(n/22) … (5)

Thay n bằng n/2 trong phương trình (4)

T(n/4) = 3T(n/8)

Đặt giá trị này vào phương trình (3)

T(n) = 3(32T(n/8)) = 33T(n/23) … (6)

.

.

Sau k lần lặp,

T(n) = 3kT(n/2k) …(7)

Mỗi khi số chữ số trong số giảm đi 2 lần, do đó, nó có thể đi sâu tới log2n,

Vì vậy, k = log2n ⇒ n = 2k

Do đó, từ phương trình (5), T(n) = 3kT( 2k /2k)

T (n) = nlog23 × T(1) (∵ nlogba = alogb n)

T(1) = 1(Chỉ cần một phép nhân để nhân hai số có chữ số 1)

Vì vậy, T(n) = nlog23 = O(n1. 58)

Phương pháp phổ thông nhân từng chữ số của cấp số nhân với từng chữ số của số bị nhân. Vậy với mỗi chữ số của cấp số nhân, n phép nhân được thực hiện với cấp số nhân. Điều này được thực hiện từng bit trong số n bit của hệ số nhân. Vì vậy, thời gian chạy của phương pháp đó là O(n2), trong khi phương pháp chia để trị làm giảm thời gian chạy xuống còn O(n1. 58). Đối với số lượng lớn, sự khác biệt trở nên đáng kể

Thí dụ

Vấn đề. Thực hiện phép nhân các số nguyên lớn đã cho 957 ´ 9873 nhanh hơn O(n2)

Giải pháp

Gọi A = a1a0 = 0957,

do đó a1 = 09 và a0 = 57 và

B = b1b0 = 9873,

do đó b1 = 98 và b0 = 73

Vấn đề đã cho có kích thước 4, vì vậy n = 4

Giải pháp cho vấn đề này bằng cách sử dụng phương pháp phân chia và chinh phục có thể được đưa ra là,

C = c2 * 104 + c1 * 102 + c0

Trong đó, c2 = a1 * b1

c0 = a0*b0

c1 = (a1 + a0) * (b1 + b0) – (c2 + c0)

Hãy tính c0, c1 và c2

c2 = a1 * b1 = 09 * 98

Đây là một vấn đề mới có kích thước 2, giải quyết nó theo cách đệ quy,

Ở đây X = x1x0 = 09 và do đó x1 = 0 và x0 = 9

Y = y1y0 = 98 = 09 và do đó y1 = 9 và y0 = 8

z2 = x1 * y1

= 0 * 9

= 0

z0 = x0 * y0

= 9 * 8

= 72

z1 = x0 + x1) * (y0 + y1) – (z2 + z0)

= (0 + 9) *(9 + 8) – (0 + 72)

= (9*17) – 72

= 81

Z = z2 * 102 + z1 * 10 + z0

= 0 + 810 + 72

= 882

c0 = a0*b0 = (57 * 73)

Giống như c2, đây cũng là bài toán cỡ 2 và được giải tương tự theo cách đệ quy, và điều tương tự sẽ áp dụng cho việc tính toán c1

c0 = 4161

c1 = (a1 + a0) * (b1 + b0) – (c2 + c0)

= (09 + 57) * (98 + 73) – (882 + 4161)

= (66 * 171) – 5043

= 6243

C = c2 * 104 + c1 * 102 + c0

= 8820000 + 624300 + 4161

= 94, 48, 461

Công thức này dẫn đến cùng một kết quả, chỉ với ba phép nhân

Vấn đề. Trình bày các bước nhân hai số nguyên sau bằng phương pháp nhân hiệu số 2101 * 1130

Phép nhân số nguyên lớn là gì?

Python có thể xử lý một số lớn đến mức nào?