Бесконечное слово Фибоначчи является специфическим, бесконечная последовательность двоичных цифр, которые вычисляются путем многократного конкатенации конечных двоичных слов.

Определим , что последовательность слов Фибоначчи типа (или FTW последовательность ) является любая последовательность ⟨W _п ⟩ , который формируется следующим образом .

• Начните с двух произвольных массивов двоичных цифр. Назовем эти массивы W _-1 и W ₀ .

• Для каждого n> 0 пусть W _n ≔ W _n-1 ∥ W _n-2 , где ∥ обозначает конкатенацию.

Следствием рекурсивного определения является то, что W _n всегда является префиксом W _{n + 1} и, следовательно, всех W _k таких, что k> n . В некотором смысле, это означает последовательность ⟨W _п ⟩ сходится к бесконечному слову.

Формально, пусть W _∞ - единственный бесконечный массив, такой, что W _n является префиксом W _∞ для всех n ≥ 0 .

Мы будем называть любое бесконечное слово, образованное описанным выше процессом, бесконечным FTW .

задача

Напишите программу или функцию, которая принимает два двоичных слова W _-1 и W _{0 в} качестве входных данных и печатает W _∞ , соблюдая следующие дополнительные правила:

• Вы можете принять слова в любом порядке; как два массива, массив массивов, две строки, массив строк или одна строка с разделителем по вашему выбору.

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

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

  В частности, это означает, что любой вывод в STDOUT или STDERR, который является результатом сбоя, будет игнорироваться.

• Если я запускаю ваш код на моей машине (Intel i7-3770, 16 ГБ ОЗУ, Fedora 21) в течение одной минуты и направляет вывод на него wc -c, он должен вывести не менее миллиона цифр W _∞ для (W _-1 , W ₀ ) = (1, 0) .

• Применяются стандартные правила игры в гольф .

пример

Пусть W _-1 = 1 и W ₀ = 0 .

Тогда W ₁ = 01 , W ₂ = 010 , W ₃ = 01001 , W ₄ = 01001010 … и W _∞ = 010010100100101001010… .

Это бесконечное слово Фибоначчи.

Контрольные примеры

Все контрольные примеры содержат первые 1000 цифр бесконечного FTW.

Input:  1 0
Output: 0100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001

Input:  0 01
Output: 0100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001

Input:  11 000
Output: 0001100000011000110000001100000011000110000001100011000000110000001100011000000110000001100011000000110001100000011000000110001100000011000110000001100000011000110000001100000011000110000001100011000000110000001100011000000110000001100011000000110001100000011000000110001100000011000110000001100000011000110000001100000011000110000001100011000000110000001100011000000110001100000011000000110001100000011000000110001100000011000110000001100000011000110000001100000011000110000001100011000000110000001100011000000110001100000011000000110001100000011000000110001100000011000110000001100000011000110000001100000011000110000001100011000000110000001100011000000110001100000011000000110001100000011000000110001100000011000110000001100000011000110000001100011000000110000001100011000000110000001100011000000110001100000011000000110001100000011000000110001100000011000110000001100000011000110000001100011000000110000001100011000000110000001100011000000110001100000011000000110001100000011000110000001100000011

Input:  10 010
Output: 0101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010

Input:  101 110
Output: 1101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101

Pyth, 8 байт

u,peGsGQ

Ввод в форме "W-1", "W0".

Доказательство завершения:

$ time pyth -cd 'u,peGsGQ' <<< '"1", "0"' 2>/dev/null | head -c1000000 > /dev/null

real    0m0.177s
user    0m0.140s
sys 0m0.038s

Доказательство правильности:

Вот серия как внутренне сгенерированная. Он печатается в конкатенации программой.

[0, 10, 010, 10010, 01010010, 1001001010010,...]

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

[0, 1, 0, 01, 010, 01001, 01001010, 0100101001001, ...]

Мы хотим доказать, что они эквивалентны.

Очевидно, они одинаковы в течение первых нескольких шагов. Давайте сравним их немного позже:

010
  010

10010
  01001

01010010
  01001010

1001001010010
  0100101001001

Мы видим, что пары строк поочередно имеют форму:

01a 10b
a10 b01

Где a и b - произвольные последовательности на 0 и 1. Давайте немного продолжим последовательность, чтобы доказать, что она продолжается навсегда по индукции:

01a   10b   10b01a   10b01a10b
  a10   b01   a10b01   b01a10b01

2 шага спустя, он имеет правильную форму.

10b   01a   01a10b   01a10b01a
  b01   a10   b01a10   a10b01a10

2 шага спустя, он имеет правильную форму.

Таким образом, по индукции строки всегда совпадают после объединения.

Haskell, 15 байт

v%w=w++w%(v++w)

Инфиксная функция %создает бесконечную строку, которую Haskell печатает вечно, потому что Haskell такой крутой.

>> "1"%"0"
"010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101

Рекурсивная идея похожа на решение Згарба . Написание fдля функции %и +для конкатенации строк, это реализует:

f(v,w) = w + f(w,v+w)

Бесконечная выходная строка начинается с w, а остаток от нее является результатом для строк со смещением Фибоначчи wи v+w.

Это не проблема генерировать миллион символов в минуту.

Haskell, 31 байт

w#v=v++drop(length v)(v#(v++w))

Это определяет инфиксную функцию, #которая принимает две строки и возвращает бесконечную строку. Использование:

> let w#v=v++drop(length v)(v#(v++w)) in "11"#"000"
"000110000001100011000000110000...

Если я запрашиваю миллионный элемент последовательности, определенной «1» и «0», даже онлайн-интерпретатор печатает результат менее чем за секунду:

> let w#v=v++drop(length v)(v#(v++w)) in ("1"#"0") !! 1000000
'0'

объяснение

w#v=                             -- The result of w#v is
    v++                          -- v concatenated to
                      v#(v++w)   -- the infinite word v#(v++w),
       drop(length v)            -- with the first v characters dropped.

По сути, мы знаем, что w#v == v#(v++w)и начинаем w#vс них v, и используем эти факты для определения результата. Поскольку Haskell ленив, это «волшебно» просто работает.

Пип, 8 байт

Эй, связан с Пифом!

(fOba.b)

Простое рекурсивное определение заимствовано из ответа Ханора на xnor . С пробелами, добавленными для ясности:

(f Ob a.b)

Каждая программа в Pip является неявной функцией, которая принимает аргументы командной строки в качестве аргументов (назначенных переменным aчерез e) и печатает свое возвращаемое значение. Oявляется оператором, который выводит, а затем возвращает свой операнд, поэтому первое, что здесь происходит, это второй аргумент, который отображается (без завершающего перевода строки).

Теперь, вдохновленный Lisp синтаксис (f x y)в Pip - это вызов функции, эквивалентный f(x,y)в C-подобных языках. fПеременная относится к текущей функции - в этом случае, программа верхнего уровня. Таким образом, программа рекурсивно вызывает себя с bиa.b в качестве новых аргументов.

Я был приятно удивлен, обнаружив, что такой подход достаточно быстр:

dlosc@dlosc:~$ time pip -e '(fOba.b)' 1 0 2>/dev/null | head -c1000000 > /dev/null

real    0m0.217s
user    0m0.189s
sys     0m0.028s

На моем компьютере с Ubuntu требуется около 30 секунд, чтобы программа достигла максимальной глубины рекурсии, после чего она распечатала где-то более миллиарда цифр.

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

W1Sba.:Ob

CJam, 12 11 байтов

llL{@_o+_}h

Это займет два слова в отдельных строках, в обратном порядке, например

0
1

дает

0100101001001010010100100101001...

объяснение

Идея состоит в том, чтобы создать слово наивно (запомнив текущее слово и добавив к нему предыдущее), и пока мы это делаем, мы печатаем все, что только что добавили (чтобы не повторять префикс, который уже был напечатан) , Чтобы избежать необходимости обрабатывать начальную точку отдельно, мы начинаем с пустого слова, так что W ₀ - это первое, что мы добавляем (и печатаем).

ll    e# Read the two lines separately.
L     e# Push an empty string.
{     e# Infinite loop...
  @   e#   Pull up the previous FTW.
  _o  e#   Print it.
  +_  e#   Append it to the current FTW and duplicate it.
}h

PowerShell, 97 76 байт

param($a,$b)write-host -n $b;while(1){write-host -n $a;$e=$b+$a;$a=$b;$b=$e}

_{Редактировать - ммм, выписывание $e.substring($b.length)после того , как мы только что соединились, $aи все $bравно, что выписать просто$a соединились ... сумасшедшего.}

Вау, многословно. По умолчанию PowerShell выдает новую строку каждый раз, когда вы что-то выводите. Действительно, единственный способ обойти это с write-host -n(сокращенно -NoNewLine), и это абсолютно убивает длину здесь.

По сути, это повторяет последовательность, создавая $e«текущий» W _n, как мы идем. Однако, поскольку мы хотим построить бесконечное слово вместо последовательности, мы используем наши предыдущие переменные, чтобы распечатать суффикс, $aкоторый был заполнен в нашем предыдущем цикле. Затем мы устанавливаем наши переменные для следующего обхода и повторяем цикл. Обратите внимание, что это предполагает, что входные данные будут явно разделены в виде строк, иначе +оператор будет использоваться для арифметики вместо конкатенации.

Пример:

PS C:\Tools\Scripts\golfing> .\infinite-ftw.ps1 "111" "000"
0001110000001110001110000001110000001110001110000001110001110000001110000001110001110000001110000001110001110000001110001110000001110000001110001110000001110001110000001110000001110001110000001110000001110001110000001110001110000001110000001110001110000001110000 ...

APL, 24 18

{(,/⌽⍵),⊂⍞←↑⍵}⍣≡⍞⍞

Использование формулировки xnor позволило сбрить несколько персонажей.

                 ⍞  ⍝ Read W₋₁ as a character string.
                ⍞   ⍝ Read W₀.
{            }⍣≡    ⍝ Apply the following function repeatedly until fixpoint:
                    ⍝ It takes a pair of strings (A B),
         ⍞←↑⍵       ⍝ prints A
 (,/⌽⍵),⊂  ↑⍵       ⍝ and returns (BA A).

На бесконечной машине за бесконечное время она фактически напечатала бы W _∞ трижды - сначала постепенно, во время выполнения цикла, а затем дважды в результате всего выражения, когда ⍣≡оператор fixpoint наконец возвращается.

Это не очень быстро, но достаточно быстро. В GNU APL:

$ printf '%s\n' '{(,/⌽⍵),⊂⍞←↑⍵}⍣≡⍞⍞' 1 0 | apl -s | head -c 100
0100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010$
$ time printf '%s\n' '{(,/⌽⍵),⊂⍞←↑⍵}⍣≡⍞⍞' 1 0 | apl -s | head -c 1000000 >/dev/null
    0m3.37s real     0m2.29s user     0m1.98s system

Чистая Баш, 58

a=$1
b=$2
printf $b
for((;;)){
printf $a
t=$b
b+=$a
a=$t
}

У меня заканчивается память до 1 минуты, но к тому времени у меня много цифр - через 10 секунд у меня 100 миллионов цифр:

$ ./ftw.sh 1 0 | head -c100
0100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010ubuntu@ubuntu:~$ 
$ { ./ftw.sh 1 0 & sleep 10 ; kill $! ; } | wc -c
102334155
$ 

Mathematica, 56 байт

$IterationLimit=∞;#0[$Output~WriteString~#2;#2,#<>#2]&

С 76 (ГЦК)

main(c,v)char**v;{int p(n){n>2?p(n-1),p(n-2):puts(v[n]);}for(p(4);;p(c++));}

Это довольно простой рекурсивный принтер, реализованный как вложенная функция (расширение GNU C, не поддерживаемое clang), чтобы избежать необходимости vобхода. p(n)печатает W _n-2 , где W _-1 и W ₀ должны быть указаны в v[1]и v[2]. Это изначально вызывает p(4)для печати W ₂ . Затем он зацикливается: он вызывает p(3)печать W ₁ , делая полный вывод W ₂ W ₁ , который равен W ₃ . Затем он вызывает p(4)для печати W ₂ , делая полный вывод ₄ W и т. Д. Производительность немного лучше, чем мой предыдущий ответ: я вижу 1875034112 значений в минуту.

С, 81 (лязг)

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

s[],*p=s;main(c,v)char**v;{for(++v;;)for(puts(v[*++p=*++p!=1]);*p+1==*--p;++*p);}

Это имеет все виды неопределенного поведения, в основном для развлечения. Он работает с clang 3.6.2 в Linux и clang 3.5.2 в Cygwin для тестовых случаев, о которых идет речь, со специальными параметрами командной строки или без них. Он не ломается, когда оптимизация включена.

Это не работает с другими компиляторами.

Вы можете принять слова в любом порядке; как два массива, массив массивов, две строки, массив строк или одна строка с разделителем по вашему выбору.

Я принимаю слова в качестве аргументов командной строки в формате строки.

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

Я использую новую строку в качестве последовательного разделителя.

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

В частности, это означает, что любой вывод в STDOUT или STDERR, который является результатом сбоя, будет игнорироваться.

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

Если я запускаю ваш код на моей машине (Intel i7-3770, 16 ГБ ОЗУ, Fedora 21) в течение одной минуты и направляет вывод на него wc -c, он должен вывести не менее миллиона цифр W _∞ для (W _-1 , W ₀ ) = (1, 0) .

При тестировании с использованием { ./program 1 0 | tr -d '\n' & sleep 60; kill $!; } | wc -cя получаю 1816784896 цифр за одну минуту на моей машине, когда программа была скомпилирована -O3, и 1596678144, когда она была скомпилирована с оптимизацией.

Ungolfed, нет UB, с объяснением:

#include <stdio.h>

// Instead of starting with -1 and 0, start with 0 and 1. I will use lowercase w for that,
// so that wx = W(x-1).

// Declare a variable length array of numbers indicating what has been printed.
// The length is indicated through a pointer just past the end of the values.
// The first element of the array is a special marker.
// [0 3 1] means that w3 w1 has been printed.
// The array is initialised to [0] meaning nothing has been printed yet.
int stack[99999];
int *ptr = stack + 1;

int main(int argc, char *argv[]) {
  ++argv; // Let argv[0] and argv[1] refer to w0 and w1.
  for(;;) {
    // Determine the word to print next, either 0 or 1.
    // If we just printed 1 that wasn't the end of a different word, we need to print 0 now.
    // Otherwise, we need to print 1.
    int word = ptr[-1] != 1;

    // Print the word, and mark the word as printed.
    puts(argv[word]);
    *ptr++ = word;

    // If we just printed w(x) w(x-1) for any x, we've printed w(x+1).
    while (ptr[-1] + 1 == ptr[-2]) {
      --ptr;
      ++ptr[-1];
    }
  }
}

Javascript (53 байта)

(a,c)=>{for(;;process.stdout.write(a))b=a,a=c,c=b+a;}

Входные данные должны быть строковыми, а не числовыми ( '0'и не только 0).

Perl 5, 45 55 49 байтов

44 байта, плюс 1 для -E вместо-e

sub{$i=1;{say$_[++$i]=$_[$i].$_[$i-1];redo}}

Используйте как например

perl -E'sub{$i=1;{say$_[++$i]=$_[$i].$_[$i-1];redo}}->(1,0)'

Это печатает последовательные приближения к W _∞ и, таким образом, если вы будете ждать достаточно долго, печатает в последней строке вывода, W _∞ на любую желаемую длину, как требуется. Цифры слова объединяются без разделителя.

Так как я на Windows, я проверил его на "по крайней мере один миллион разрядов W _∞ », запустив его с перенаправленным выводом в файл и убив его примерно через 59 секунд, затем запустив GnuWin32.wc -L , который напечатал 701408733.

Обновить:

ОП пояснил в комментарии к этому ответу (и, вероятно, я должен был все равно понять), что дополнительный вывод, предшествующий W _∞, дисквалифицирует вышесказанное. Итак, вместо этого есть 55-байтовое решение, которое печатает только W _∞ :

sub{print$_[0];{print$_[1];unshift@_,$_[0].$_[1];redo}}

Используется так же, но с аргументами в обратном порядке , и не требует-E :

perl -e'sub{print$_[0];{print$_[1];unshift@_,$_[0].$_[1];redo}}->(0,1)'

Несомненно, это может быть дальше, но я не вижу, как это сделать прямо сейчас.

Дальнейшее обновление:

Деннис побрил пять байтов, используя -a(таким образом читая, <>чтобы удалить sub) и переназначая параметр, переданныйprint в концеredo блока:

С -aneи чтение из <>(оба входа в одной строке, через пробел, в обратном порядке); 48 + 2 байта:

$_=$F[0];{print;unshift@F,$F[0].($_=$F[1]);redo}

И, исходя из этого, я побрил еще один байт (так же, как и выше, но теперь входы в правильном порядке); 47 + 2 байта:

$_=$F[1];{print;push@F,$F[-1].($_=$F[-2]);redo}

REXX , 48

arg a b
do forever
b=a||b
say b
a=b||a
say a
end

ftw.rex
exec ftw.rex 0 1

В настоящее время не могу проверить производительность, потому что я использовал онлайн-компилятор, чтобы написать его. «Навсегда» можно заменить на любое число, где в качестве напечатанных номеров ftw (число + 2).

Я также написал небольшое (грязное) решение в Прологе. Не знаю, как проверить производительность с этим, но, вероятно, в любом случае это ужасно.

f(A,B,C):-atom_concat(B,A,D),(C=D;f(B,D,C)).

:- C='0';C='1';(f(1,0,C)).

Python 2, 67 байт

a,b=input()
print'\n'.join(b+a)
while 1:a,b=b,b+a;print'\n'.join(a)

Принимает ввод как разделенную запятыми пару строк: "1","0"для примера в вопросе.

Нет онлайн-переводчика, потому что бесконечные циклы плохие. Буферизованный вывод заставил меня набрать много байтов. :( Спасибо Деннису за то, что он указал, что 1 цифра в строке действительна.

Сроки на моей (значительно более слабой) машине:

$ time python golf.py <<< '"1","0"' 2>/dev/null | head -c2000000 > /dev/null

real    0m1.348s
user    0m0.031s
sys     0m0.108s

Дьялог АПЛ, 9

{⍵∇⍺,⍞←⍵}

Этот использует ∇для определения рекурсивной функции. Это прямой перевод этого xnor's Python 3 ответа . Он принимает W _{0 в} качестве правого и W _{-1 в} качестве левого аргумента, оба должны быть символьными векторами.

Минколанг 0,11 , 62 байта

(od" "=,6&xI0G2@dO$I)I1-0G($d2[I2:g]Xx0c2*1c-0g0g-d[icO]0G0G1)

Попробуй это здесь. Ожидается ввод в порядке W ₀ , W _-1 с пробелом между ними.

объяснение

(                             Open while loop (for input-reading)
 od                           Read in character from input and duplicate
   " "=,                      0 if equal to " ", 1 otherwise
        6&                    Jump 6 characters if this is non-zero
          xI0G2@              Dump, push length of stack, move to front, and jump next two
                dO            Duplicate and output as character if 1
                  $I)         Close while loop when input is empty
                     I1-0G    Push length of stack - 1 and move it to the front

Мета-объяснение следующего заключается в том, что на данный момент у нас есть два числа, за которыми следует строка «0» и «1» без разделения. Если длины W ₀ и W _-1 равны aи b, соответственно, то два числа в начале стека равны <a+b>и <a>, в этом порядке. Слово, образованное объединением W _{i + 1} и W _i , то есть W _{i + 1} + W _i , равно 2 * W _{i + 1} - W _i . Таким образом, следующий код дублирует стек (2 * W _{i + 1} ), выскакивает сверху<a> элементов (- W _я ), а затем заменяет <a+b>и <a>со своими преемниками, <a+2b>и <b>.

(                                       Open while loop (for calculation and output)
 $d                                     Duplicate the whole stack
   2[I2:g]                              Pull <a+b> and <a> from the middle of the stack
          Xx                            Dump the top <a> elements (and <a+b>)
            0c2*1c-                     Get <a+b> and <a>, then calculate
                                        2*<a+b> - <a> = <a+2b> = <a+b> + <b>
                   0g0g-                Get <a+b> and <a>, then subtract
                        d[icO]          Output as character the first <b> elements
                              0G0G      Move both to front
                                  1)    Infinite loop (basically, "while 1:")

Python 3, 32

def f(a,b):print(end=b);f(b,a+b)

Та же рекурсивная идея, что и в моем ответе на Haskell , за исключением того, что префикс напечатан, потому что Python не может обрабатывать бесконечные строки.

Использовал трюк из Sp3000 для печати без пробелов, поместив строку в качестве endаргумента в Python 3

Perl, 32 байта

#!perl -pa
$#F=3}for(@F){push@F,$F[-1].$_

Считая Шебанг как два, ввод берется из стандартного ввода, пространство отделяется как W ₀ , W _-1 . Вывод для 1 МБ раз в ~ 15 мс, большинство из которых можно отнести к запуску интерпретатора.

Образец использования

$ echo 0 1 | perl inf-ftw.pl
0100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001001010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001001010010100100101001001010010100100101001010010010100100101001010010010100100101001010010010100101001001010010010100101001001010010100100101001001...

$ echo 110 101 | perl inf-ftw.pl
1101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101101011101011101101011101101011101011101101011101011101101011101...

Пролог, 69 байт

q(A,B):-atom_concat(B,A,S),write(A),q(B,S).
p(A,B):-write(B),q(A,B).

Пример ввода: p ('1', '0')

Не удалось удалить лишнюю запись.
Должен быть в состоянии улучшить это, если я пойму, как это сделать.