Действительно. Ну если по две цифры брать, то получится О(1) проверок, потому что отношение двух соседних двузнычных чисел есть 1+О(1/n) (n --- основание системы), так что относительная погрешность частного будет 1+O(1/n), поэтому абсолютная будет O(1).

(Reply to this) (Parent) (Thread)

Почти верно. Осталась ещё одна неточность:
иногда от делимого надо брать три цифры.
Кнут в Искусстве программирования делает очень похоже. Только он в начале
несколько раз удваивает делитель, чтобы старшая цифра была не меньше половины основания.

(Reply to this) (Parent) (Thread)

Не понял, зачем и когда три цифры надо.

(Reply to this) (Parent) (Thread)

Когда делим 100 на 19, например.

(Reply to this) (Parent) (Thread)

так вроде если делить 110 на 19, не сильно больше получается?

(Reply to this) (Parent) (Thread)

Это правда, но проблема в том, что по сути мы все равно делим трёхзначное число на двузначное.
В противном случае мы бы делили 10 на 19 и получили бы 0.

(Reply to this) (Parent)