I. Mở đầu về số nguyên lớn trong lập trình

Chúng ta đều biết rằng, việc giải bài toán bằng máy tính nói chung và lập trình thi đấu nói riêng luôn luôn đối mặt với dữ liệu có kích thước rất lớn. Hiển nhiên là vì những dữ liệu quá lớn vượt ra ngoài khả năng tính toán của con người, nên mới cần tới sự trợ giúp của máy tính.

Với sự nâng cấp liên tục của máy tính điện tử, độ lớn dữ liệu mà máy tính có thể lưu trữ được cũng ngày càng tăng lên. Tuy nhiên, khả năng lưu trữ luôn luôn là hữu hạn, mà dữ liệu là vô hạn (dữ liệu dạng văn bản có thể dài vô hạn, dữ liệu dạng số có thể cực kỳ lớn,...). Ngôn ngữ lập trình đã có sẵn rất nhiều kiểu dữ liệu với khoảng giá trị rất lớn, nhưng cũng không phải luôn luôn lưu trữ được mọi giá trị.

Riêng đối với kiểu số trong C++, chúng ta có sẵn kiểu dữ liệu nguyên thủy là long long với tầm lưu trữ lên tới khoảng $20$ chữ số. Nhưng nếu như có những dữ liệu số với độ dài nhiều hơn thế thì sao? Kĩ thuật xử lý số nguyên lớn ra đời nhằm giải quyết vấn đề đó. Trong chuyên đề này, chúng ta sẽ được học cách biểu diễn các số nguyên lên tới hàng trăm, hàng nghìn, thậm chí vài chục nghìn chữ số,...dựa vào khả năng lưu trữ chuỗi kí tự của máy tính. Các số nguyên sẽ được chuyển sang dạng chuỗi kí tự, sau đó thiết kế những phép toán cộng, trừ, nhân, chia, đồng dư tương ứng. Do độ dài của chuỗi kí tự phụ thuộc vào khả năng lưu trữ của trình biên dịch (mà thông thường rất lớn) nên ta dễ dàng giải quyết vấn đề.

Trước khi đọc chuyên đề này, bạn đọc nên nắm vững các kĩ thuật xử lý chuỗi kí tự, các quy tắc so sánh kí tự trong máy tính cũng như kiến thức về nạp chồng toán tử. Các cài đặt cụ thể trong bài viết sẽ được minh họa bằng ngôn ngữ C++11.

II. Cách biểu diễn số nguyên lớn

1. Biểu diễn bằng chuỗi kí tự

Một cách hay để biểu diễn các số nguyên lớn trong C++ là sử dụng lớp chuỗi kí tự <string> trong C++. Các chữ số sẽ tương ứng với các kí tự trong chuỗi, và độ dài của các số khi đó sẽ phụ thuộc vào chương trình biên dịch của ngôn ngữ. Phương pháp biểu diễn này khá được ưa chuộng vì nó đơn giản, dễ hiểu, tuy nhiên trong một số trường hợp cụ thể, thời gian chạy của chương trình cài đặt số lớn bằng string sẽ khá lâu. Mình sẽ giải thích cụ thể ở các thuật toán chi tiết.

2. Biểu diễn bằng mảng các kí tự

Sử dụng một mảng để chứa các chữ số cũng là một phương án thường được sử dụng. Với phương pháp này, mỗi chữ số sẽ tương ứng với một kí tự trong mảng, đồng thời ta duy trì một biến đếm để kiểm soát số chữ số của số ban đầu. Với phương pháp này, tuy cài đặt có khó hơn, nhưng tốc độ chạy chương trình sẽ nhanh hơn, và chúng ta cũng không cần tới thao tác chuyển đổi giữa kí tự và chữ số như phương pháp đầu tiên.

III. Các phép toán đối với số nguyên lớn (nhập xuất, so sánh, cộng - trừ)

Bây giờ thì chúng ta sẽ đi vào cách cài đặt cụ thể với từng phép toán đối với số nguyên lớn. Mình sẽ cài đặt các phép toán ở cả hai phương pháp sử dụng chuỗi kí tự và mảng các chữ số. Để cho đơn giản, chúng ta sẽ quy định như sau:

• Đối với phương pháp thứ nhất, mình định nghĩa một kiểu bignum_str để biểu diễn các số lớn (chính là string):

  typedef string bignum_str;
  

• Đối với phương pháp thứ hai, mình định nghĩa một kiểu bignum_vec để biểu diễn mảng chứa các chữ số của số nguyên, ở đây sử dụng kiểu vector:

  typedef vector < int > bignum_vec;
  

Ngoài ra, chúng ta sẽ coi như chỉ thực hiện các phép toán đối với các số nguyên không âm thôi. Nếu muốn sử dụng tính toán số lớn với các số nguyên có dấu, các bạn chỉ cần biến đổi một chút từ code gốc là được. Chẳng hạn, khi cộng hai số nguyên âm với nhau, các bạn chỉ cần coi như đang cộng hai số nguyên dương rồi thêm dấu trừ vào phía trước,...Giờ thì bắt đầu thôi!

1. Nhập xuất các số nguyên lớn

Đối với cách biểu diễn bằng chuỗi kí tự, chúng ta chỉ cần trực tiếp nhập - xuất các chuỗi kí tự biểu diễn số nguyên là xong. Cài đặt như sau:

void input(bignum_str &number)
{
    cin >> number;
}

void output(bignum_str number)
{
    cout << number;
}

int main()
{
    string a, b;
    input(a);
    input(b);
    
    output(a);
    output(b);
}

Còn đối với cách biểu diễn bằng mảng, ta vẫn nhập chuỗi bằng kiểu string, nhưng sau đó sẽ đưa lần lượt các kí tự vào vector theo chiều ngược lại. Lí do vì sao mình lại đưa các chữ số vào mảng theo chiều ngược lại thì lát nữa ở các giải thuật tính toán các bạn sẽ hiểu rõ hơn.

Ngoài ra, khi thực hiện các phép toán trên hai số nguyên lớn bằng vector, mình sẽ sử dụng thêm một hàm fix() có tác dụng xử lý các giá trị nhớ từ hàng sau ra hàng trước của các số, đồng thời xóa đi các chữ số $0$ vô nghĩa ở kết quả nếu có. Hàm fix sẽ được viết mẫu một lần ở đây, và từ các phép tính sau mình sử dụng luôn chứ không viết lại để tránh chương trình quá dài.

Cài đặt 2: Hàm fix() dùng để xử lý một số nguyên lớn ở kiểu vector: Xóa chữ số $0$ vô nghĩa, dồn các giá trị nhớ từ hàng phía sau ra hàng phía trước. Đối với hai hàm cin và cout, mình sẽ sử dụng nạp chồng các toán tử >> và <<, kèm theo luôn cách sử dụng trong chương trình chính:`

void fix(bignum_vec &number)
{
    /* 
        Thêm chữ số 0 vào cuối vector (thực tế là thêm vào đầu số). Chỗ này để xử lý 
        trường hợp nếu kết quả cuối cùng có thêm một chữ số ở đầu tiên do biến nhớ dư.
    */
    number.push_back(0); 
    
    for (int i = 0; i < number.size() - 1; ++i)
    {
        number[i + 1] += (a[i] / 10); // Hàng trước cộng thêm nhớ của hàng sau.
        number[i] %= 10; // Hàng hiện tại chỉ lưu chữ số cuối cùng của tổng hàng.
        
        if (number[i] < 0) // Nếu hàng hiện tại bị âm thì mượn thêm từ hàng sau.
        {
            number[i] += 10;
            --number[i - 1];
        }
    }
    
    // Xóa chữ số 0 vô nghĩa ở đầu kết quả phép toán.
    while (number.size() > 1 && number.back() == 0)
        number.pop_back();
}

istream &operator >> (istream &cin, bignum_vec &number)
{
    string s;
    cin >> s;

    number.clear();
    for (int i = s.size() - 1; i >= 0; --i)
        number.push_back(s[i] - '0');

    return number, cin;
}

ostream &operator << (ostream &cout, bignum_vec &number)
{
    cout << number.back();

    for (int i = number.size() - 2; i >= 0; --i)
        cout << number[i];

    return cout;
}

int main()
{
    // Khi nhập xuất thì khai báo biến kiểu bignum_vec và dùng trực tiếp lệnh cin, cout.
    bignum_vec a, b;
    cin >> a >> b;
    
    cout << a << endl << b;
}

2. So sánh hai số nguyên lớn

Nguyên tắc so sánh hai số nguyên lớn khi sử dụng chuỗi kí tự như sau:

• Bước $1$: Chuẩn hóa hai chuỗi bằng cách cân bằng độ dài của chúng. Nếu chuỗi nào ngắn hơn thì ta thêm kí tự '0' vào đầu chuỗi đó tới khi độ dài hai chuỗi bằng nhau.
• Bước $2$: So sánh hai chuỗi sử dụng trực tiếp các toán tử >, <, >=, <=. ==, !=. Những toán tử này sẽ so sánh các chuỗi theo mã ASCII của từng cặp kí tự, và "vô tình" thứ tự ASCII lại chính là thứ tự đúng của các số.

Cài đặt 1: Hàm compare(a, b) dưới đây sẽ so sánh hai chuỗi số $a$ và $b,$ nếu $a < b$ thì trả về $-1,$ nếu $a > b$ thì trả về $1,$ còn $a = b$ thì trả về $0$. Ngoài ra, mình viết sẵn hàm equal_length(a, b) để cân bằng độ dài hai chuỗi số $a$ và $b$. Từ các phép tính dưới sẽ sử dụng luôn chứ không viết lại nữa.

void equal_length(bignum_str &a, bignum_str &b)
{
    while (a.size() < b.size())
        a = '0' + a;
    while (b.size() < a.size())
        b = '0' + b;
}
        
int compare(bignum_str a, bignum_str b)
{
    equal_length(a, b);
    
    if (a < b)
        return -1;
    if (a > b)
        return 1;

    return 0;
}

Đối với phương pháp dùng mảng, chúng ta có thể sử dụng nạp chồng toán tử cho các toán tử < và ==. Đối với toán tử <, kết quả sẽ trả về true nếu $a < b,$ ngược lại kết quả trả về false. Tương tự với toán tử ==.

Cài đặt 2: So sánh hai số nguyên lớn $a$ và $b$ sử dụng mảng lưu chữ số:

bool operator < (const bignum_vec &a, const bignum_vec &b)
{
    if (a.size() != b.size())
        return a.size() < b.size();
        
    for (int i = a.size() - 1; i >= 0; --i)
        if (a[i] != b[i])
            return a[i] < b[i];
            
    return false;
}

bool operator == (const bignum_vec &a, const bignum_vec &b)
{
    if (a.size() != b.size())
        return false;
        
    for (int i = a.size() - 1; i >= 0; --i)
        if (a[i] != b[i])
            return false;
            
    return true;
}

3. Phép cộng hai số nguyên lớn

Thuật toán cộng hai số nguyên lớn sử dụng chuỗi kí tự như sau:

• Bước $1$: Cân bằng độ dài hai chuỗi bằng cách thêm kí tự '0' vào đầu chuỗi ngắn hơn.
• Bước $2$: Cộng từng kí tự chữ số của hai chuỗi từ phải qua trái giống như quy tắc đặt tính ở tiểu học, phần nhớ được mang theo sang bên trái ở mỗi lần cộng. Sau mỗi lần cộng ở một hàng, ta thêm kí tự cuối của kết quả cộng hàng đó vào bên trái chuỗi kết quả.
• Bước $3$: Nếu biến nhớ còn khác $0,$ viết thêm kí tự '1' vào bên trái chuỗi kết quả.

Cài đặt 1: Cộng hai chuỗi số nguyên $a$ và $b$ sau đó trả ra tổng:

bignum_str add(bignum_str a, bignum_str b)
{
    equal_length(a, b);
    
    int carry = 0;
    bignum_str res;
    for (int i = a.size() - 1; i >= 0; --i)
    {
        // Cộng hai chữ số cùng hàng và thêm biến nhớ từ hàng bên phải dồn lên.
        int d = (a[i] - '0') + (b[i] - '0') + carry;
        
        carry = d / 10; // Biến nhớ bằng kết quả hàng trước chia 10.
        res = (char)(d % 10 + '0') + res; // Viết chữ số cuối của kết quả.
    }
    
    if (carry)
        res = '1' + res;
        
    return res;
}

Đối với phương pháp mảng chữ số, ta làm hoàn toàn tương tự. Nhưng vì ban đầu các số được đưa vào mảng theo thứ tự ngược lại, nghĩa là chữ số hàng đơn vị của số ban đầu sẽ là phần tử đầu tiên của mảng, nên bước cân bằng độ dài hai mảng là không cần thiết nữa. Điều này giúp tiết kiệm thời gian chạy đáng kể.

Cài đặt 2: Cộng hai số nguyên lớn sử dụng mảng chữ số. Sử dụng nạp chồng toán tử + đối với hai biến kiểu bignum_vec:

bignum_vec operator + (bignum_vec a, bignum_vec b)
{
    // Kết quả phép cộng sẽ gán thẳng vào số a, ta resize trước cho nó.
    a.resize(max(a.size(), b.size()), 0);
    
    for (int i = 0; i < b.size(); ++i)
        a[i] += b[i];
    
    fix(a);
    
    return a;
}

4. Phép trừ hai số nguyên lớn

Để cho đơn giản, chúng ta chỉ xét trường hợp lấy số lớn hơn trừ số nhỏ hơn. Nếu như $a < b$ thì phải hoán đổi vị trí của chúng trước khi trừ, rồi đưa ra kết quả có thêm dấu - ở đằng trước.

Đối với phương pháp chuỗi, thuật toán như sau:

• Bước $1$: Cân bằng độ dài hai chuỗi bằng cách thêm kí tự '0' vào đầu chuỗi ngắn hơn.
• Bước $2$: Lầy từng cặp chữ số trừ đi nhau theo chiều từ phải qua trái giống như đặt tính, nếu kết quả bị âm thì cộng thêm $10$ và nhớ $-1$ sang hàng phía trước.
• Bước $3$: Nếu kết quả cuối cùng còn số $0$ vô nghĩa ở bên trái thì xóa nó đi. Lưu ý chỉ được xóa đến khi kết quả còn $1$ chữ số thì dừng lại.

Cài đặt 1: Trừ hai số lớn kiểu chuỗi:

bignum_str diff(bignum_str a, bignum_str b)
{
    equal_length(a, b);
    
    int d = 0, carry  = 0;
    bignum_str res;
    for (int i = a.size() - 1; i >= 0; --i)
    {
        d = (a[i] - '0') - (a[i] - '0') - carry;
        
        // Tính toán biến nhớ cho hàng này.
        if (d < 0)
        {
            d += 10;
            carry = 1;
        }
        else 
            carry = 0;
        
        // Thêm kí tự cuối cùng của kết quả trừ hàng vào đầu biến hiệu.
        res = (char)(d + '0') + res;
    }
    
    // Xóa chữ số 0 vô nghĩa ở đầu kết quả. Nếu kết quả bằng 0 thì giữ lại một kí tự.
    while (res.size() > 1 && res.front() == '0')
        res.erase(res.begin());
        
    return res;
}

Cài đặt 2: Trừ hai số nguyên lớn cho nhau sử dụng phương pháp mảng lưu chữ số:

bignum_vec operator - (bignum_vec a, bignum_vec b)
{
    for (int i = 0; i < b.size(); ++i)
        a[i] -= b[i];

    fix(a);
    
    return a;
}

Để tiếp tục tìm hiểu về các phép toán nhân - chia đối với số nguyên lớn, mời các bạn sang phần $2$ của bài viết này nhé!