2014 dxdy logo

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

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




На страницу 1, 2  След.
 
 Быстрый перевод из одной системы счисления в другую.
Сообщение15.10.2010, 21:55 
Уважаемые программисты.
Подскажите пожалуйста наиболее быстрый алгоритм перевода числа из одной системы счисления в другую.
Например, у меня есть число 523412321 в восьмиричной системе счисления. Мне нужно представить его в 18-ричной, 30-ричной, 94-ричной системе. Причём наиболее быстрым способом.

P.S. Если это поможет, то основание системы счисления всегда чётное (но хотелось бы иметь универсальный алгоритм).
P.P.S. Размерность числа (количество знаков) может быть любой.

Так же интересует ваше мнение по вопросам:
1. Легче (быстрее) переводить из системы счисления с меньшим основанием в большее или на оборот?
2. Что обуславливает скорость перевода (кроме размерности числа) ?
3. Есть ли выигрыш в том, что системы счисления чётные или выигрыша нет (есть проигрыш по времени)?

Заранее спасибо. Буду рад любым ссылкам и конструктивным идеям.

 
 
 
 Re: Быстрый перевод из одной системы счисления в другую.
Сообщение15.10.2010, 21:58 
Аватара пользователя
Халявы здесь нет. Сначала ваши попытки решения.

 
 
 
 Re: Быстрый перевод из одной системы счисления в другую.
Сообщение15.10.2010, 22:17 
whiterussian в сообщении #362557 писал(а):
Халявы здесь нет. Сначала ваши попытки решения.

Не знаю, что вы имеете в виду под халявой. Меня не интересует код на каком-либо языке программирования.
Меня интересуют алгоритмы если таковые существуют и их теоретическое обоснование. Если вы знаете где об этом можно почитать, то я буду глубоко признателен.
Пока перевожу обычным способом:
Код:
0. (((a[i]*n + a[i-1])*n + a[i-2])*n + ...)* n + a[0] -> x в десятичный вид, а затем
1. x MOD m -> первая цифра
2. x DIV m = x
Операции 1 и 2 повторять пока x > 0.

Числа с которыми я работаю естественно целые.

Для перевода из системы счисления с большим основанием в систему счисления с меньшим основанием существует более "удобный" алгоритм:
Код:
Пусть A представлено в виде "1" в системе счисления по основанию A, тогда в системе счисления по основанию A-1 оно будет представляться в виде "11", в системе счисления A-2 --- "12" и так далее, в системе по основанию A-n ---"1n" до тех пор, пока A-n > 2n.

 
 
 
 Re: Быстрый перевод из одной системы счисления в другую.
Сообщение15.10.2010, 22:22 
Аватара пользователя
дело в том, что ваш текст уж очень смахивает на стандартную задачу по computer science. А ваши цитирования - на цитирования on-line лекций. Вот и все.

 
 
 
 Re: Быстрый перевод из одной системы счисления в другую.
Сообщение15.10.2010, 22:30 
madzi в сообщении #362567 писал(а):
Пока перевожу обычным способом:
Хороший способ. Для большинства случаев достаточен.

madzi в сообщении #362567 писал(а):
Для перевода из системы счисления с большим основанием в систему счисления с меньшим основанием существует более "удобный" алгоритм:
Плохой способ. Работает только для небольшого количества чисел особого вида, типа "10".

На самом деле есть, конечно, пути оптимизации Вашего алгоритма, но их стоит применять, только если преобразование представления - действительно критическая часть вычислений.
Для начала можно соптимизировать, если обе базы являются степенью одного числа, как 2-, 8- и 16-ричная системы.

 
 
 
 Re: Быстрый перевод из одной системы счисления в другую.
Сообщение15.10.2010, 22:31 
whiterussian в сообщении #362570 писал(а):
дело в том, что ваш текст уж очень смахивает на стандартную задачу по computer science. А ваши цитирования - на цитирования on-line лекций. Вот и все.

Ок. Если задача стандартная, то должны быть её стандартные решения.
Пожалуйста, укажите мне их.
Вариантов по переводу из одной системы счисления в другую (для школьников/студентов) море. Например, тут один из примеров по Google.
Меня интересует алгоритмы быстрых преобразований (т.к. разрабатывается для медленной однокристалки, к тому же эта функция вспомогательная и на неё нельзя тратить много времени/тактов).

-- Пт окт 15, 2010 23:37:10 --

venco в сообщении #362576 писал(а):
madzi в сообщении #362567 писал(а):
Пока перевожу обычным способом:
Хороший способ. Для большинства случаев достаточен.

На самом деле плохой способ, потому что требует промежуточного представления числа и потребляет большое количество вычислительного времени.

venco в сообщении #362576 писал(а):
madzi в сообщении #362567 писал(а):
Для перевода из системы счисления с большим основанием в систему счисления с меньшим основанием существует более "удобный" алгоритм:
Плохой способ. Работает только для небольшого количества чисел особого вида, типа "10".

На самом деле есть, конечно, пути оптимизации Вашего алгоритма, но их стоит применять, только если преобразование представления - действительно критическая часть вычислений.
Для начала можно соптимизировать, если обе базы являются степенью одного числа, как 2-, 8- и 16-ричная системы.

К сожалению, базы не являются степенью какого-либо числа. Единственное, что известно про базы точно --- то, что они чётные. Более того, к сожалению, заранее базы не известны. Т.е. нельзя получить заранее аналитическое решение для перевода из 42-ричной системы в 26-ричную, потому что очередное число может быть записано в 60-ричной, а может и в 28-ричной. Да и выходные системы требуются различные.

Буду благодарен вашим предложениям по оптимизации алгоритма.

 
 
 
 Re: Быстрый перевод из одной системы счисления в другую.
Сообщение15.10.2010, 22:40 
Для однокристалки скорее надо оптимизировать по размеру кода. Соответственно, лучше всего подойдёт уже приведённый простейший алгоритм.

 
 
 
 Re: Быстрый перевод из одной системы счисления в другую.
Сообщение15.10.2010, 22:42 
Размер кода пока не критичен. Критично время вычисления. В моём случае простейший алгоритм не подходит. Иначе я бы не обратился за помощью на форум.

 
 
 
 Re: Быстрый перевод из одной системы счисления в другую.
Сообщение15.10.2010, 22:42 
Я не знаю для чего Вам понадобился перевод, но обычно оптимально хранить и работать с числами в родном - бинарном формате, а переводить в нужную систему счисления при вводе/выводе.

 
 
 
 Re: Быстрый перевод из одной системы счисления в другую.
Сообщение15.10.2010, 22:48 
venco в сообщении #362585 писал(а):
Я не знаю для чего Вам понадобился перевод, но обычно оптимально хранить и работать с числами в родном - бинарном формате, а переводить в нужную систему счисления при вводе/выводе.

Ок. Есть некий канал, по которому приходит информация о:
Код:
1. основании (системы счисления)
2. количестве разрядов
3. сами разряды (от младших к старшим)
4. новое основание (требуемая система счисления)
От алгоритма ожидается:
1. основание (которое было задано)
2. количество разрядов (от младших к старшим)
3. сами разряды

Всё это используется некоторой системой авторизации, которая таким образом проверяет, что не подменили чип, на котором работает основная программа.

 
 
 
 Re: Быстрый перевод из одной системы счисления в другую.
Сообщение15.10.2010, 22:58 
Какие пределы у оснований, длин чисел, и величин чисел?

-- Пт окт 15, 2010 15:59:34 --

(Оффтоп)

madzi в сообщении #362586 писал(а):
Всё это используется некоторой системой авторизации, которая таким образом проверяет, что не подменили чип, на котором работает основная программа.
Мне кажется, для защиты такой примитивный алгоритм мало подходит.

 
 
 
 Re: Быстрый перевод из одной системы счисления в другую.
Сообщение15.10.2010, 23:00 
venco в сообщении #362576 писал(а):
Плохой способ. Работает только для небольшого количества чисел особого вида, типа "10".

На самом деле есть, конечно, пути оптимизации Вашего алгоритма, но их стоит применять, только если преобразование представления - действительно критическая часть вычислений.
Для начала можно соптимизировать, если обе базы являются степенью одного числа, как 2-, 8- и 16-ричная системы.

Хотелось бы услышать по-подробнее, почему данный способ является плохим, так как он показывает большую производительность.

Допустим у меня есть число
$231\equiv(1.0)_{231}$ уменьшим систему счисления на 1
$231\equiv(1.1)_{230}$ продолжаем уменьшение на 1
$231\equiv(1.2)_{229}$ таким образом я могу дойти до $231/2 = 115$ т.е.
$231\equiv(1.114)_{115}$ при этом я могу рассчитать значения разрядов за одну операцию.
При переходе через гранцу $\frac{A-n}{2}>n$ увеличивается старший разряд, а младший почти обнуляется
$231\equiv(2.1)_{114}$ и т.д.

 
 
 
 Re: Быстрый перевод из одной системы счисления в другую.
Сообщение15.10.2010, 23:04 
madzi в сообщении #362593 писал(а):
$231\equiv(1)_{231}$
Вы уже второй раз повторили ошибку. На самом деле:$231\equiv(10)_{231}$

 
 
 
 Re: Быстрый перевод из одной системы счисления в другую.
Сообщение15.10.2010, 23:06 
venco в сообщении #362591 писал(а):
Какие пределы у оснований, длин чисел, и величин чисел?

-- Пт окт 15, 2010 15:59:34 --

(Оффтоп)

madzi в сообщении #362586 писал(а):
Всё это используется некоторой системой авторизации, которая таким образом проверяет, что не подменили чип, на котором работает основная программа.
Мне кажется, для защиты такой примитивный алгоритм мало подходит.

Длина не превышает 50 разрядов.
Основание не превышает 65535.

(Оффтоп)

Защиту разрабатывал не я, а тот кто изначально создавал систему. От меня требуется сменить чип на более производительную модификацию. Повторив при этом алгоритмы авторизации. К сожалению, мне не известно каким образом автор осуществлял перевод. Я предполагаю, что у него для этих целей имелась заготовленная таблица возможных чисел и ответов на них. Но такой способ мне не подходит в виду больших требований к объёму памяти (как вариант, возможно числа вычислялись некоторым способом, но тратить времени на анализ и нахождения этого способа у меня тоже нет времени). Автор, естественно, не оставил исходников. Спасибо, что документацию написал...


-- Сб окт 16, 2010 00:07:25 --

venco в сообщении #362596 писал(а):
madzi в сообщении #362593 писал(а):
$231\equiv(1)_{231}$
Вы уже второй раз повторили ошибку. На самом деле:$231\equiv(10)_{231}$

Согласен. Вы правы, это действительно 10.

 
 
 
 Re: Быстрый перевод из одной системы счисления в другую.
Сообщение15.10.2010, 23:07 
madzi в сообщении #362593 писал(а):
уменьшим систему счисления на 1
Вы предлагаете заменить несколько умножений и делений на гораздо большее количество инкрементов/декрементов. Это будет эффективнее только если на Вашем процессоре умножение и деление реализовано через примитивное сложение и вычитание.

-- Пт окт 15, 2010 16:11:17 --

Более того, когда числа у Вас станут длиннее двух разрядов, операция перехода к следующему основанию станет сравнимой по сложности с исходной задачей.

-- Пт окт 15, 2010 16:13:16 --

В общем, оптимизировать надо имплементацию обычного алгоритма, например, заменой деления умножением и т.п.
Как именно это делать - зависит от системы команд.

 
 
 [ Сообщений: 22 ]  На страницу 1, 2  След.


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