2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Системы исчисления.
Сообщение06.12.2005, 08:29 


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

 Профиль  
                  
 
 
Сообщение09.12.2005, 01:10 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 
Сообщение09.12.2005, 07:33 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group