Thuật toán 'thông minh' của Karatsuba thua nhân tay tới tận 9.800 chữ số

Một chiếc máy tính bỏ túi hiện được số có 8 chữ số, quá số đó nó báo lỗi. Nhưng đầu bạn thì không: cần nhân hai số hai mươi chữ số, bạn vẫn làm được — chỉ là phải lấy giấy ra, kê cột, nhân từng chữ số rồi cộng dồn, chậm hơn nhiều. CPU cũng đúng thế. Một thanh ghi 64-bit chứa tối đa khoảng 19 chữ số thập phân; quá đó, số phải nằm thành mảng và mọi phép tính làm thủ công theo cột, y như hồi tiểu học. Mà mật mã RSA cần số 600 chữ số, một số Fibonacci thứ triệu có hàng trăm nghìn chữ số — nên "làm tay" không phải chuyện hiếm, nó là nền của cả một mảng thư viện. Bài này đo chi phí thật của phép nhân số lớn, và soi 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ớ, đúng 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 đẹp. 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 cho 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 hẳn.

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, nên chúng phải cắt nhau ở đâu đó.

Bậc thấp hơn không tự động thắng

Niềm tin tôi mang vào rất chắc: "Karatsuba có O tốt hơn thì luôn nhanh hơn nhân học sinh". Bảng bác 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 ấy: ở 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 cái ngưỡng khổng lồ đó, 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 thê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. Đúng 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.

Còn một con số cần đặt cạnh để 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 — đúng 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 một 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 nông hay sâu.

Về đến code hằng ngày

Điều đầ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 gọi 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ế. Chuyện này không riêng gì bignum: cùng cái bẫy với mọi cặp "thuật toán O tốt / hằng số lớn" đọ 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.

Điều 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.

Và đây là chỗ dân viết ứng dụng cao cấp thường quên rằng mình đang dùng bignum. Java BigInteger.multiply chính là cỗ máy chuyển tầng đó: nó dùng schoolbook cho số nhỏ rồi tự nhảy sang Karatsuba và Toom-Cook khi số đủ dài — nên một vòng lặp BigInteger tưởng vô hại có thể là điểm nóng ẩn nếu số phình to. Go có math/big.Int với cùng tinh thần. Và cơ sở dữ liệu: kiểu NUMERIC/DECIMAL của Postgres là số học chính xác tùy ý (chính là bignum) — nó đúng đến từng xu nhưng chậm hơn bigint gốc nhiều lần, nên một cột tiền tệ tính toán nặng nên cân nhắc lưu số nguyên đơn vị nhỏ nhất (xu) thay vì NUMERIC nếu giá trị vừa 64-bit. Mẫu số chung: "độ phức tạp tốt hơn" là 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; và rất nhiều phép "số bình thường" thật ra đã là số lớn trá hình.

Muốn tự thấy thì trong Python (nơi int là bignum sẵn), đo độ 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. Thời gian tăng khoảng bốn lần thì bạn đang ở vùng schoolbook O(n²); tăng ít hơn (gần ba lần) thì CPython đã tự chuyển sang Karatsuba (nó làm vậy quanh ngưỡng ~70 chữ số nội bộ). Cách nào cũng thế, bạn 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 nó là ai.