Cải thiện tốc độ bài toán chia số nguyên lớn

Chia như cấp 1 ấy
Như 12264/123
-> đầu tiên lấy 122 so với 123, ta thấy 122 < 123
-> Lấy thêm 1 số nữa là 1226 > 123
1226 / 123 = 9 dư 119 < 123
-> mượn thêm 4 thành 1194.
1194 / 123 = 9 dư 87
Nhưng do hết số rồi v kq cuồi cùng là 99 và dư 87
Cách này code khá phức tạp nhưng bù lại nhanh hơn trừ thông thường nhiều.

Làm sao để biết 1226 / 123 = 9 dư 119 nhỉ?

KQ phép chia trên thường chỉ trong khoảng từ 1-9
Nên có thể for để tìm
Mà nhân 1 số có 1 chữ số với 1 số cực lớn thì đâu có khó khăn đúng không? :>
-> Nhân kq với số chia rồi trừ là tìm đc số dư ngay.

Vậy thì thực hiện phép trừ như cách của bạn kia, vẫn tốt hơn là nhân thử từ 1 đến 9 chứ nhỉ? Vì phép cộng hay phép trừ thì chỉ có độ phức tạp tuyến tính, còn nhân thì độ phức tạp hàm mũ.

Không hề,
Trừ thì có độ phức tạp O(ma/b) Với a, b = số bị chia và số chia. (m ở đây là độ phức tạp khi trừ 2 số)
Trong khi chia thì có dpt = O(m(m-n)) Với m,n = chiều dài của số bị chia và số chia.
m ở đây là độ phức tạp khi tính phép chia đc tách nhỏ ra.
O(n) cho phép nhân 1 số <10 cho 1 số cực lớn
O(m) nữa cho phép trừ
9 cho vòng lặp.
Vậy tổng là O(9(m+n)) ~ O(m) (giả sử m > n)

Ví dụ 100 / 2
Thì thuật 1 tốn 250 = 100 phép tính
Trong khi thuật 2 chỉ tốn 32 = 6 phép tính

EDIT: Sửa n*(m-n) thành m*(m-n) thì mới đúng

Chốt:
Trừ: O(m*(a/b))
Chia O(m^2)

À nhầm, đang nói đến cách tìm thương nằm trong khoảng từ 1 đến 9. Tưởng cách tìm thương của bạn kia là trừ, nhưng mà là trừ dần dần rồi tăng biến đếm.