Máy tính chia theo hai cách chính: chia dài trong hệ nhị phân (dịch bit và trừ, mỗi bước cho ra một hoặc vài bit của thương), hoặc tính gần đúng số nghịch đảo 1/b bằng phép lặp Newton rồi nhân với số bị chia. Dù cách nào, phép chia vẫn là phép tính chậm nhất trong bốn phép, và chính mạch chia từng gây ra một trong những lỗi phần cứng nổi tiếng nhất lịch sử: lỗi chia của bộ vi xử lý Intel Pentium năm 1994.
Chia dài nhị phân: phép chia lớp 3 trong hệ 0 và 1
Trong hệ thập phân, mỗi bước chia dài phải đoán "số chia vừa đủ mấy lần", từ 0 đến 9. Trong hệ nhị phân việc này dễ hơn nhiều: thương mỗi bước chỉ là 0 hoặc 1, tức là chỉ cần hỏi "phần đang xét có lớn hơn hoặc bằng số chia không". Có thì trừ và ghi 1, không thì ghi 0.
Ví dụ 27 chia 5. Trong hệ nhị phân, 27 là 11011, 5 là 101:
| Bước | Hạ bit | Phần đang xét | So với 101 | Bit thương | Còn lại |
|---|---|---|---|---|---|
| 1 | 1 | 1 | nhỏ hơn | 0 | 1 |
| 2 | 1 | 11 | nhỏ hơn | 0 | 11 |
| 3 | 0 | 110 | lớn hơn, trừ 101 | 1 | 1 |
| 4 | 1 | 11 | nhỏ hơn | 0 | 11 |
| 5 | 1 | 111 | lớn hơn, trừ 101 | 1 | 10 |
Thương là 00101 = 5, dư 10 = 2. Kiểm lại: 5 × 5 + 2 = 27. Mạch điện làm đúng như vậy: một thanh ghi giữ phần dư, mỗi nhịp đồng hồ dịch trái một bit, thử trừ số chia, xem kết quả âm hay dương để ghi bit thương. Chia hai số 64 bit theo cách này cần khoảng 64 bước, trong khi phép nhân có thể làm song song gần như một lúc. Đó là lý do phép chia chậm.
SRT: đoán nhiều bit một lúc bằng bảng tra
Để nhanh hơn, các bộ xử lý từ thập niên 1960 trở đi dùng họ thuật toán SRT, đặt theo tên ba người độc lập nghĩ ra nó vào khoảng năm 1958: Sweeney, Robertson và Tocher. Ý tưởng: mỗi bước cho ra một "chữ số" thương trong cơ số lớn hơn (cơ số 4 cho 2 bit mỗi bước), và chữ số ấy được đoán bằng cách tra một bảng nhỏ, chỉ dựa vào vài bit đầu của phần dư và số chia. Bảng được thiết kế để dù đoán hơi lệch, các bước sau vẫn tự sửa được, miễn là mọi ô trong bảng đúng.
Chính câu "miễn là mọi ô trong bảng đúng" là nơi câu chuyện năm 1994 bắt đầu.
Lỗi chia Pentium 1994: năm ô trống trong bảng tra
Bộ vi xử lý Pentium ra mắt năm 1993, dùng mạch chia SRT cơ số 4 với một bảng tra 1.066 ô. Khi chuyển bảng vào mạch, năm ô lẽ ra mang giá trị 2 lại bị để là 0. Với phần lớn phép chia, đường tính không bao giờ đi qua năm ô ấy. Với một số rất ít cặp số, nó đi qua, và kết quả sai từ khoảng chữ số có nghĩa thứ tư trở đi.
Người phát hiện là Thomas Nicely, giáo sư toán ở Đại học Lynchburg, bang Virginia. Ông đang tính tổng nghịch đảo các cặp số nguyên tố sinh đôi (liên quan đến hằng số Brun), một phép tính cần hàng tỉ phép chia, và nhận thấy kết quả trên máy Pentium lệch với máy khác. Sau nhiều tháng loại trừ các khả năng, ông kết luận lỗi nằm ở chính bộ xử lý và báo cho Intel, rồi gửi thư cho một số đồng nghiệp vào cuối tháng 10/1994. Thông tin lan nhanh trên mạng.
Ví dụ kinh điển được truyền đi khắp nơi:
- Kết quả đúng: 4.195.835 : 3.145.727 = 1,333820449…
- Pentium lỗi cho ra: 1,333739068…
Sai từ chữ số thập phân thứ tư. Phép thử đơn giản: tính 4.195.835 − (4.195.835 : 3.145.727) × 3.145.727. Máy đúng cho 0; Pentium lỗi cho 256.
Từ "hiếm gặp" đến khoản lỗ 475 triệu đô la
Intel ban đầu cho rằng lỗi hiếm đến mức người dùng bảng tính bình thường chỉ gặp một lần trong khoảng 27.000 năm, và chỉ đổi chip cho ai chứng minh được mình cần tính toán chính xác. IBM tính lại theo cách khác và đưa ra con số một lần trong khoảng 24 ngày, rồi tạm ngừng bán máy tính dùng Pentium. Hai con số chênh nhau vì giả định khác nhau về loại phép chia người dùng hay làm, và chính sự chênh lệch đó làm công chúng mất niềm tin.
Ngày 20/12/1994, Intel đổi chính sách: thay chip miễn phí cho bất kỳ ai yêu cầu. Đầu năm 1995, công ty ghi nhận khoản chi 475 triệu đô la Mỹ cho vụ việc. Bài học được nhắc đến trong giới kỹ thuật suốt ba thập kỷ: một lỗi toán học nhỏ có thể không đáng kể về kỹ thuật nhưng rất đắt về niềm tin. Sau vụ này, các hãng chip đầu tư mạnh vào kiểm chứng hình thức, tức chứng minh toán học rằng mạch đúng thay vì chỉ thử trên nhiều ví dụ.
Cách thứ hai: Newton tìm số nghịch đảo
Thay vì chia trực tiếp, nhiều bộ xử lý và thư viện phần mềm tính 1/b rồi nhân với a, đúng ý tưởng của người Babylon gần bốn nghìn năm trước. Để tính 1/b chỉ bằng nhân và trừ, người ta dùng phép lặp Newton:
x mới = x cũ × (2 − b × x cũ)
Ví dụ tính 1/7, bắt đầu đoán thô x = 0,1:
| Lần lặp | Giá trị x | Số chữ số đúng (so với 0,142857142857…) |
|---|---|---|
| 0 | 0,1 | 0 |
| 1 | 0,13 | 1 |
| 2 | 0,1417 | 2 |
| 3 | 0,14284777 | 4 |
| 4 | 0,1428571422 | 9 |
| 5 | 0,142857142857… | 16 trở lên |
Số chữ số đúng xấp xỉ nhân đôi sau mỗi lần lặp. Bắt đầu bằng một giá trị đoán khá tốt tra từ bảng nhỏ, chỉ hai ba lần lặp là đủ độ chính xác của số thực 64 bit. Cách này hợp với máy có mạch nhân rất nhanh.
Những mẹo chia nhanh trình biên dịch dùng
- Chia cho luỹ thừa của 2 là dịch bit: chia số nguyên không âm cho 8 chỉ là dịch phải 3 bit, giống chia cho 1.000 trong hệ thập phân là bỏ ba chữ số cuối.
- Chia cho hằng số là nhân rồi dịch: khi chương trình viết x : 10 với số 10 cố định, trình biên dịch thay bằng phép nhân x với một "số thần kỳ" rồi dịch phải. Với số nguyên không dấu 32 bit, x : 10 bằng (x × 3.435.973.837) dịch phải 35 bit. Số thần kỳ ấy xấp xỉ 2 mũ 35 chia 10, làm tròn lên.
- Tránh chia trong vòng lặp: người lập trình đồ hoạ, xử lý âm thanh hay tính 1/b một lần rồi nhân nhiều lần.
Mẹo cuối giống thói quen tính nhẩm: chia nhiều số cho 25 thì nhân với 4 rồi chia 100 cho nhanh.
Dòng thời gian phép chia trong máy
| Năm | Sự kiện |
|---|---|
| 1946 | ENIAC có bộ phận riêng để chia và khai căn, chậm hơn nhiều so với cộng |
| Khoảng 1958 | Thuật toán SRT được Sweeney, Robertson, Tocher đề xuất độc lập |
| 1985 | Chuẩn IEEE 754 cho số thực: phép chia phải làm tròn đúng như tính chính xác rồi làm tròn |
| 1993 | Pentium ra mắt với mạch chia SRT cơ số 4 |
| 1994 | Thomas Nicely phát hiện lỗi chia; Intel thay chip theo yêu cầu từ 20/12 |
| 1995 | Intel ghi nhận chi phí 475 triệu đô la Mỹ |
Góc nhìn hôm nay: nghi ngờ con số lạ
Câu chuyện Pentium là lời nhắc rằng máy tính cũng có thể sai, và cách phát hiện thường rất đơn giản: tính một kết quả theo hai cách độc lập rồi so. Nicely tìm ra lỗi vì ông kiểm chéo trên nhiều máy. Với người làm bảng tính hằng ngày, thói quen tương tự là nhân ngược để kiểm phép chia, cộng lại các phần đã chia xem có bằng tổng không. Ai muốn đọc thêm có thể tìm các bài phân tích kỹ thuật về "Pentium FDIV bug", trong đó có cả ảnh chụp mạch và bảng tra được phục dựng.
Câu hỏi thường gặp
Máy tính thực hiện phép chia như thế nào?
Hoặc chia dài trong hệ nhị phân, mỗi bước so phần dư với số chia, trừ và ghi một bit thương; hoặc dùng bảng tra để ra nhiều bit một lúc (thuật toán SRT); hoặc tính số nghịch đảo bằng phép lặp Newton rồi nhân. Phép chia chậm hơn phép nhân nhiều lần.
Lỗi chia Pentium năm 1994 là gì?
Bộ vi xử lý Intel Pentium đời đầu có năm ô bị sai trong bảng tra 1.066 ô của mạch chia, làm một số rất ít phép chia sai từ khoảng chữ số có nghĩa thứ tư. Giáo sư Thomas Nicely phát hiện năm 1994; Intel phải thay chip theo yêu cầu và chịu chi phí 475 triệu đô la.
Ví dụ phép chia sai trên Pentium?
4.195.835 chia 3.145.727 đúng ra là 1,333820449…, còn Pentium lỗi cho 1,333739068… Nhân ngược lại và trừ, máy đúng cho 0, máy lỗi cho 256.
Vì sao phép chia chậm hơn phép nhân?
Vì phép nhân có thể tính các tích riêng song song rồi cộng lại, còn phép chia phải làm tuần tự: bước sau cần phần dư của bước trước. Các mẹo như bảng tra SRT hay phép lặp Newton giúp rút ngắn nhưng phép chia vẫn tốn nhiều nhịp hơn.
Phép lặp Newton tính 1/b như thế nào?
Bắt đầu từ một giá trị đoán x, lặp công thức x mới = x × (2 − b × x). Mỗi lần lặp, số chữ số đúng gần như nhân đôi; với 1/7 bắt đầu từ 0,1, sau bốn lần đã đúng 9 chữ số.