Phép chia dài
Vì một số trục trặc trong việc xác nhận tài khoản với bên hosting nên tới giờ tôi vẫn chưa khôi phục lại được trang Tin Sáng. Đầu tuần tôi sẽ gọi điện để nói chuyện với họ xem có cách nào giải quyết nhanh được hay không.
Cập nhật: Tin Sáng đã trở lại :-).
Một hai tuần trước tôi có đố thế này trên Tin Sáng: chia 778990657124673576 cho 999489 với số phép tính ít nhất. Có rất nhiều câu trả lời thú vị và đây là đáp án của tôi.
Tôi phải nghĩ về vấn đề này khi phải thiết kế một thư viện để làm các phép toán số học trên số nguyên lớn (thường gọi là Big Integer). Trong các phép toán số học này thì phép chia lấy số dư là quan trọng nhất (vì nó là phép tính được dùng nhiều nhất trong các thuật toán mã hóa). Để lập trình phép tính này, tôi tham khảo thuật toán Long Division mà Knuth mô tả trong chương 4, cuốn The Art of Computer Programming II.
Nếu muốn chia 1736 cho 27, việc đầu tiên bạn cần làm là ước lượng chữ số thứ nhất của thương sao cho khi nhân nó với 20 thì nhỏ hơn 173. Bạn ước lượng càng chính xác thì số phép tính bạn phải thực hiện càng ít. Trung bình một người ước lượng một hai lần cho đến khi họ có con số chính xác, nên nhìn chung con người làm tốt việc này.
Câu hỏi là làm sao dạy cho máy tính cách ước lượng và thuật toán của Knuth chính là câu trả lời. Knuth chỉ ra rằng chữ số \(q_0'\) tính theo cách dưới đây chỉ lệch nhiều nhất là 2 đơn vị so với chữ số đầu tiên \(q_0\) của thương:
$$q_0' = \min(\lfloor \frac{u_0 * b + u_1}{v_0} \rfloor, b - 1)$$ trong đó
* \(b\) là hệ cơ số. các hệ cơ số thường dùng là \(2, 10, 16,\dots\)
* \(u_0, v_0\) lần lượt là chữ số đầu tiên của số bị chia và số chia.
Knuth chứng minh rằng \(q_0' \ge q_0\) và nếu như \(v_0 \ge \lfloor \frac{b}{2} \rfloor\) thì \(q_0 \ge q_0' - 2\). Nói cách khác thuật toán của Knuth mô phỏng xuất sắc quá trình làm phép chia của con người.
Điều kiện \(v_0 \ge \lfloor \frac{b}{2} \rfloor\) gợi ý rằng nếu \(v_0\) có một dạng đặc biệt thì có thể tìm được một ước lượng tốt hơn một chút. Giả sử như \(v_0 = b - 1\). Lúc này ta có
$$
x = \lfloor \frac{u_0 * b + u_1}{v_0} \rfloor
= \lfloor \frac{u_0 * b + u_1}{b - 1} \rfloor
= u_0 + \lfloor \frac{u_0 + u_1}{b - 1} \rfloor
\le u_0 + 2
$$
Trường hợp \(x = u_0 + 2\) chỉ xảy ra với xác suất \(\frac{1}{b^2}\) khi \(u_0 = u_1 = b - 1\). Nói cách khác, khi \(v_0 = b - 1\) thì \(u_0\) là một ước lượng rất tốt cho \(q_0\). Với xác suất rất cao \(u_0\) hoặc \(u_0 + 1\) chính là chữ số kế tiếp của thương.
Quay trở lại với câu đố. Do số bị chia bắt đầu bằng 999, ta có thể chọn b = 1000 và thực hiện phép chia theo thuật toán của Knuth với mẹo mà tôi vừa nói. Tổng cộng số phép toán phải thực hiện là 10, trong đó bao gồm 4 phép nhân và 6 phép trừ.
Giải thích hình:
- Hàng 2, 3, 4: chữ số đầu tiên (trong hệ cơ số 1000) của số bị chia là 778 và tôi dự đoán nó cũng là chữ số đầu tiên của thương. Khi nhân 778 với 999489 tôi có 777602442, trừ với số bị chia thì nhận được 001388215. Chữ số đầu tiên sau khi trừ là 001, nghĩa là dự đoán ban đầu của tôi bị hụt 1 đơn vị, nên phải cộng 1 lên cho thương (778 + 1 = 779) đồng thời trừ số bị chia cho số chia một lần nữa (1388215 - 99489 = 388726).
- Hàng thứ 5 bạn sẽ thấy chữ số đầu tiên của số bị chia đã trở thành 0. Nghĩa là tôi đã loại bỏ được một chữ số của số bị chia. Lập lại dự đoán: 388 sẽ là chữ số kế tiếp của thương.
Cập nhật: Tin Sáng đã trở lại :-).
Một hai tuần trước tôi có đố thế này trên Tin Sáng: chia 778990657124673576 cho 999489 với số phép tính ít nhất. Có rất nhiều câu trả lời thú vị và đây là đáp án của tôi.
Tôi phải nghĩ về vấn đề này khi phải thiết kế một thư viện để làm các phép toán số học trên số nguyên lớn (thường gọi là Big Integer). Trong các phép toán số học này thì phép chia lấy số dư là quan trọng nhất (vì nó là phép tính được dùng nhiều nhất trong các thuật toán mã hóa). Để lập trình phép tính này, tôi tham khảo thuật toán Long Division mà Knuth mô tả trong chương 4, cuốn The Art of Computer Programming II.
Nếu muốn chia 1736 cho 27, việc đầu tiên bạn cần làm là ước lượng chữ số thứ nhất của thương sao cho khi nhân nó với 20 thì nhỏ hơn 173. Bạn ước lượng càng chính xác thì số phép tính bạn phải thực hiện càng ít. Trung bình một người ước lượng một hai lần cho đến khi họ có con số chính xác, nên nhìn chung con người làm tốt việc này.
Câu hỏi là làm sao dạy cho máy tính cách ước lượng và thuật toán của Knuth chính là câu trả lời. Knuth chỉ ra rằng chữ số \(q_0'\) tính theo cách dưới đây chỉ lệch nhiều nhất là 2 đơn vị so với chữ số đầu tiên \(q_0\) của thương:
$$q_0' = \min(\lfloor \frac{u_0 * b + u_1}{v_0} \rfloor, b - 1)$$ trong đó
* \(b\) là hệ cơ số. các hệ cơ số thường dùng là \(2, 10, 16,\dots\)
* \(u_0, v_0\) lần lượt là chữ số đầu tiên của số bị chia và số chia.
Knuth chứng minh rằng \(q_0' \ge q_0\) và nếu như \(v_0 \ge \lfloor \frac{b}{2} \rfloor\) thì \(q_0 \ge q_0' - 2\). Nói cách khác thuật toán của Knuth mô phỏng xuất sắc quá trình làm phép chia của con người.
Điều kiện \(v_0 \ge \lfloor \frac{b}{2} \rfloor\) gợi ý rằng nếu \(v_0\) có một dạng đặc biệt thì có thể tìm được một ước lượng tốt hơn một chút. Giả sử như \(v_0 = b - 1\). Lúc này ta có
$$
x = \lfloor \frac{u_0 * b + u_1}{v_0} \rfloor
= \lfloor \frac{u_0 * b + u_1}{b - 1} \rfloor
= u_0 + \lfloor \frac{u_0 + u_1}{b - 1} \rfloor
\le u_0 + 2
$$
Trường hợp \(x = u_0 + 2\) chỉ xảy ra với xác suất \(\frac{1}{b^2}\) khi \(u_0 = u_1 = b - 1\). Nói cách khác, khi \(v_0 = b - 1\) thì \(u_0\) là một ước lượng rất tốt cho \(q_0\). Với xác suất rất cao \(u_0\) hoặc \(u_0 + 1\) chính là chữ số kế tiếp của thương.
Quay trở lại với câu đố. Do số bị chia bắt đầu bằng 999, ta có thể chọn b = 1000 và thực hiện phép chia theo thuật toán của Knuth với mẹo mà tôi vừa nói. Tổng cộng số phép toán phải thực hiện là 10, trong đó bao gồm 4 phép nhân và 6 phép trừ.
Giải thích hình:
- Hàng 2, 3, 4: chữ số đầu tiên (trong hệ cơ số 1000) của số bị chia là 778 và tôi dự đoán nó cũng là chữ số đầu tiên của thương. Khi nhân 778 với 999489 tôi có 777602442, trừ với số bị chia thì nhận được 001388215. Chữ số đầu tiên sau khi trừ là 001, nghĩa là dự đoán ban đầu của tôi bị hụt 1 đơn vị, nên phải cộng 1 lên cho thương (778 + 1 = 779) đồng thời trừ số bị chia cho số chia một lần nữa (1388215 - 99489 = 388726).
- Hàng thứ 5 bạn sẽ thấy chữ số đầu tiên của số bị chia đã trở thành 0. Nghĩa là tôi đã loại bỏ được một chữ số của số bị chia. Lập lại dự đoán: 388 sẽ là chữ số kế tiếp của thương.
Comments
rao vặt