Перевод из любой системы счисления в любую с++

[Duncon]

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

[Сионист]

Ту вот сам и иди. Я, конечно, понимаю, что инженер с дефицитом фантазии - это поэт. Но её ведь нет совсем. Так что остаётся программирование чужих идей.

[Absurd]

Сумматоров и сдвигателей, иначе умножение может занимать многие годы. А раз в самом умножении уже есть сдвиг, то действительно зачем дублировать?

ОК, тогда задача: нарисуйте пожалуйста схему сдвигателя байта влево на N позиций на логических элементах И-ИЛИ-НЕ. Вход - 8 сигнальных линий байта который сдвигаем и четыре сигнальные линии аргумента, кодирующие величину сдвига (0-8). Выход - 16 сигнальных линий.

[Сионист]

1. Я то нарисовал. Удвоитель, двигать за один раз на все произвольное количество бит - схема сложнее, рисовать ленивее и тогда добавляются ещё 3 входа для правого операнда. На одной логике и так лень, нарисовал на триггерах. А попробуй ты на одних сумматорах. И чтоб при этом уложиться в 40 тактов. При этом не используя x<<1=x+x, x<<2=(x<<1)+(x<<1), x<<3=(x<<2)+(x<<2), x<<4=(x<<3)+(x<<3), x<<5=(x<<4)+(x<<4), x<<6=(x<<5)+(x<<5), x<<7=(x<<6)+(x<<6).
2. 8 бит + синхронизация, + надо "сказать", копируем мы левый операнд, или двигаем. набегает 11, а вот выходов достаточно 8.

Да, кому кажется, что у меня много фантазии, подумайте вот над чем: фантастов хватило только на полёты дальше и быстрей, лампы мощней и чуть иначе выглядящих существ, среди поэтов считается гением тот, кто даже сочиняя про колдуна не смог придумать ни одного заклятья, а инженеры то принципиально новый двигатель сочинят, то принципиально отличающийся от полевых и биполярных баллистический транзистор, то придумают в локаторе юзать доплеровский эффект от вращения лопастей, то ещё чего нибудь.

[Absurd]

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

Тем не менее, операция сдвига должна выполняться за один такт, так что это не соответствует тому что использовалось начиная с 386-го процессора.

https://ru.wikipedia.org/wiki/Barrel_shifter

А попробуй ты на одних сумматорах.

Учебник по Computer science Кормана-Лайзерсона-Ривеста, раздел 29.3.1, иллюстрация 29.14 (матричный умножитель). Точно такая же квадратичная зависимость количества необходимых элементов от разрядности операндов как и в barrel shifter-е.

Примерно так:

[Absurd]

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

Absurd пишет именно за этим. Я - не за этим.

Ну тут не RSDN и не /s/, тем не менее. Тебе грех жаловаться.

[Сионист]

Тем не менее, операция сдвига должна выполняться за один такт, так что это не соответствует тому что использовалось начиная с 386-го процессора.

https://ru.wikipedia.org/wiki/Barrel_shifterТак я и нарисовал сдвиг за один такт, это умножение занимает больше. Просто только на один бит, но для умножения этого достаточно. Всё равно ведь правый операнд последовательно пробегает все значения.

Код: Выделить всё

for (i=0, Result=0; i<7; ++i)
{
 Result+=(x<<i)*((y>>i)&1);
}

можно заменить на

Код: Выделить всё

for (Result=0; y!=0; x<<=1, y>>=1)
{
 Result+=x*(y&1);
}

. Но можно и произвольный сдвиг за 1 такт сделать, просто схема позапутанней выйдет. И при чём здесь i80386? Интерпретация CISC системы команд микрокодом RISC ядра появилась позже. НЯЗ с пентиума. И Вы же не будете утверждать, что на том же i80386 умножение занимает больше времени, чем сложение. И по-Вашему же выходит, что и больше, чем сдвиг. Если же делать сдвиг через умножение, используя весь умножитель целиком, то надо сначала по величине сдвига вычислить множитель, накопив произведение нужного количества двоек (так как без рядов ни как иначе степень на получишь, в лучшем случае можно оптимизировать, учтя, что четвертая степень есть квадрат квадрата, восьмая - квадрата четвёртой и так далее), а потом ещё и умножить полученную степень на левый операнд. x<<=2 в этом случае займёт в три раза больше времени, чем умножение, да и то в предположении о нулевых накладных расходах на цикл, чего не бывает. В порядке бреда конечно можно предположить, что микрокод исполняется на более высокой частоте, чем тактовая частота всего процессора, но я не могу себе представить, как это можно было бы реализовать.

Учебник по Computer science Кормана-Лайзерсона-Ривеста, раздел 29.3.1, иллюстрация 29.14 (матричный умножитель). Точно такая же квадратичная зависимость количества необходимых элементов от разрядности операндов как и в barrel shifter-е.

Примерно так:

All complete. Вот только Ваша схема отчётливо благоухает сдвигом, да ещё и неявным. Сколько сумматоров наберётся в x64? А с явным сдвигом достаточно одного. И одного сдвигателя. Причём, если плюнуть на растактовку сдвига на произвольную величину, то зависимость линейная, а сдвиг не занимает времени больше, чем умножение. Причём, меньшие размеры - это большая частота.

[Absurd]

Сколько сумматоров наберётся в x64? А с явным сдвигом достаточно одного. И одного сдвигателя. Причём, если плюнуть на растактовку сдвига на произвольную величину, то зависимость линейная, а сдвиг не занимает времени больше, чем умножение. Причём, меньшие размеры - это большая частота.

Еще раз - вычислительный блок на современных чипах занимает менее 20% площади. При этом он содержит не только целочисленную, но и плавающую арифметику и еще и SIMD инструкции. Это не узкое место, экономия транзисторов тут большого выигрыша не даст. Некоторые исследователи предлагают усложнить плавающую точку чтобы, например, иметь представление для чисел вроде 1/3 без ошибки округления, поскольку подобная модификация не сильно увеличит площадь кристалла. (https://www.crcpress.com/The-End-of-Err ... 1482239867)

Узкое место в современных CPU - кеши и когерентность кешей (MESI protocol).