Tính giai thừa số lớn (Big Factorial)

Tính giai thừa số lớn (Big Factorial)
(Ngày cập nhật cuối: 18/05/2009)
Chủ đề bài báo: Tính giai thừa số lớn, C/C++, thuật toán.
Bài toán tính giai thừa là một trong các bài toán cơ bản khi học về lập trình (vòng lặp và đệ qui). Về cơ bản tính giai thừa (Factorial) là một bài toán tính tích n! = 1*2*…*n. Đối với các giá trị n nhỏ (n ≤ 20) thì giá trị của n! vẫn nằm trong vùng biểu diễn của số nguyên, tuy nhiên đối với số n lớn (khoảng vài trăm, vài nghìn) thì việc tính n! trở nên khó khăn vì giá trị của n! vượt quá khoảng biểu diễn của kiểu số nguyên lớn nhất. Trong bài báo này tôi sẽ giới thiệu với các bạn một thuật toán cơ bản dùng để tính giai thừa của một số nguyên lớn (n ≤ 100000) trên ngôn ngữ C/C++.
1. Giới hạn của kiểu số nguyên trong C/C++Trước khi đi vào các thuật toán, tôi muốn giới thiệu với các bạn độc giả giới hạn biểu diễn của các kiểu số nguyên trong C/C++. Các bạn hãy xem ví dụ C++ sau:
// file intlimit.cpp
#include
#include
#include
using namespace std;
int main()
{
cout << "CHAR_MIN = " << CHAR_MIN << endl;
cout << "CHAR_MAX = " << CHAR_MAX << endl;
cout << "UCHAR_MAX = " << UCHAR_MAX << endl;
cout << "SHRT_MIN = " << SHRT_MIN << endl;
cout << "SHRT_MAX = " << SHRT_MAX << endl;
cout << "USHRT_MAX = " << USHRT_MAX << endl;
cout << "INT_MIN = " << INT_MIN << endl;
cout << "INT_MAX = " << INT_MAX << endl;
cout << "UINT_MAX = " << UINT_MAX << endl;
cout << "LONG_MIN = " << LONG_MIN << endl;
cout << "LONG_MAX = " << LONG_MAX << endl;
cout << "ULONG_MAX = " << ULONG_MAX << endl;
cout << "LLONG_MIN = " << LLONG_MIN << endl;
cout << "LLONG_MAX = " << LLONG_MAX << endl;
cout << "ULLONG_MAX = " << ULLONG_MAX << endl;
system("pause");
return 0;
}
Kết quả chạy chương trình trên là:
CHAR_MIN = -128
CHAR_MAX = 127
UCHAR_MAX = 255
SHRT_MIN = -32768
SHRT_MAX = 32767
USHRT_MAX = 65535
INT_MIN = -2147483648
INT_MAX = 2147483647
UINT_MAX = 4294967295
LONG_MIN = -2147483648
LONG_MAX = 2147483647
ULONG_MAX = 4294967295
LLONG_MIN = -9223372036854775808
LLONG_MAX = 9223372036854775807
ULLONG_MAX = 18446744073709551615
Như vậy chúng ta thấy rằng kiểu số nguyên lớn nhất là long long (có dấu), còn unsigned long long là kiểu số nguyên không có dấu lớn nhất (có giá trị dương lớn nhất gấp đôi giá trị dương lớn nhất của kiểu long long).
2. Tính giai thừa với kiểu dữ liệu số nguyên lớn nhất.
Bây giờ chúng ta đã biết kiểu số nguyên lớn nhất là long long, chúng ta sẽ sử dụng kiểu số nguyên này để tính giai thừa của một số nguyên bằng chương trình sau:
// file bigfac0.cpp
#include
using namespace std;
int main()
{
long long kq = 1ll;
unsigned long n;
unsigned long i = 1ul;
cout <> n;
for(i=1ul;i<=n;++i)
kq = kq * i;
cout << kq;
system("pause");
return 0;
}
Theo kết quả thử nghiệm chạy chương trình trên chúng ta có thể tính tới giá trị 20! (bằng 2432902008176640000), một con số khá khiêm tốn.
3. Thuật toán tính giai thừa số lớn
Để có thể tính được giai thừa của các số lớn, chúng ta bắt buộc phải thay đổi cách biểu diễn kết quả của việc tính giai thừa, đó là một số nguyên lớn. Chúng ta sẽ sử dụng một mảng các số nguyên để biểu diễn các chữ số của số nguyên lớn n!. Tuy nhiên một số nguyên có thể biểu diễn không chỉ 1 chữ số của n!, nó có thể biểu diễn 2, 3, 4, .. chữ số của n!. Vậy chúng ta nên chọn một phần tử của mảng kết quả sẽ biểu diễn bao nhiêu chữ số. Nói một cách dễ hiểu hơn giả sử với n = 20, ta có n! = 2432902008176640000, nếu ta sử dụng một mảng số nguyên biểu diễn các chữ số của n!, sẽ có các khả năng sau:
Một phần tử mảng biểu diễn
1 chữ số a[0] = 0, a[1] = 0, a[2] = 0, a[3] = 0, a[4] = 4, …, a[18] = 2
2 chữ số a[0] = 0, a[1] = 0, a[2] = 64, a[3] = 76, …, a[9] = 2
3 chữ số a[0] = 0, a[1] = 640, a[2] = 176, …, a[6] = 2
4 chữ số a[0] = 0, a[1] = 7664, a[2] = 81, …, a[4] = 243
…. ….
Vậy chúng ta sẽ chọn các biểu diễn nào, trước hết để an toàn chúng ta sử dụng một phần tử mảng để biểu diễn 4 chữ số của n!.
Với các biểu diễn này, chúng ta sẽ sử dụng phương pháp nhân đa thức để tính n!, kết quả n! là một đa thức với các hệ số nguyên, mỗi hệ số biểu diễn 4 chữ số. Thuật toán có một vòng lặp chính, mỗi lần lặp ta sẽ lấy giá trị của biến chạy i nhân với đa thức kết quả. Ở đây cần chú ý các điểm sau:
+ Do mỗi phần tử mảng biểu diễn 4 chữ số của n! nên khi in ra ta cần thêm các số 0 vào phần đầu của số nếu như phần tử mảng tương ứng không có đủ 4 chữ số (xét theo giá trị thực của nó), trừ phần tử mảng cuối cùng. Ví dụ nếu a[j] = 0 (với 1 vị trí j nào đó) thì sẽ in ra 0000, nếu a[j] = 23 thì sẽ in ra 0023.
+ Ta sẽ thực hiện nhân giá trị i với giá trị hiện tại của đa thức kết quả bằng thuật toán nhân tay:
- Lấy i nhân với giá trị a[j] (j là vị trí đang xét của đa thức) và cộng với kết quả dư từ phép nhân trước (i nhân với a[j-1]), lưu vào biến sl.
- Chia sl cho 10000 (vì mỗi hệ số của đa thức biểu diễn 4 chữ số), phần dư và gán cho a[j], kết quả của phép chia gán cho biến dư sn.
- Khởi đầu mỗi lần lặp (nhân i với đa thức kết quả) biến sn được gán bằng 0.
+ Ban đầu số chữ số của n! được xem là 1 (biến so), sau mỗi lần lặp, nếu giá trị của sn còn lớn hơn 0 thì phải tăng biến so lên 1 đơn vị (để biểu diễn giá trị dư sn).
Sau đây là phần chương trình cài đặt thuật toán:
// file bigfacvs.cpp
#include
#include
#include
#define MAX 100000
using namespace std;
int main()
{
int i,j,n,so;
unsigned long sl;
unsigned sn;
int a[MAX];
clock_t t1, t2;
cout << "Chuong trinh tinh giai thua so lon\n";
cout <> n;
a[0]=1;
t1=clock();
sn=0;
so = 1;
for(i=1;i<=n;++i)
{
sn = 0l;
for(j=0;j<so;++j)
{
sl=i*a[j]+sn;
a[j]=sl%10000;
sn=sl/10000;
}
if(sn)
a[so++] = sn;
}
t1=clock()-t1;
i=so-1;
t2 = clock();
cout <=0;–j)
cout << setw(4) << setfill('0') << a[j];
t2 = clock() – t2;
cout << "\nThoi gian tinh toan:" << (float)t1/CLK_TCK;
cout << "\nThoi gian hien thi:" << (float)t2/CLK_TCK;
system("pause");
return 0;
}
Một số kết quả tính toán (trên bộ công cụ Visual Studio 2008 SP1):
Giá trị n Thời gian tính toán (giây) Thời gian hiển thị (giây)
1000 0 0.04
3000 0.03 0.15
5000 0.06 0.28
10000 0.29 0.59
30000 2.62 1.92
50000 7.5 3.26
80000 21 5.64
100000 33 7

Các bạn có thể thay đổi thuật toán trên để mỗi phần tử của mảng a biểu diễn 5, 6 chữ số của n!, tuy nhiên theo thực nghiệm tôi thấy rằng nó không làm thuật toán nhanh hơn, và cũng cần chú ý là khi đó giá trị của biến sn cực đại sẽ là 106 * n và với n = 100000 thì sẽ vượt qúa miền biểu diễn của kiểu số nguyên int, nên kết quả có thể sai. Đối với mảng a[] bạn có thể dùng kiểu unsigned, hiệu năng của thuật toán hầu như không thay đổi. Tuy nhiên đối với các giá trị n nhỏ (n < 20000) bạn có thể dùng kiểu long thay cho unsigned long đối với biến sl và thuật toán sẽ chậm hơn so với kiểu unsigned long.
Thêm một chú ý nhỏ nữa là nếu bạn dịch chương trình trên với DevCpp thì thời gian thực hiện thuật toán có thể sẽ chậm hơn một chút. Bảng kết quả trên chạy trên hệ thống của tôi có cấu hình: CPU Centrino 1.5 Ghz, Cache 2 Mb, Ram 1 GB, HDD 120 Gb Samsung ATA 5400 rpm.
Cuối cùng, thuật toán tôi trình bày trong bài báo này không phải là thuật toán nhanh nhất, hiệu quả nhất để tính giai thừa của một số nguyên lớn, nó là một thuật toán cơ bản. Các thuật toán cao cấp hơn, có thể tính được với giá trị của n rất lớn trong thời gian ngắn xin hẹn các bạn trong một bài viết khác.
Mặc dù đã hết sức thận trọng và xem xét kỹ lưỡng các ví dụ đưa ra trong bài viết, tuy vậy vẫn có thể không tránh khỏi các sai sót, rất mong nhận được sự đóng góp ý kiến của các bạn độc giả. Mọi góp ý, thắc mắc xin gửi về địa chỉ email: tuannhtn@yahoo.com.

Hải Phòng, ngày 18, tháng 05, năm 2009

Nguyễn Hữu Tuân

6 Responses to “Tính giai thừa số lớn (Big Factorial)”

  1. bekhoebedep Says:

    Lâu rồi em mới thấy thầy viết bài, vẫn là CTDL & GT. Có người từng nói “Tư duy mới về những vấn đề cũ”, chắc thầy cũng thích câu đó :D Bài số nguyên lớn dùng danh sách liên kết có biểu diễn được vô hạn các số được không thầy?
    Hôm nay, em qua trường thấy lại đỗ môn LTHĐT, mừng phát khóc. Lần này chắc là qua thật phải không thầy ^^!

  2. 4fire Says:

    Chúc mừng em, nói chung là tôi thấy cái gì thú vị và có thể viết được thì viết thôi. Các vĩ nhân thường bị đời hắt hủi. Lần trước tôi nhớ là đã nói với em là em đỗ mà. Phải có lòng tin chứ.

  3. nhlionheart Says:

    Thầy cho em hỏi muốn vẽ đồ họa bằng c++ thì nên dùng phần mềm nào và tạo 1 project mới như thế nào .
    Em cảm ơn thầy

  4. 4fire Says:

    Em nên dùng Visual Studio với ngôn ngữ C++ hoặc C#. Về thư viện thì còn tùy mục đích của em.
    Nếu chỉ để minh họa các thuật toán đồ họa thì GDI (C/C++) hoặc GDI+(C#) là đủ, còn nếu muốn cao cấp hơn thì dùng Open GL hoặc DirectX. Còn nếu là để xử lý ảnh thì còn tùy mục đích: nhận dạng số, chữ hay …

  5. ánh dương Says:

    Thầy chỉ cho em cách cài đặt và sử dụng thư viện thư viện Boost trong C++ với. Em muốn học về Multi Thread. Em cảm ơn thầy

    • 4fire Says:

      Để dùng boost (trên Windows và với VS 2010, khuyến khích dùng VS 2012 update 4 hoặc VS 2013 update 2) thì em phải tự build boost, khá mất thời gian. Nhưng điều hay là các chương trình có dùng boost sẽ không cần phải copy đi kèm với thư viện này mà vẫn chạy tốt vì nó được biên dịch với output là các static libraries. Đầu tiên em cần add hai đường dẫn sau vào biến môi trường PATH của Windows (đây là đối với VS 2012, có thể em dùng các bản VS khác thì sẽ khác):
      C:\Program Files\Microsoft Visual Studio 11.0\VC\bin
      C:\Program Files\Microsoft Visual Studio 11.0\Common7\IDE
      Sau đó download boost và và unzip thành thư mục D:\boost, sau đó vào command line, chạy lệnh bootstrap để cấu hình, chạy lệnh .\b2 để dịch boost bằng VS, chờ một thời gian là sẽ xong. Để cấu hình VS sử dụng boost cần thêm đường dẫn D:\boost\stage\lib vào library directory của VS, D:\boost vào include directory của VS. Và thế là xong, nói chung cũng khá đơn giản.
      Về lập trình đa luồng, có một vài lựa chọn sau:
      + boost::thread, theo đánh giá của tôi là hơi chậm nhưng đa nền tảng.
      + pthread, tốc độ tốt nhưng khá phức tạp, đa nền tảng nhưng tài liệu hỗ trợ trên Windows hơi kém.
      + windows thread, tốc độ nhanh nhất và chỉ trên các hệ thống chạy Windows, đơn giản hơn pthread.
      + C++11 thread, đơn giản nhất, tốc độ tốt. Với ba lựa chọn ở trên, mỗi khi muốn thực hiện một tác vụ đa luồng, em cần viết chương trình (các hàm, các lớp) theo đúng kiểu framework tương ứng còn với C++11 thread thì điều này là native nên là dễ nhất cho ai mới bắt đầu như em, tất nhiên là em phải hiểu hết C++ đã.
      Lựa chọn lập trình đa luồng là tất yếu vì dữ liệu cần xử lý ngày càng lớn và thật là bực mình nếu máy tính của em có 4 CPU cores mà em chỉ viết được chương trình chạy với 1 core.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: