попробуем метод дихотомии (половинного деления) "наоборот" :)))
Например делитель возводим в степень двойки, пока не превысим делимое, запоминаем результат. С остатком поступаем так же. С остатком остатка - аналогично и так до конца.
В финале - складываем коэффициенты.
ИМХО для больших результатов быстрее будет :))
З.Ы. можно ещё подумать как оптимизировать. Это первое что пришло в голову.