Một số nguyên 64-bit chứa được tới khoảng 19 chữ số thập phân. Nhưng mật mã RSA cần số 600 chữ số, một giai thừa lớn hay số Fibonacci thứ triệu có hàng trăm nghìn chữ số. Những số ấy không vừa một thanh ghi CPU, nên phải lưu thành mảng và làm phép tính thủ công — đúng như cách ta cộng, nhân bằng tay hồi tiểu học. Bài này đo chi phí thật của phép nhân số lớn, và kiểm một niềm tin quen thuộc: rằng thuật toán "thông minh hơn" (Karatsuba) luôn thắng thuật toán "ngây thơ" (nhân học sinh).
Số lớn là một mảng chữ số
Một bignum lưu số dưới dạng mảng các hạn (limb) — mỗi hạn là một "chữ số" trong cơ số lớn, thường 2³² hay 2⁶⁴. Cộng hai số n hạn là O(n): cộng từng cặp hạn kèm nhớ, như cộng tay theo cột. Nhân mới là chỗ tốn: cách học sinh (schoolbook) nhân mỗi hạn của số này với mỗi hạn của số kia rồi cộng dồn — đúng n × n phép nhân hạn, tức O(n²). Số gấp đôi chữ số thì công gấp bốn.
Năm 1960, Karatsuba tìm ra một mẹo hay. Chẻ mỗi số n hạn làm đôi: a = a₁·B + a₀. Nhân thẳng cần bốn tích con (a₁b₁, a₁b₀, a₀b₁, a₀b₀). Karatsuba nhận ra chỉ cần ba: tính a₁b₁, a₀b₀, và (a₁+a₀)(b₁+b₀), rồi phần giữa a₁b₀+a₀b₁ suy ra bằng phép trừ. Ba phép nhân nửa-kích-thước thay vì bốn, đệ quy xuống, cho độ phức tạp O(n^1,585) — bậc thấp hơn hẳn O(n²). Đây là chia để trị kinh điển. Nghe như Karatsuba phải luôn nhanh hơn. Tôi đo, và số nhỏ nói khác.
Đo: schoolbook đúng là O(n²)
Trước hết kiểm hai cách cho cùng kết quả (chúng khớp từng hạn ở n=100), rồi đo thời gian nhân hai số n hạn với n tăng dần. Một hạn 32-bit ≈ 9,6 chữ số thập phân, nên n=1024 hạn là số ~9.800 chữ số.
Thời gian nhân hai số n hạn (micro giây):
n hạn (~chữ số) | schoolbook | Karatsuba
64 (~ 614) | 1,5 | 4,2
128 (~ 1.228) | 7,5 | 13,5
256 (~ 2.457) | 31,0 | 43,4
512 (~ 4.915) | 125,6 | 139,1
1024 (~ 9.830) | 520,0 | 455,4 <- điểm giao
2048 (~19.660) | 2.050,9 | 1.731,9
4096 (~39.321) | 8.312,0 | 5.291,2
Cột schoolbook xác nhận O(n²): mỗi lần n gấp đôi, thời gian gần gấp bốn (7,5 → 31 → 125,6 → 520, tỉ lệ đều ~4,1). Cột Karatsuba tăng chậm hơn — mỗi lần n gấp đôi chỉ gấp khoảng ba (2^1,585 ≈ 3), đúng dấu hiệu O(n^1,585). Hai đường cong có độ dốc khác nhau, và chúng phải cắt nhau ở đâu đó.
Một lần tôi đo hớ: bậc thấp hơn không tự động thắng
Niềm tin tôi mang vào: "Karatsuba có O tốt hơn thì luôn nhanh hơn nhân học sinh". Bảng bác bỏ nó suốt bảy hàng đầu. Ở mọi kích thước tới 512 hạn, schoolbook nhanh hơn. Tệ hơn cho niềm tin đó: ở 64 hạn (~600 chữ số — đã là số rất lớn với đời thường), Karatsuba chậm hơn 2,8 lần (4,2 so với 1,5 µs). Điểm giao chỉ đến ở 1024 hạn — khoảng 9.800 chữ số thập phân. Dưới ngưỡng khổng lồ ấy, thuật toán "ngây thơ" thắng thuật toán "thông minh".
Vì sao? Vì Big-O giấu hằng số. O(n^1,585) của Karatsuba đi kèm một hằng số ẩn lớn: mỗi tầng đệ quy phải làm nhiều phép cộng và trừ để ghép ba tích con lại, phải cấp phát bộ nhớ tạm cho chúng, phải quản lý lời gọi đệ quy. Với số nhỏ, cái đống chi phí phụ ấy lớn hơn phần công mà bậc tốt hơn tiết kiệm được. Chỉ khi n đủ lớn — khi n² đủ vượt trội n^1,585 để bù cho hằng số — Karatsuba mới thắng. Đây đúng là bài học điểm giao của chia để trị mà sê-ri đã gặp: một thuật toán tiệm cận tốt hơn không có nghĩa nhanh hơn ở kích thước thực tế của bạn.
Con số cần đối chiếu để thấy toàn cảnh: một phép nhân 64-bit gốc của CPU chạy 0,74 nano giây — một lệnh máy. Nhân hai số 1024 hạn tốn 520 µs, tức ~700.000 lần chậm hơn. Đó là cái giá thật của "số lớn": mỗi khi bạn rời khỏi kích thước vừa thanh ghi, bạn trả một khoản khổng lồ, và câu hỏi thuật toán (schoolbook hay Karatsuba) chỉ là chọn mức khổng lồ ấy.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên rất cụ thể: thuật toán tiệm cận tốt hơn chỉ đáng dùng khi dữ liệu vượt điểm giao của nó. Nếu bạn viết một thư viện số lớn và mù quáng luôn dùng Karatsuba, bạn làm chậm mọi phép nhân trên số dưới ~10.000 chữ số — tức gần như mọi phép trong thực tế. Đây không phải chuyện riêng bignum: cùng bẫy với mọi cặp "thuật toán O tốt / hằng số lớn" so với "thuật toán O tệ / hằng số nhỏ". Đo điểm giao cho triển khai của bạn, trên phần cứng của bạn rồi mới chọn.
Hệ quả thứ hai: các thư viện thật không chọn một thuật toán — chúng chuyển thuật toán theo kích thước. GMP (thư viện số lớn chuẩn) dùng schoolbook cho số nhỏ, chuyển sang Karatsuba khi vượt một ngưỡng, rồi Toom-Cook, rồi FFT cho số cực lớn — mỗi thuật toán ngự trị đúng khoảng kích thước mà nó nhanh nhất. Đây chính xác là ý tưởng của introsort mà bài sắp xếp lai đã đo: dùng thuật toán đơn giản cho phần nhỏ, thuật toán phức tạp cho phần lớn, và ngưỡng chuyển được đo chứ không đoán. Một thư viện tốt là một tập hợp thuật toán kèm các ngưỡng đã hiệu chỉnh.
Hệ quả thứ ba là bài học đo lường bao trùm: "độ phức tạp tốt hơn" là một lời hứa về hành vi khi n → vô cùng, không phải về tốc độ ở n của bạn. Con số mang theo: nhân học sinh là O(n²) nhưng thắng Karatsuba O(n^1,585) tới tận ~1024 hạn (~9.800 chữ số), vì hằng số ẩn của Karatsuba — đệ quy, cộng, trừ, cấp phát — lớn hơn cái bậc tốt hơn tiết kiệm; ở 64 hạn Karatsuba còn chậm 2,8 lần, và mọi phép số lớn chậm hơn nhân 64-bit gốc hàng trăm nghìn lần. Trước khi thay một thuật toán bằng cái "nhanh hơn về lý thuyết", hãy hỏi kích thước dữ liệu thật của mình nằm ở đâu trên đường cong — nhiều khi nó nằm hẳn ở phần mà cái đơn giản vẫn thắng.
Thử ba mươi giây
Trong Python (nơi int là bignum sẵn), đo thử độ dốc O(n²) của phép nhân: import time; a=b=10**5000; t=time.perf_counter(); [a*b for _ in range(10000)]; print(time.perf_counter()-t) — ghi lại thời gian; rồi đổi 10**5000 thành 10**10000 (gấp đôi số chữ số) và đo lại. Nếu thời gian tăng khoảng bốn lần, bạn đang ở vùng schoolbook O(n²); nếu tăng ít hơn (gần ba lần), CPython đã tự chuyển sang Karatsuba (nó làm vậy quanh ngưỡng ~70 chữ số nội bộ). Dù cách nào, bạn cũng sẽ thấy tận mắt rằng nhân số lớn không miễn phí như nhân int thường — và độ dốc của đường cong chính là thuật toán bên dưới đang tự khai báo nó là ai.
