Đường dẫn truy cập

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


Gạch bỏ các bội số của 5

Chân dung Eratosthenes, trong bách khoa toàn thư Thụy Điển Nordisk Familjebok năm 1907.
Chân dung Eratosthenes, trong bách khoa toàn thư Thụy Điển Nordisk Familjebok năm 1907.

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, ....

Liệt kê các số
Liệt kê các số

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, ...

Gạch bỏ các bội số của 2
Gạch bỏ các bội số của 2

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, ...

Gạch bỏ các bội số của 3
Gạch bỏ các bội số của 3

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.....

Gạch bỏ các bội số của 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.

(Còn tiếp 1 kỳ)

  • 16x9 Image

    Vũ Quí Hạo Nhiên

    Vũ Quí Hạo Nhiên là giáo sư Toán đại học cộng đồng Coastline College ở Quận Cam, California, với hơn 10 năm dạy các đại học cộng đồng trong vùng như Santa Ana, Cypress, Santiago Canyon, và Orange Coast College. Ngoài ra, ông cũng từng làm báo Việt ngữ trong hơn 10 năm, với chức vụ Tổng thư ký Toà soạn và Phụ tá chủ bút cũng như cộng tác viên cho nhiều báo, đài phát thanh tại Mỹ và các nước khác.

    Ông là giám đốc chương trình luyện thi SAT cho một trung tâm tại Garden Grove, là giám khảo chấm thi AP Statistics cho College Board / ETS, và là cộng tác viên viết sách giáo khoa Toán cho nhà xuất bản Hawkes Learning.

    Trong blog này Vũ Quí Hạo Nhiên viết về những chuyện ông biết: Toán, giáo dục, lịch sử California. Ông hy vọng độc giả sẽ thảo luận, phê bình, kể cả chê trách, cũng như cho ý kiến đề nghị đề tài.

    Các bài viết của tác giả là blog cá nhân và được đăng tải với sự đồng ý của đài VOA nhưng không phản ánh quan điểm chính thức của chính phủ Hoa Kỳ.

Diễn đàn Facebook

VOA có ứng dụng mới

Xem tin tức VOA trực tiếp trên điện thoại và máy tính bảng! Ứng dụng tin tức miễn phí của VOA Tiếng Việt liên tục cập nhật thông tin trung thực, đa chiều về tình hình Việt Nam và thế giới; đặc biệt có thêm chức năng vượt tường lửa, phá chặn website.

Hãy tải ngay ứng dụng VOA Tiếng Việt trên iTunes StoreGoogle Play!

Lưu ý: Ứng dụng cũ của VOA đã bị xóa vào ngày 15/1/2020.

XS
SM
MD
LG