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

[madzi]

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

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

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

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

Нет. Я не предлагаю заменять. Просто указываю на то, что движение "вниз" более предпочтительно. Так может быть реализовано одним делением и взятием остатка. Промежуточные переходы меня не интересуют. Но это справедливо для первого диапазона. Меня же интересует общий случай.
Под первым диапазоном я понимаю основания от $X$ до $X/2$ т.е.
если у меня есть 231 в 142-ричной системе счисления, то это $231\equiv(1.89)_{142}$. И мне нужно перейти к 120-ричной системе счисления, то я знаю, что нужно к последнему разряду просто добавить $22=142-120$ и проверить, что последний разряд не перешёл через основание. $231\equiv(1.89+22)_{120}=(1.111)_{120}$. Можно наоборот, не добавлять, а вычитать (при переходе от 120- к 142-ричной).

P.S. Кстати, сейчас посмотрел - все числа что мне известны - нечётные, даёт ли это выигрыш? также как неясно есть ли выигрыш от чётного основания системы?

[venco]

Можно ещё сделать так, на примере перевода основания из 13 в 10.
Входное число: $(5.7.6)_{13} \equiv 942$
Сначала считаем поразрядно:
$(1.0)_{13} = (1.3)_{10}$
$(1.0.0)_{13} = (1.6.9)_{10}$
Домножаем на соответствующую цифру, складываем и нормализуем:
$6*(0.0.1)+7*(0.1.3)+5*(1.6.9) = (0.0.6)+(0.7.21)+(5.30.45) = (5.37.72) = (5.44.2) = (9.4.2)$
Такой алгоритм будет быстрее, т.к. требует операций с относительно небольшими числами.

-- Пт окт 15, 2010 16:25:02 --

Ваше постепенное уменьшение основания работает только пока разрядов мало. Уже для трёх вычисления существенно усложняются, а если ещё больше, то проще будет воспользоваться простым алгоритмом.

[madzi]

Интересная идея. Спасибо.
Думаю её можно развить в следующую:

Ошибочные рассуждения писал(а):

Имеем $942 \equiv (5.7.6)_{13}$
Получаем $(6)_{13}$ и переводим его $(6+3)_{10}$
Получаем следующий разряд $(7)_{13}$ и переводим его $(7+3.9+3)_{10}$
Получаем следующий разряд $(5)_{13}$ и переводим его $(5+3.10+3.12)_{10}$
Получаем $(8+1.3+1.2)_{10} = (942)_{10}$

Правильные рассуждения писал(а):

Имеем $942 \equiv (5.7.6)_{13}$
Получаем $(6)_{13}$ и переводим его $(6)_{10}$
Получаем следующий разряд $(7)_{13}$ и переводим его $(7.6+7*3)_{10}$
Получаем следующий разряд $(5)_{13}$ и переводим его $(5.7+5*6.27+5*9)_{10}$
Получаем $(5.37.72)_{10}=(8.14.2)_{10}=(9.4.2)_{10}$

[venco]

Ничего не понял, но если Вам понятно, то и пусть.

[madzi]

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

Ничего не понял, но если Вам понятно, то и пусть.

Я постараюсь более чётко сформулировать и тогда запощу сюда. Пока мне ясно одно, что предложенная вами идея позволяет реализовать сериализацию алгоритма (по вводу). Т.е. вычислять по мере поступления разрядов. Это уже огромный плюс.

Остаются пока не понятными вопросы из первого поста:
1. Есть-ли преимущества в том, что числа нечётные ?
2. Есть-ли преимущества в том, что основания у систем счисления чётные ?
3. Есть-ли преимущества у перевода из системы с большем основанием в меньшую ?

[venco]

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

Правильные рассуждения писал(а):

Имеем $942 \equiv (5.7.6)_{13}$
Получаем $(6)_{13}$ и переводим его $(6)_{10}$
Получаем следующий разряд $(7)_{13}$ и переводим его $(7.6+7*3)_{10}$
Получаем следующий разряд $(5)_{13}$ и переводим его $(5.7+5*6.27+5*9)_{10}$
Получаем $(5.37.72)_{10}=(8.14.2)_{10}=(9.4.2)_{10}$

А вот это то же, что и у меня.

[NikSoft]

Кнут Д. Исскуство программирования, Т2, третье издание
Глава 4.4 Преобразование из одной системы счисления в другую