2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 
Сообщение09.12.2005, 01:10 
Аватара пользователя
:evil:
К сожалению, в литературе не встречал. В лоб (делением по схеме Горнера) время будет, очевидно, пропорционально квадрату длины (что не в кайф).

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

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

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group