Быстрый перевод из одной системы счисления в другую.

[madzi]

Уважаемые программисты.
Подскажите пожалуйста наиболее быстрый алгоритм перевода числа из одной системы счисления в другую.
Например, у меня есть число 523412321 в восьмиричной системе счисления. Мне нужно представить его в 18-ричной, 30-ричной, 94-ричной системе. Причём наиболее быстрым способом.

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

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

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

[whiterussian]

Халявы здесь нет. Сначала ваши попытки решения.

[madzi]

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.

[whiterussian]

дело в том, что ваш текст уж очень смахивает на стандартную задачу по computer science. А ваши цитирования - на цитирования on-line лекций. Вот и все.

[venco]

madzi в сообщении #362567 писал(а):

Пока перевожу обычным способом:

Хороший способ. Для большинства случаев достаточен.

madzi в сообщении #362567 писал(а):

Для перевода из системы счисления с большим основанием в систему счисления с меньшим основанием существует более "удобный" алгоритм:

Плохой способ. Работает только для небольшого количества чисел особого вида, типа "10".

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

[madzi]

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-ричной. Да и выходные системы требуются различные.

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

[venco]

Для однокристалки скорее надо оптимизировать по размеру кода. Соответственно, лучше всего подойдёт уже приведённый простейший алгоритм.

[madzi]

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

[venco]

Я не знаю для чего Вам понадобился перевод, но обычно оптимально хранить и работать с числами в родном - бинарном формате, а переводить в нужную систему счисления при вводе/выводе.

[madzi]

venco в сообщении #362585 писал(а):

Я не знаю для чего Вам понадобился перевод, но обычно оптимально хранить и работать с числами в родном - бинарном формате, а переводить в нужную систему счисления при вводе/выводе.

Ок. Есть некий канал, по которому приходит информация о:

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

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

[venco]

Какие пределы у оснований, длин чисел, и величин чисел?

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

(Оффтоп)

madzi в сообщении #362586 писал(а):

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

Мне кажется, для защиты такой примитивный алгоритм мало подходит.

[madzi]

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}$ и т.д.

[venco]

madzi в сообщении #362593 писал(а):

$231\equiv(1)_{231}$

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

[madzi]

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.

[venco]

madzi в сообщении #362593 писал(а):

уменьшим систему счисления на 1

Вы предлагаете заменить несколько умножений и делений на гораздо большее количество инкрементов/декрементов. Это будет эффективнее только если на Вашем процессоре умножение и деление реализовано через примитивное сложение и вычитание.

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

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

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

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