В качестве первой задачки для реализации на brainfuck я решил взять, казалось бы, простое упражнение — вывести в десятичном формате записанное на ленте 4-байтовое число. Задачка оказалась интересной, особенно, если учесть, что дублировать код (и использовать, что число именно 4-байтовое) мне хотелось как можно меньше, а больше пользоваться циклами.
Сразу было видно, что есть два разных подхода — либо пытатьтся делить исходное число с остатком на 10, и составлять цифры из полученных остатков, либо формировать десятичное число, умножая его на 2 и при необходимости прибавляя единицу. Поигравшись со вторым вариантом, и обнаружив, что биты поступают не в том порядке, в каком надо, вернулся к первому варианту.
Проблем было две — первое: избежать возникновения ведущих нулей, второе: написать деление с остатком «длинного» числа на 10. Вторая задача, очевидно, сводится к делению двухбайтового числа, меньшего 2560… Но перейдем сразу к программе.
Сначала ввод. В принципе, он не нужен (по условию, число уже записано на ленте), но надо же как-то отлаживать
,>,>,>,<<<
Чтобы можно было использовать цикл по исходным данным, введем дополнительную разметку
<+>
>>>[->>>+<<<]<
[->>+<<]<
[->+<]
+>>+>>+
Между байтами исходного числа и слева от левого байта стоят единицы. Каретка — на самой правой единице (между двумя младшими байтами). Начинаем главный цикл. С этого момента длина исходных данных нигде не используется.
Сначала найдем начало числа
[[<<]>>
Теперь будем сдвигать каждую цифру на 4 ячейки влево, и на освободившемся пространстве делить число, составленное из предыдущего остатка и новой цифры, на 10:
[->[-<<<<+>>>>]<<<<<
[->>+>+<<<]>>+
[-<[->>+>++++++++++<[->->+<<]+>[-<[-]>]<[->>[-]<<<<<+>>>]>>[-<<+>>]<<<<]->]
Здесь используется тот факт, что (a*256+b)/10=((a*255+b)+a)/10, и что a<10.
После того, как частное и остаток найдены, надо проверить — не получился ли ведущий ноль. Если получился, то метку «1» между найденным и следующим байтами не ставим.
<+<[->+>+<<]
>>[-<<[-]+>>]<<<<[->>[-]+>>+<<<<]>>>>
[-<<<<+>>>>]>[-<+>]>>>]
Когда число кончилось, последний найденный остаток — это новая цифра. Приписываем ее к строке вывода
<++++++[->++++++++<]<<<[->>>>+<<<<]
и сдвигаем цифры найденного на этом шагу частного на 3 байта вправо (чтобы они были на правильном расстоянии от строки вывода)
<<[->[->>>+<<<]>>+<<<<<]>>>>>]
Если оказалось, что частного нет, цикл закончен — и можно выводить строку
>[.>]+++++++++++++.---.
Вот и все.
Получилось как-то громоздко — наверное, многих возможностей я еще не вижу.
Может быть, вариант с удвоением был бы лучше — но для него исходные цифры надо было бы не делить, и умножать на 2, и работать с битом переноса. Надо будет попробовать. Но этот вариант будет работать только когда число состояний «байта» — степень двойки (в приведенном выше коде этот факт не используется, программа будет работать с любым числом состояний, большим 10).
Сразу было видно, что есть два разных подхода — либо пытатьтся делить исходное число с остатком на 10, и составлять цифры из полученных остатков, либо формировать десятичное число, умножая его на 2 и при необходимости прибавляя единицу. Поигравшись со вторым вариантом, и обнаружив, что биты поступают не в том порядке, в каком надо, вернулся к первому варианту.
Проблем было две — первое: избежать возникновения ведущих нулей, второе: написать деление с остатком «длинного» числа на 10. Вторая задача, очевидно, сводится к делению двухбайтового числа, меньшего 2560… Но перейдем сразу к программе.
Сначала ввод. В принципе, он не нужен (по условию, число уже записано на ленте), но надо же как-то отлаживать
,>,>,>,<<<
Чтобы можно было использовать цикл по исходным данным, введем дополнительную разметку
<+>
>>>[->>>+<<<]<
[->>+<<]<
[->+<]
+>>+>>+
Между байтами исходного числа и слева от левого байта стоят единицы. Каретка — на самой правой единице (между двумя младшими байтами). Начинаем главный цикл. С этого момента длина исходных данных нигде не используется.
Сначала найдем начало числа
[[<<]>>
Теперь будем сдвигать каждую цифру на 4 ячейки влево, и на освободившемся пространстве делить число, составленное из предыдущего остатка и новой цифры, на 10:
[->[-<<<<+>>>>]<<<<<
[->>+>+<<<]>>+
[-<[->>+>++++++++++<[->->+<<]+>[-<[-]>]<[->>[-]<<<<<+>>>]>>[-<<+>>]<<<<]->]
Здесь используется тот факт, что (a*256+b)/10=((a*255+b)+a)/10, и что a<10.
После того, как частное и остаток найдены, надо проверить — не получился ли ведущий ноль. Если получился, то метку «1» между найденным и следующим байтами не ставим.
<+<[->+>+<<]
>>[-<<[-]+>>]<<<<[->>[-]+>>+<<<<]>>>>
[-<<<<+>>>>]>[-<+>]>>>]
Когда число кончилось, последний найденный остаток — это новая цифра. Приписываем ее к строке вывода
<++++++[->++++++++<]<<<[->>>>+<<<<]
и сдвигаем цифры найденного на этом шагу частного на 3 байта вправо (чтобы они были на правильном расстоянии от строки вывода)
<<[->[->>>+<<<]>>+<<<<<]>>>>>]
Если оказалось, что частного нет, цикл закончен — и можно выводить строку
>[.>]+++++++++++++.---.
Вот и все.
Получилось как-то громоздко — наверное, многих возможностей я еще не вижу.
Может быть, вариант с удвоением был бы лучше — но для него исходные цифры надо было бы не делить, и умножать на 2, и работать с битом переноса. Надо будет попробовать. Но этот вариант будет работать только когда число состояний «байта» — степень двойки (в приведенном выше коде этот факт не используется, программа будет работать с любым числом состояний, большим 10).
