Ông già Erastosthenes ngầu cỡ nào (kỳ 1)

Gọi Erastosthenes là ông già vì ông thọ 82 tuổi và chân dung người ta thường vẽ là một người đầu hói láng o và râu rậm rạp, chứ thực ra lúc sinh thời ông thành tài rất sớm và đạt chức vụ cao nhất là Trưởng Quản thủ Thư viện Alexandria năm ông 35 tuổi.

Erastosthenes sinh năm 279 tr.C.N. tại Cyrene, Bắc Phi Châu, khi đó là một phần của Hy Lạp và hiện nay thuộc Libya. Ông là một nhà bác học theo đúng nghĩa là ông giỏi nhiều ngành, trong đó có Toán.

Ông nổi tiếng từ trẻ, viết trường thi, viết sách sử, nghiên cứu địa lý, nên năm ông 30 tuổi vị Pharaoh, vua Ai Cập, Ptolemy III Euergetes, mời ông về làm Quản thủ Thư viện Alexandria. Năm năm sau, ông lên Trưởng Quản thủ Thư viện, chức vụ ông sẽ giữ suốt đời.

Thư viện Alexandria là nơi thu giữ mọi kiến thức lịch sử văn chương khoa học của thế giới cổ đại. Dưới sự điều khiển của Erastosthenes, kho tàng tri thức ở Alexandria lại càng rộng lớn hơn. Cho tới ngày hôm nay, phim ảnh, văn chương, nghệ thuật vẫn dùng Thư viện Alexandria làm biểu tượng của sự tổng hợp kiến thức cả thế giới.

Làm Trưởng Quản thủ Thư viện Alexandria, vì vậy, giống với chức vụ Bộ trưởng Giáo dục hay Viện trưởng một Viện Đại học thời nay, hơn là chỉ có công việc thư viện. Erastosthenes cũng được giao nhiệm vụ dạy dỗ các hoàng tử, trong đó có vị Pharaoh Ptolemy IV Philopator tương lai. Nếu trong triều đình Việt Nam thì công việc của ông tương đương chức Thái Phó.

Ông có nhiều thành tựu về Toán. Trong số học, ông để lại một phương pháp mang tên ông, là “sieve of Eratosthenes.” Trong bài này tôi sẽ nói về sieve of Eratosthenes, là một thành tựu đã rất “ngầu” rồi. Bài thứ nhì tôi sẽ nói về thành tựu khác còn… ngầu hơn.

“Sieve” trong tiếng Anh có nghĩ là cái phin, cái vá, cái rây, là cái đồ để lọc. Cái vá để trụng bánh phở, giữ bánh phở lại và nước chảy ra, là một cái sieve. Cái rây để lọc bột, cho bột mịn qua được và giữ lại phần bị đóng cục để bỏ đi, cũng là một cái sieve.

Sieve of Erastothenes dùng để lọc các số không phải nguyên tố và chừa lại số nguyên tố. Ở Việt Nam gọi là sàng Erastothenes. Sieve này xài rất dễ.

Số nguyên tố là một số mà chỉ chia đúng cho chính nó và cho 1 mà thôi. Thí dụ, 5 là số nguyên tố vì 5 chỉ chia đúng cho 5 và 1. Nhưng 15 không phải số nguyên tố vì 15 chia đúng cho 15 và cho 1, nhưng cũng chia đúng cho 3 và cho 5 nữa. Số 1 theo thông lệ không kể là số nguyên tố; vậy các số nguyên tố đầu tiên là: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ….

Số nguyên tố xài được vào việc gì? Nhiều ứng dụng lắm, nhưng một ứng dụng gần với mọi người nhất là password trong điện thoại, máy tính, trang web các loại. Không có trang web nào chứa password của ai hết. Chính vì vậy mà khi quên password thì chỉ có thể lập password mới chứ không ai cho mình lại password cũ được. Các trang web chỉ chứa một dạng mã hoá của password thôi. Và password được mã hoá bằng cách sử dụng các số nguyên tố cực kỳ lớn, lớn tới mức người ta hy vọng là các máy điện toán mạnh nhất cũng không bẻ khoá nổi.

Sàng Erastothenes lọc ra số nguyên tố bằng cách này. Viết hết các số từ 1 tới bao nhiêu đó, thí dụ 1000.

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, ….

Số 1 không phải số nguyên tố, không kể.

Vậy: (*) số đầu tiên sau đó chưa gạch bỏ là số nguyên tố. Đó là số 2.

Gạch bỏ hết các bội số của 2. Tức là gạch bỏ: 4, 6, 8, 10, 12, …

Trở lại với (*) Số đầu tiên sau đó chưa gạch bỏ là số nguyên tố.

Đó là số 3.

Gạch bỏ hết các bội số của 3, tức là gạch bỏ: 6, 9, 12, 15, 18, …

Rồi lại trở lại và làm tiếp:

(*) Số đầu tiên sau đó chưa gạch bỏ là số nguyên tố. Đó là số 5. Gạch bỏ các bội số của 5…..

Làm cho tới chừng nào hết số để gạch bỏ thì các số còn lại là toàn bộ các số nguyên tố từ 1 tới 1000. Vì số nào chia đều được cho số khác là đã bị gạch bỏ mất rồi.

Cái sàng này có gì hay?

Trước hết, hãy xem lại cách tôi miêu tả ở trên. Sàng này chỉ lập lại có 2 bước chỗ đánh dấu (*). Cho nên, trong phương diện thảo chương cho máy điện toán, sàng Erastosthenes có algorithm (giải thuật) đơn giản, viết vài hàng là xong. Tuy đơn giản nhưng rất mạnh và có thể dễ dàng chạy với những con số thật lớn như hàng triệu, hàng tỷ. Thời sơ khai của máy điện toán, nhiều người dùng thuật toán sàng Erastosthenes để đánh giá tốc độ và sức mạnh của máy điện toán cá nhân.

Thứ nhì, giải thuật này có thể cho chạy song song. Máy điện toán không cần chờ cho xong bước này mới phải làm tiếp tới bước sau. Tưởng tượng ông Erastosthenes có một lô đệ tử, mỗi đệ tử phụ trách một con số. Trong khi một đệ tử đang gạch bỏ các bội số của 2, thì đệ tử khác có thể bắt đầu gạch bỏ bội số của 3 mà không cần chờ. Đệ tử khác gạch bỏ bội số của 5. Ai làm nhanh thì cứ việc qua mặt người khác, ai làm chậm thì cứ việc để cho người khác qua mặt.

Có nghĩa là sàng Erastosthenes rất thích hợp cho parallel computing, tính toán song song, một phương pháp tính toán hiện đại trong ngành điện toán, chỉ phổ biến từ thập niên 1990, 2000 trở về sau này. Và thật vậy, nhiều lớp dạy parallel computing bằng viết chương trình chạy sieve of Erastosthenes.

Cho nên điểm ngầu thứ nhất của Erastosthenes là 2200 năm trước đây đã nghiên cứu về một đề tài đang được ứng dụng trong các trang web, điện thoại thông minh, và chế ra một thuật toán mà cho tới hiện nay vẫn giúp hiện đại hoá máy tính.

Nội nhiêu đó thôi đủ thấy Erastosthenes ngầu thế nào rồi. Nhưng trong bài tới tôi sẽ chỉ ra độ ngầu của Erastosthenes còn hơn thế này nữa.