Секция Фибоначчи. странные формы вывода (Haskell)

Я наблюдал за результатами реализации последовательности Fibobacci в Haskell, когда я понял некоторые "странные" формы в оптации чисел.

Прежде всего, это код Haskell, который я придумал:

fib :: Integer -> [Integer]
fib 0 = [0]
fib 1 = [0, 1]
fib a = (fib' 0 1 [0,1] 1 a)

fib' :: Integer -> Integer -> [Integer] -> Integer -> Integer -> [Integer]
fib' n1 n2 l cont n 
        | cont == n = l
        | otherwise = (fib' n2 n3 (l++[n3]) (cont+1) n)
             where n3 = n2 + n1

Для чего-то вроде fib 10 выход будет: [0,1,1,2,3,5,8,13,21,34,55] Затем я хотел попробовать что-то вроде fib 1000, в то время как числа невероятно большие и все... то, что я увидел, было каким-то странным elipses, образованным ",", который распечатывается между каждым Integer из списка, например:

example1

Итак, я увеличил размер окна вывода, чтобы увидеть, будет ли этот странный шаблон повторяться, и ответ "да":

example2

И мой вопрос:

Кто-нибудь знает, почему появляется этот шаблон в "," между целыми числами из списка? Разве это не должно быть более случайным и менее похожим на elipses?

Ответ 1

Числа Фибоначчи растут как экспоненциальная функция n.

Длина числа в десятичном значении - это, по существу, его логарифмическая база 10. Таким образом, длина Фибоначчи растет как линейная функция от n, поскольку логарифм и экспоненциально отменяют друг друга.

Таким образом, если вы напечатали их в столбце, вы увидите прямую линию. Но вы печатаете их один за другим, поэтому позиции накапливаются. Если вы принимаете кумулятивные суммы линейной последовательности, вы получаете квадратичную последовательность.

Локально каждая строка содержит примерно то же число чисел Фибоначчи, назовем ее k. Это означает две вещи:

Номер строки изменяется линейно с n.
Чтобы вычислить реальные позиции запятых (относительно левого края окна), нам нужно взять оставшуюся часть кумулятивного "абсолютного положения" по модулю длины линии. Это эквивалентно (в среднем) вычитанию 1/k за каждый приращение n. Эта настройка является линейной и не меняет квадратичное поведение позиции.

Итак, вы видите параболу - график квадратичной функции.

Ответ 2

Нет ничего странного, когда вы задумываетесь об этом. Соседние числа Фибоначчи имеют одинаковую длину, а длина увеличивается с последовательностью. Предположим, у вас есть размер экрана 30 символов, а текущий F(n) имеет 29 цифр, а для следующих нескольких чисел длина может быть:

29, 29, 29, 30, 30, 30, 31, 31, 31

Который дает вам левое → стабильное → правое движение.