Перевод десятичных чисел в двоичную и шестнадцатеричную формы (61, 152)

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

Но сначала я предлагаю решить задачку чуть попроще - перевод в двоичную систему. Не использующую регистров памяти. Почему добавлено ограничение на регистры памяти? Если использовать данный алгоритм в качестве подпрограммы, для внедрения кода в основную программу будет достаточно согласований по вводу и возврату на уровне стека.


Перевод из десятичного в двоичное

В связи с отсутствием МК-152 эксперимент проводим на эмуляторе МК-61/52.

00.В^  01.0  02.ХУ 03.1    04.ХУ  05.2   06./   07.К[x] 08.FBx 09.К{х}  
10.Кзн 11.ХУ 12.FО 13.ХУ   14.х   15.FBx 16.ВП  17.1    18.FО  19.+
20.В^  21.FО 22.FО 23.Fx=0 24.05  25.FО  26.FО  27.С/П 

Инструкция: ввод десятичного числа в РХ, В/0, С/П - на экране его двоичное представление. Стек используется полностью, то есть вся информация в стеке после выполнения будет потеряна. В связи с ограничениями разрядности индикатора (8 позиций), корректно отобразить можно только числа в диапазоне 0..255.

Например, 234, В/0, С/П дает

11101010

Вывод на индикатор МК-152 должен быть проще, программа сократится, т.к. не понадобится умножать на степень 10 для сдвига разрядов влево (в сторону старших).


Перевод из десятичного в шестнадцатеричное

В МК-152 есть возможность выводить строки символов из памяти данных (регистров с адресами адреса от 1000 до 8167). Идея состоит в наполнении регистров с 1000 по 1007 байтами, содержащими ASCII-код шестнадцатеричного символа, а в конце вывести эту строку на экран.

К сожалению, следующий простой алгоритм получения остатка от деления для двух чисел n1 и n2 не работает если разрядность n1 приближается к максимальной (8 разрядов).

n1 B^ n2 : K[x] FBx K{x} n2 * K[x]

Например, остаток деления 99999999 на 16 будет не 15, а 14, при отбрасывании дробной части от 14,5. Поэтому придется честно умножать делитель на целую часть от остатка и вычитать из делимого.

00.П2  01.1   02.0   03.0   04.9   05.ПО   06.Сx  07.ПП  08.45   09.ИП2 
10.ИП2 11.1   12.6   13.П1  14.:   15.K[x] 16.П2  17.ИП1 18.х    19.-    
20.ПП  21.35  22.ИП2 23.ИП1 24.-   25.Fx

Программа использует стек и регистры Р0, Р1 и Р2.

Инструкции: вводим десятичное число, В/0, С/П, на экран в строку выводится шестнадцатеричное представление.

Второй вариант был предложен пользователем AtH, программа использует цикл вместо блока сравнения остатка с делителем (16) по шагам 22-29. Прежняя проблема с целочисленным делением на МК-152 отсутствует, то есть для 99999999 остаток получится 15,00032.

Вот вариант AtH (завершающий БП 00 не является обязательным по условиям, тем более, в качестве подпрограммы, поэтому я убрал его в обоих вариантах.).
00.П1  01.7    02.П0   03.3   04.F10x 05.+     06.П3  07.1   08.6    09.П2
10.Сх  11.КП3  12.ИП1  13.ИП2 14./    15.К[x]  16.П1  17.FBx 18.K{x} 19.ИП2
20.х   21.K[x] 22.1    23.0   24.-    25.Fx≥0  26.29  27.7   28.+    29.5
30.8   31.+    32.КП3  33.FL0 34.12   35.ИП3   36.1   37.+   38.РРП  39.90
40.27  41.С/П

Попробуем сократить код. Цифру 7 заменяем на 8, в противном случае, максимальным выводимым числом будет не 99999999, а 16777215 (преобразуется в FFFFFF). Далее, заменим блок 03-06 более коротким, а 07-09 безболезненно перенесем по месту первого использования делителя на адрес 13.

Команду 32.КПЗ можно убрать, а цикл замкнуть на шаг 06. Тогда не понадобятся и шаги 35-37 (правда, в этом случае числа больше 99999999 обрабатываться не будут). Это сокращение предложил arvi в ходе рассмотрения промежуточных вариантов.

Также заметим, что алгоритм получения остатка из самой первой версии программы короче используемого на 1 шаг. Его мы и вставим, получая 35 шагов и 4 регистра памяти.

00.П1  01.8    02.П0   03.Fex 04.П3  05.Сх   06.КП3 07.ИП1 08.ИП1  09.1
10.6   11.:    12.К[x] 13.П1  14.1   15.6    16.х   17.-   18.1    19.0
20.-   21.Fx≥0 22.25   23.7   24.+   25.5    26.8   27.+   28.FL0  29.06
30.ИП3 31.РРП  32.90   33.27  34.С/П

Дальнейшие возможные пути сокращений.

Существует также альтернативный вариант блока 18-27. К сожалению, он имеет ту же длину, что и применяемый.
18.8 19.- 20.П2 21.6 22.3 23.+ 24.FL2 25.28 26.7 27.-

Можно ли заменить этот блок функцией? Пока мне это не удалось. Например, следующая аппроксимация занимает на 1 шаг больше (11 шагов вместо 10).
18.В1 19.ВП 20.1 21./-/ 22.К[x] 23.7 24.х 25.+ 26.4 27.8 28.+

Undefined

Комментарии

Сократить подпрограмму (кстати, она занимает 62 шага и написана неоптимально) можно. Но требуется лишь написать программу, которая была бы меньше неё. Надеюсь, что принципиально другой алгоритм позволит уменьшить размер подпрограммы в несколько раз.

Получилось 47 шагов + нет ошибки при целочисленном делении.

Про иной алгоритм, ты случайно не имел в виду завязки на двоично-десятичное представление?
Возможно, это было бы проще (BCD -> Bin -> Hex), но тут нужны конкретные хаки уровня сдвига битов. В руководстве я сходу не нашел, а в старых моделях такого не было.

На 8086 конкурировали два алгоритма. Я реализовал со старших нибблов к младшим, т.к. его мало кто программирует. Более популярен алгоритм остатков (его реализовал a_avl), но он даёт нибблы в обратном порядке (их надо либо записывать в буфер, либо устраивать рекурсию).

Насчёт двоично-десятичного представления, интересная идея. Некоторые регистры занимаются преобразованием чисел. Например, R9038 преобразует число в двоичный формат FLOAT. Можно ли из этого вытянуть что-нибудь, полезное для Грааля, я пока не задумывался.

Сейчас аврал, надо погонять твою программу и проверить-подсократить программу a_avl. (Добавлено: О! Ещё Чёрная Королева обещанный результат предоставила, и всё сегодня.) Кажется, что большинство любителей МК-152 программирует на выходных.

Почитал интересные возможности (правда я не понял, как доступиться к универсальному байтовому буферу, примеров в доке явно не хватает).
Мне кажется, можно было бы сделать BCD -> Bin, а потом потетрадно вывести шестнадцатеричное число.
Правда не факт, что BCD -> Bin будет коротким (см Two-Byte Unpacked BCD to Binary и обратные Binary to BCD Shift и Add-3 Algorithm).

BCD в BIN переводит функция R9038. Здесь экономия потребуется при обращении к функциональным регистрам для перевода, считывания результата, для алгоритма преобразования BIN в ASCII HEX и его вывода.

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

У меня почему-то не работает программа. Выдаёт странные числа, а строка комментариев пустует.

Пожалуйста, если не трудно, проверьте правильность программы. Я, честно, всё правильно ввожу и у меня не работает. Может, всё-таки там какая-то опечатка?

Исправления. Внес исправления
См. также сообщение
http://pmk.arbinada.com/node/39#comment-100

Теперь работает. Правда, она отображает лишний нолик перед однозначными шестнадцатиричными числами. Но, наверное, так и долнжо быть.

Это не баг, это фича (feature) :))

Прогнал программу, выявил следующие ошибки. PPП9027 требует адреса строки вывода в стеке. Ну и команда КЭКР не нужна, при С/П экран обновляется автоматически.

К сожаленнию в вопросе прогона и корректировки "по месту" пока могу только положиться на тебя.

Зубы не заговаривай, программу давай! :-) Кстати, так моя мама и работала на "больших" ЭВМ. Отдавала программу операторам на перфокартах, они ей приносили распечатки. Ответ машины на бумаге: где какие ошибки или результат вычислений.

Исправил. Если я тебя правильно понял, то надо изменить только блок вывода

30.ИП0 31.РРП 32.90 33.27

Простой алгоритм, кстати, может сработать. Т.к. разрядов всё-таки 12. Единственное, что после деления нужно прибавить небольшое число (10^-10 или побольше), чтобы из-за незначительных ошибок K[x] не отбросила дробную часть вида ,99999999.

Если добавлять к числу какую-то дельту абсолютной погрешности, то это сожрет сэкономленные шаги. Да и не вполне ясно, всегда ли будет достаточно этого числа. Например, для 99999999 нужно прибавлять 0,4.
Похоже, функция нелинейна, константой не обойтись, т.е. надо вычислять дельту относительной погрешности, а это еще шаги.

Я и добавлял, в "затравке". А второй вариант не я, а какой-то аноним написал. Я просто подсократил его, как и ты.

Кстати, если это ИП2 используется лишь дважды, то может нам нафик занимать регистр 2 не сдалось?

Да можно заменить на FBx и XY
P.S. Стек "уходит", т.е. в лоб не пойдет, надо еще что-то в него включить...

08.1 09.6 10.: 11.К[x] 12.П1 13.FBx 14.K{x} 15.1 16.6 17.*

21.Fx≥0 22.24 23.7 24.+ 25.5 26.8 27.+

А здесь точно условный переход на 24, а не 25?

На 25. Ошибся, видимо