Системы исчисления.

[ikuh]

Доброго времени суток!
Проблема следующая.
Есть число в двоичной системе исчисления (размер порядка 1Мб), нужен алгоритм перевода его в произвольную систему исчисления за разумное время и обратно. В частности интересует системы исчисления по основанию P, где P простое число.
Существуют ли быстрые алгоритмы для перевода из одной системы исчисления в другую?
Буду очень благодарен за ссылки на сайты или книги по этой теме.
Заранее большое спасибо!

[незваный гость]

К сожалению, в литературе не встречал. В лоб (делением по схеме Горнера) время будет, очевидно, пропорционально квадрату длины (что не в кайф).

Могу поделиться идеей, хотя и не проверенной. Рассмотрим число в основании $p^k$. Его перевод в систему по основанию $p$ распадается в перевод каждой "цифры". Идея состоит в том, что бы выбрать $k_1$ оптимально большим (учитывая сложность деления больших чисел), затем применить $k_2$, и так далее. При некоторой удаче сложность может упасть с ${\rm O}(l^2)$ до ${\rm O}(l \log l)$. Есть, конечно, затраты и на вычисление $p^k$. То есть, считать надобно аккуратно.

[незваный гость]

Несколько ссылок, которые стоит посмотреть (я не уверен, что там разбирается именно эта задача, но они могут навести на мысли):
1) (как всегда) Кнут Д. Искусство программирования (Том 2. Получисленные алгоритмы);
2) Грегори Р., Кришнамурти Е. Безошибочные вычисления: методы и приложения;
3) GMP: GNU Multiple Precision Arithmetic Library;