CÓ THỂ BẠN CHƯA BIẾT

Các bạn đọc thân mến, các bạn thường được thầy cô kể về câu chuyện như một huyền thoại về cậu bé Gauss. Bé Gauss khi đó đã có thể tính tổng từ 1 tới 100 bằng công thức 100 * 101 / 2 = 5050. Thế nhưng, còn có rất nhiều chuyện thú vị trước thời điểm này.

Chuyện là, hồi đó quốc vương nước Phổ (nước Đức lúc bấy giờ) mang mộng làm bá chủ thiên hạ. Đồng thời, ông vua này cũng rất mê tín. Ông ta tin rằng, với sự giúp đỡ của thần linh, giấc mơ bá chủ thiên hạ của mình sẽ sớm được hoàn thành.

Để cầu sự giúp đỡ của thần linh, ông ta phải làm một đạo tràng. Nhưng để làm được đạo tràng này, các nhà chiêm tinh nói rằng phải tính toán được chính xác tổng các số từ 1 tới 1 tỷ. Tại sao lại vậy thì người viết này bài không biết, đây là bí mật quốc gia hồi bấy giờ, nếu ai tiết lộ ra bên ngoài thì sẽ bị xử tử hình. Có thể con số này mang một ý nghĩa tâm linh đặc biệt.

Mong muốn nhanh chóng làm được việc này, ông ta đã huy động một đội ngũ hùng hậu các nhà Tính học (người có khả năng tính nhẩm nhanh) của đất nước dưới sự chỉ huy của ngài To Son – một nhà Tính học nổi tiếng thời bấy giờ. Phần thưởng sau khi hoàn thành công việc này là nhà vua sẽ gả công chúa độc nhất của mình cho ngài To Son, các nhà Tính học khác thì được hưởng cuộc sống vinh hoa phú quý đến trọn đời. Các bạn cũng nên biết rằng, công chúa của nhà vua là độc nhất, nghĩa là ai lấy được công chúa sẽ trở thành đức vua mới sau khi nhà vua băng hà.

Để kích lệ tinh thần làm việc của các nhà Tính học, nhà vua cho phép họ được nhìn công chúa diệu của mình. Nàng công chúa này có một sắc đẹp kiều diễn, da nàng trắng như tuyết, môi đỏ như son, làm mê đắm bất cứ chàng trai nào. Ngài To Son nhận công việc này cũng một phần vì lý do đó.

Công việc tính toán tưởng chừng như đơn giản nhưng sự thật vô cùng vất vả bởi 1 tỷ là con số khổng lồ. Với dự tính ban đầu, ngài To Son cho rằng có thể kéo dài mất 200 năm.

Ngài nghĩ cần phải tìm một phương pháp hiệu quả hơn so với việc phải tính tổng tuần tự từng bước một. Tuy nhiên, do nhà vua rất nóng lòng, ngài To Son đã chia công việc tính toán khổng lồ này cho 10 nhóm Tính học. Mỗi nhóm Tính học thực hiện tính toán trên một dãy gồm 10^8 số liên tiếp nhau. Công việc cuối cùng là ngài To Son sẽ tổng hợp và tính tổng từ 10 kết quả cuối cùng này. Còn các nhà Tính học khác thì tập trung suy nghĩ một phương pháp mới, hiệu quả hơn.

Đang thả mình vào dòng suy nghĩ, ngài chợt nhìn thấy một vật lấp lánh trên bầu trời. Thoắt một cái, một con chim sắt to lớn đã ở bên cạnh ngài. Một cánh cửa từ từ mở ra, một người tự xưng là Tô Sơn đến từ thế kỉ XXI đến bắt chuyện với ngài với mong muốn tìm hiểu về lịch sử của loài người. Họ càng nói, càng thân (có lẽ tên họ có điểm gì đó giống nhau). Và ngài đã kể cho Tô Sơn nghe về phiền muộn của ngài.

Tô Sơn vốn là một sinh viên dốt tính toán nhưng lại ham mê máy tính. Anh bảo ngài đừng lo: “Tôi có 10 processors, mỗi processor của tôi có thể tính toán được công việc của 1 nhóm trong vòng thời gian chỉ có 0.5 giây. Như vậy, 10 processors của tôi sẽ tính giúp công việc của 10 nhóm của ngài. Processor đầu tiên ngoài nhiệm vụ tính công việc của 1 nhóm, sẽ có nhiệm vụ tổng hợp các kết quả từ 10 processors. Thời gian tổng hợp 10 kết quả từ 10 processors từ processor đầu tiên này diễn ra vô cùng ngắn. Đặc biệt, các processors này có thể làm việc đồng thời cùng một lúc nên chỉ cần sau 0.5 giây ngài sẽ nhận được kết quả (chứ không phải là 10*0.5 = 5 giây như thông thường)”.

Rồi anh lặng lẽ viết một đoạn chương trình, thời gian viết đoạn chương trình này khoảng 30 phút. Bởi anh suy nghĩ viết một chương trình tổng quát để tính tổng từ 1 tới n với k processors.

Anh phân tích:

Có một cách phân chia công việc tính tổng cho k processors là: k-1 processors đầu tính tổng [n/k] số liên tiếp. Processors cuối cùng (thứ k) tính tổng các số liên tiếp còn lại: Tức: n – (k-1) * [n/k]

Nhưng anh chợt nghĩ:

Vậy: Nếu n = 7, k = 4 thì sao:

Công việc tính toán cho từng processor sẽ lần lượt là:

1, 2, 3, 4

1, 1, 1, 4

Như vậy, processor thứ 4 thực hiện tính tổng 4 số liên tiếp, trong khi đó 3 processors còn lại chỉ tính 1 số duy nhất. Như vậy: nếu thực hiện tính toán thì thời gian anh phải chờ đợi sẽ là max(O(1), O(1), O(1), O(4) = O(4)). Anh nghĩ, cách chia này không được lợi về mặt thời gian. Vì vậy, anh nghĩ ra một giải pháp tốt hơn.

Anh nhận thấy: 7 % 4 = 3. Vậy nếu cho chia cho 3 processors đầu mỗi processors [7/4] + 1 = 2 processors, các processors còn lại là [7/4] = 1 processor thì công việc tính toán cho từng processor sẽ lần lượt là:

1, 2, 3, 4

2, 2, 2, 1

Vậy thời gian chờ đợi sẽ là max(O(2), O(2), O(2), O(1)) = O(2). Rõ ràng tốt hơn cách ban đầu.

Chương trình anh viết như sau:




Do các processors được thực hiện đồng thời nên Độ phức tạp về thời gian là T(n) = max(O(k)*O(1), O([n/k] + 1), O([n/k])) = max(O(k), O([n/k] + 1), O([n/k])) = max(O(k), O(n/k))

Do k là số processors, nó luôn hữu hạn chứ không phải là tài nguyên vô hạn nên T(n) = O(n/k)

(Một số giáo trình về lập trình/xử lý song song giả sử là k = +∞ nên Độ phức tạp về thời gian mà họ đưa ra là O(log(n)) cho bài toán tính tổng ở trên, nhưng k = +∞ là con số không bao giờ đạt được, nó chỉ là con số mơ ước trong lý thuyết)

Toàn bộ chương trình anh viết sử dụng thư viện MPI dùng cho việc tính toán song song trên ngôn ngữ C++. (Cái hay của thư viện MPI là làm cho người lập trình khi viết code cảm tưởng có vô số processors – như vậy việc lập trình sẽ trở nên thoải mái và dễ dàng hơn rất nhiều, nhưng để tính chính xác thời gian khi chạy chương trình thì chúng ta phải hiểu là bao giờ cũng chỉ có giới hạn số processors mà thôi).

Ngài To Son cảm ơn sự giúp đỡ tận tình của thế kỉ XXI. Ngài nhanh chóng thông báo kết quả với nhà vua và sánh duyên cùng công chúa. Mười năm sau, đức vua lâm bệnh nặng qua đời mang theo giấc mộng bá chủ xuống dưới hoàng tuyền, ngài To Son trở thành quốc vương mới của nước Phổ, thúc đẩy nền hòa bình thịnh trị.

Một hôm, trong chuyến thị sát tại một trường tiểu học, tình cờ ngài ghé ngang qua lớp của Gauss, và ngài đã tìm được thêm một lời giải thú vị. Ngài đã tặng danh hiệu “Thần đồng đất Phổ” cho Gauss.

Từ cách làm của Gauss, ngài cũng phát triển thêm một phương pháp để phương pháp của Gauss hiệu quả hơn cho việc chứng minh trường hợp tổng quát.

Để ghi nhớ những cống hiến không mệt mỏi, ngay từ khi còn sống, tên của ngài đã được các nhà Tính học đặt cho một miệng núi lửa trên phần trông thấy của Mặt trăng.

Bài viết liên quan: Tính tổng từ 1 tới numnodes*10^8: Click here

Toàn văn bài viết: Click here

Tính tổng từ 1 tới n, với n = 10^9 thời gian chạy chương trình là 0.38 giây: Click here

One Response to “CÓ THỂ BẠN CHƯA BIẾT”

  1. hung anh Says:

    Văn thơ lai láng quá đi :v .ltv kiêm nhà văn rất phù hợp cho chú đấy.


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

%d bloggers like this: