Cấu trúc dữ liệu và Giải thuật Bài 108: Toán học số học & Thuật toán số lớn (BigInt Arithmetic) - Xử lý tính toán với các số nguyên có kích thước cực lớn vượt ngưỡng phần cứng.

Trong kiến trúc máy tính truyền thống, CPU xử lý các kiểu dữ liệu số nguyên có kích thước cố định: 32-bit (int32) hoặc 64-bit (int64). Kiểu int64 lớn nhất chỉ chứa được giá trị xấp xỉ $9.22 \times 10^{18}$ .

Tuy nhiên, trong nhiều bài toán thực tế, các con số vượt xa giới hạn phần cứng này:

Mật khẩu & Mã hóa (Cryptography): Các thuật toán mã hóa hiện đại như RSA sử dụng các khóa có độ dài từ 2048-bit đến 4096-bit, tương đương với các con số có hàng trăm đến hàng nghìn chữ số thập phân.
Blockchain & Smart Contracts: Hệ thống Ethereum tính toán số dư token bằng đơn vị Wei (1 ETH = $10^{18}$ Wei). Khi thực hiện các phép tính nhân chia với lượng cung token khổng lồ, tràn số (Integer Overflow/Underflow) sẽ gây sập hợp đồng thông minh hoặc thất thoát tài sản.
Khoa học tính toán (Scientific Computing): Tính giai thừa của các số lớn như $1000!$ (tạo ra một con số có hơn 2500 chữ số).

Để giải quyết triệt để vấn đề này, khoa học máy tính sử dụng BigInt Arithmetic (Thuật toán số học số lớn) — giả lập các phép tính toán học thủ công bằng cấu trúc dữ liệu mảng (array/slice).

1. Biểu diễn số lớn trong bộ nhớ

Thay vì lưu trữ số trong một ô nhớ CPU duy nhất, một số nguyên lớn được biểu diễn dưới dạng mảng (slice) các chữ số.

Cách tiếp cận cơ bản: Mỗi phần tử trong mảng lưu một chữ số từ $0$ đến $9$ . Ví dụ, số 12345 được lưu trong mảng theo thứ tự đảo ngược để dễ tính toán: [5, 4, 3, 2, 1].
Cách tiếp cận tối ưu (Base $10^9$ / Chunking): Để tăng tốc độ thực thi, mỗi phần tử của mảng không chỉ lưu 1 chữ số mà lưu một khối (chunk) có giá trị lên đến $10^9 - 1$ (tức là hệ cơ số $10^9$ ). Nhờ đó, một mảng ngắn có thể biểu diễn những con số dài hàng nghìn chữ số mà giảm thiểu số lần lặp vòng lặp.

2. Các thuật toán phép tính cơ bản trên số lớn

A. Phép cộng số lớn (BigInt Addition)

Mô phỏng lại cách chúng ta cộng hai số bằng tay từ phải sang trái (Cột dọc):

Duyệt từ phần tử đầu tiên (đơn vị) đến hết mảng.
Cộng hai chữ số tại cùng vị trí cộng với số nhớ (carry) từ hàng trước.
Chữ số mới tại vị trí đó bằng (sum % 10) (hoặc cơ sở tương ứng), và số nhớ mới bằng (sum / 10).

Độ phức tạp thời gian: $O(N)$ với $N$ là số lượng chữ số của số lớn nhất.

B. Phép nhân số lớn (BigInt Multiplication)

Thuật toán trường học (Schoolbook Multiplication): Nhân từng chữ số của số này với từng chữ số của số kia rồi cộng dồn kết quả dịch cột. Độ phức tạp: $O(N \times M)$ .
Thuật toán Karatsuba: Sử dụng tư tưởng chia để trị (Divide and Conquer) để hạ độ phức tạp xuống $O(N^{\log_2 3}) \approx O(N^{1.585})$ , cực kỳ tối ưu cho các số có hàng chục nghìn chữ số.

3. Hiện thực hóa Phép cộng số lớn bằng Golang

Đoạn code Golang dưới đây cài đặt cấu trúc dữ liệu cơ bản biểu diễn số lớn dưới dạng chuỗi/mảng đảo ngược và thuật toán cộng hai số nguyên không giới hạn độ dài:

package main

import (
	"fmt"
	"strings"
)

// Hàm cộng hai số nguyên lớn được biểu diễn dưới dạng chuỗi (strings)
func AddBigInt(num1 string, num2 string) string {
	i := len(num1) - 1
	j := len(num2) - 1
	carry := 0
	var result []string

	// Duyệt từ phải qua trái (từ hàng đơn vị lên hàng cao nhất)
	for i >= 0 || j >= 0 || carry > 0 {
		sum := carry

		if i >= 0 {
			sum += int(num1[i] - '0')
			i--
		}

		if j >= 0 {
			sum += int(num2[j] - '0')
			j--
		}

		// Tính số nhớ cho lần lặp tiếp theo
		carry = sum / 10

		// Lưu phần dư vào kết quả
		digitChar := fmt.Sprintf("%d", sum%10)
		result = append(result, digitChar)
	}

	// Đảo ngược mảng kết quả vì ta duyệt từ phải sang trái
	for l, r := 0, len(result)-1; l < r; l, r = l+1, r-1 {
		result[l], result[r] = result[r], result[l]
	}

	return strings.Join(result, "")
}

func main() {
	// Hai con số cực lớn vượt quá giới hạn int64 của phần cứng
	num1 := "123456789012345678901234567890"
	num2 := "987654321098765432109876543210"

	sum := AddBigInt(num1, num2)

	fmt.Printf("Số thứ nhất: %s\n", num1)
	fmt.Printf("Số thứ hai:  %s\n", num2)
	fmt.Printf("Tổng kết quả: %s\n", sum)
}

4. Ứng dụng thực tế

Thư viện chuẩn của ngôn ngữ: Hầu hết các ngôn ngữ lập trình hiện đại đều tích hợp sẵn thư viện BigInt (như math/big trong Golang hay BigInteger trong Java/Python) để tự động xử lý các bài toán tài chính và mã hóa mà lập trình viên không phải tự viết từ đầu.
Hệ thống thanh toán toàn cầu: Đảm bảo độ chính xác tuyệt đối từng đồng xu / satoshi (đơn vị nhỏ nhất của Bitcoin bằng $10^{-8}$ BTC) mà không gặp sai số dấu phẩy động (Floating-point rounding errors).

Số học số lớn là minh chứng cho việc bằng cách thay đổi cấu trúc lưu trữ dữ liệu (từ thanh ghi phần cứng sang mảng động trong RAM), chúng ta có thể mở rộng biên giới tính toán của máy tính đến vô tận.

cấu trúc dữ liệu