Ứng dụng máy tính à? Ai mà chẳng làm được đúng không?
(chadnauseam.com)"Ứng dụng máy tính à? Ai mà chẳng làm được" → thực ra không đúng
- Máy tính phải hiển thị chính xác kết quả của các biểu thức toán học, và việc này khó hơn nhiều so với tưởng tượng
- Trên máy tính của iOS,
(10^100) + 1 − (10^100)bị tính sai thành0 - Nhưng Android lại cho ra kết quả đúng là 1, và cách họ làm điều đó thực sự khó tin
Google và Hans-J. Boehm
- Google đã tuyển dụng lập trình viên nổi tiếng Hans-J. Boehm
- Boehm là chuyên gia đã định nghĩa ngữ nghĩa của biến dùng chung trong C++
- Nhưng nhiệm vụ được giao cho ông lại là phát triển ứng dụng máy tính, một việc ngoài dự đoán
Vấn đề của số dấu phẩy động
- Số dấu phẩy động không thể biểu diễn chính xác các giá trị như
0.3hay10^100 - Nghĩa là máy tính dựa trên số dấu phẩy động không thể đáng tin cậy
- Để tính toán chính xác, cần một cách tiếp cận khác
Giải pháp dùng Bignum
- Bài toán tính số nguyên có thể được giải bằng Bignum (số nguyên không giới hạn)
- Bignum là kiểu số nguyên có thể mở rộng động theo dung lượng bộ nhớ
- Bài toán
(10^100) + 1 - (10^100)có thể được giải bằng Bignum - Nhưng phép toán với phân số vẫn chưa được giải quyết
Phân số và số đại số
- Phân số (như giá trị
3/4) có thể được xử lý bằng cách dùng Bignum để lưu tử số và mẫu số - Nhưng không thể biểu diễn các số vô tỉ như số pi (π) hay căn bậc hai của 2 (√2)
- Boehm đã thử cách biểu diễn dựa trên đa thức
- Ví dụ:
√2có thể được biểu diễn bằng phương trìnhx² - 2 = 0 - Nhưng π thì ngay cả cách này cũng không thể biểu diễn được
- Ví dụ:
Số thực kiến tạo (Constructive Real Numbers)
- Boehm đã nghiên cứu khái niệm "phép toán số thực đệ quy (RRA)"
- Khi người dùng nhập độ chính xác mong muốn, hệ thống sẽ tính giá trị trong phạm vi độ chính xác đó
- Ví dụ: nếu biểu diễn π trong sai số
0.01thì sẽ trả về3.14 - Nhưng cách này khiến việc so sánh chính xác trở nên khó khăn
Vấn đề biểu diễn số 0 chính xác
- Theo cách RRA,
1 - 1có thể được biểu diễn không phải là0mà là0.0000000001 - Điều này gây vấn đề về mặt trải nghiệm người dùng (UX)
- Boehm bắt đầu hợp tác với các nhà nghiên cứu khác để tìm lời giải
Thuật toán Richardson-Fitch
- Năm 1994, Dan Richardson và John Fitch đã giải quyết bài toán so sánh số trong một số phép toán nhất định
- Nhưng thuật toán này quá chậm nên trên thực tế không thể dùng được
- Ví dụ, để xác định
1 ≠ 1 - e^(-e^1000)cần số phép tính còn nhiều hơn cả số nguyên tử trong vũ trụ
Kết hợp RRA và phép toán hữu tỉ
- Boehm nảy ra ý tưởng kết hợp ưu điểm của RRA với phép toán trên số hữu tỉ
- Với các phép toán đơn giản (ví dụ:
6 × 9hoặc8 / 3) thì dùng phép toán hữu tỉ - Chỉ khi có số vô tỉ mới dùng RRA
- Kết quả là biểu diễn số dưới dạng hữu tỉ × số thực
Biểu diễn ký hiệu (Symbolic Representation)
- Các số đặc biệt như π, √2 được dùng biểu diễn ký hiệu thay vì RRA
- Ví dụ: π được lưu dưới dạng ký hiệu "π" và chỉ chuyển thành số khi cần
- Không chỉ bốn phép toán cơ bản, mà cả các hàm lượng giác (sin, cos, tan), log và hàm mũ cũng tận dụng biểu diễn ký hiệu
Giải pháp cuối cùng
- Mọi số đều được lưu dưới dạng hữu tỉ × số thực (biểu diễn ký hiệu hoặc RRA)
- Khi có thể thì dùng phép toán hữu tỉ để giữ độ chính xác
- Tận dụng biểu diễn ký hiệu tối đa để giảm thiểu phép toán RRA
- Kết quả là hoàn thiện được một hệ thống máy tính lý tưởng, cân bằng giữa tốc độ và độ chính xác
Kết luận
- Ứng dụng máy tính Android do Boehm và nhóm của ông tạo ra không phải là một chương trình đơn giản
- Nó áp dụng các thuật toán nhanh và hiệu quả mà vẫn cho kết quả chính xác
- Đây không phải "chỉ là một ứng dụng máy tính", mà là một hệ thống tinh vi về mặt toán học
"Lần tới khi dùng máy tính Android, hãy nhớ đến nỗ lực này!"
12 bình luận
Ngoài lề một chút, khá thú vị là AI neo đã dịch thành “thế chứ”. Nguyên văn là “Anyone could make that” nên không có sắc thái đùa cợt như vậy đâu haha, nhưng lại hợp cực kỳ.
Hồi còn là sinh viên đại học, tôi từng có một môn học mà phải tự tay hàn một bo mạch 8086, nối bàn phím số và LCD chữ vào, rồi dùng hợp ngữ 8086 để làm cả một chiếc máy tính bỏ túi chỉ thực hiện bốn phép tính cơ bản.
Tôi đã làm bo mạch, nối cả bàn phím lẫn LCD và cho nó chạy được, nhưng lại không làm được máy tính.
Lúc đó tôi nghĩ mình không có năng khiếu về phần mềm nên đã đi làm kỹ sư phần cứng, nhưng rồi chẳng hiểu sao bây giờ lại đang phát triển phần mềm.
Máy tính thật sự rất khó.
Phải là “geojanh-a” chứ không phải “geojana”. 😃
Muốn xử lý điều chỉnh số dấu phẩy động thì cũng đau đầu lắm đấy? hahaha
Nhắc đến ứng dụng máy tính, tôi lại nghĩ ngay tới máy tính mặc định của Windows. Nếu tính
2+2*2thì nó cho ra 8 chứ không phải 6. Có vẻ như họ cố tình làm vậy, nhưng tôi hoàn toàn không hiểu nổi. Trước đây tôi từng tính lượng cồn trong một ly cocktail, kết quả cho ra lượng cồn còn nhiều hơn cả tổng lượng đồ uống nên đã có một phen bối rối.Đây là kiểu hoạt động của máy tính điện tử thông thường, mỗi lần bấm toán tử thì biểu thức trước đó sẽ được tính ngay; chẳng lẽ bạn chỉ mới dùng máy tính khoa học thôi sao?
Hoàn toàn đồng cảm. Lúc đầu tôi chọn làm ứng dụng máy tính vì thấy không cần máy chủ nên sẽ ổn, ai ngờ sau đó phải vật lộn rất vất vả để bắt các lỗi tính toán và bug phát sinh.
Tổng quan triển khai trong mã nguồn
Giải thích logic phép toán của máy tính trong mã nguồn
Mã xử lý số nguyên
Mã xử lý số thực
"Ứng dụng máy tính à? Ai mà chả làm được" → thực ra không phải vậy
Có vẻ cái này có thể ứng dụng vào vô số chỗ luôn ấy chứ haha
"Python á? Dễ ẹc mà" → thực ra không phải vậy
Tôi cũng đã nghĩ y như vậy khi xem. haha
"JavaScript á? Dễ như ăn kẹo ấy mà" → thật ra không phải vậy
"(10^100)+1−(10^100)"Ồ, thật sự máy tính trên iPhone hiển thị 0, còn máy tính trên Android hiển thị 1.
Nhưng khi tìm kiếm trên Google thì lại hiện ra 0...
Bình luận trên Hacker News