Фибоначчи на собеседовании

    Вычисление ряда Фибоначчи — это классическая алгоритмическая задача, потому её нередко дают на собеседованиях, когда хотят проверить, что кандидат в принципе хоть как-то умеет в алгоритмы. Предположим, вы тот самый кандидат. Вам дали задание: на языке JavaScript написать функцию fib(n), возвращающую энное число Фибоначчи. Считаем, что нулевое число Фибоначчи — это нуль. Проверка корректности аргумента не требуется. Какие у вас есть варианты?

    image

    1. Быть проще, и люди к вам потянутся.


    Самое простое решение — это банальный цикл.

    const fib = n => {
      let prev = 0, next = 1;
      while(n-- && (next = prev + (prev = next)));
      return prev;
    }
    

    Шутка. Разумеется, так писать не нужно — если, конечно, вы не собеседуетесь на должность штатного обфускатора.

    const fib = n => {
      let prev = 0, next = 1;
      for(let i = 0; i < n; i++){
        next = prev + next;
        prev = next - prev;
      }
      return prev;
    }
    

    У вас кончились талончики на переменные? cypok

    Ладно, ладно, для ещё большей читаемости напишем так:

    const fib = n => {
      let prev = 0, next = 1;
      for(let i = 0; i < n; i++){
        let temp = next;
        next = prev + next;
        prev = temp;
      }
      return prev;
    }
    


    Это — вариант классический, простой и элегантный. Но, возможно, вы хотите продемонстрировать своё знание ещё каких-то концепций? Например…

    2. Чтобы понять рекурсию, надо понять рекурсию


    Например, да, вы можете продемонстрировать, что умеете в рекурсию. Например, так:

    const fib = n => {
      if(n <= 1){
        return n;
      }else{
        return fib(n - 1) + fib(n - 2);
      }
    }
    

    Запомните этот вариант. Так делать не стоит. Не следует. Нельзя. Никогда. Это хуже, чем пинать щеночков, и сравнимо с небольшим холокостом.

    Возможно, вы спросите, почему. В таком случае просто запустите этот код и попытайтесь посчитать, скажем, пятидесятое число Фибоначчи. Полагаю, вы ощутите некую задержку. Шутка. Полагаю, если вы запускаете этот код не на суперкомпьютере, то попросту не дождётесь результата. При том, что простой, не рекурсивный код из предыдущих примеров посчитает пятидесятый член последовательности Фибоначчи быстрее, чем вы успеете произнести слово «пятьдесят» или любой его слог.

    Выражаясь грубым языком O-нотации, такое решение имеет временную сложность O(en). То есть — время выполнения этой функции растёт экспоненциально при увеличении n. То есть — когда n увеличивается на, время выполнения увеличивается в. Грубо говоря, если fib(45) вам пришлось ждать час, то fib(46) вы будете ждать два часа, fib(47) — 4 часа, и так далее. Я разжёвываю так подробно, чтобы каждый читатель, даже верстальщик, впервые попробовавший свои силы в написании скриптов, мог осознать ужас ситуации.

    Это правильно, но слишком грубо. Можно получить более точную оценку числа вызов функции ~(1+sqrt(5)) fib(n) и красивое замечание «Для вычисления числа Фибонначи наивным рекуррентным методом понадобится вызовов функции в 3.2 раза больше чем само число Фибонначи». Taus
    И мы получаем ещё один метод его вычисления. Надо просто запустить наивный рекурректный метод, подсчитать количество вызовов функции и разделить на 3.2! Cerberuser

    Если от вас на собеседовании потребуют рекурсивного решения этой задачи, скорее всего, это ловушка. «Правильная» рекурсия, работающая за линейное время, может выглядеть, например, так:

    const fib2 = n => {
      if(n == 0){
        return [0, 1];
      }else{
        const [prev, next] = fib2(n - 1);
        return [next, prev + next];
      }
    }
    
    const fib = n => fib2(n)[0];
    

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

    3. Мемная функция


    Существует волшебный способ, превращающий чудовищно неэффективное решение из прошлого параграфа в потенциально очень быстрое (хотя и не лишённое проблем). Имя ему — мемоизация. А если говорить по-русски — мы просто запоминаем результаты предыдущих вызовов вместо того, чтобы вычислять их заново.

    В принципе, мы можем даже ничего не менять внутри того решения — просто добавить функцию-обёртку memoize. Здесь я для наглядности использую её упрощённую версию для функции с единственным аргументом.

    //я изменил название функции, потому что заказчику мы отдадим не её, а её обёрнутую версию
    const oldFib = n => {
      if(n <= 1){
        return n;
      }else{
        return oldFib(n - 1) + oldFib(n - 2);
      }
    }
    
    const memoize = f => {
      const cache = {};
      return arg => cache[arg] || (cache[arg] = f(arg));
    }
    
    const fib = memoize(oldFib);
    

    Вуаля! Теперь функция fib имеет через замыкание доступ к объекту cache. Если её вызывают с аргументом, который ранее не встречался, вычисленное значение сохраняется в cache. При новых вызовах функции с тем же аргументом значение не придётся вычислять заново, оно будет просто взято из кэша. Основная проблема «плохой» старой функции fib была в том, что одни и те же значения в ней вычислялись заново несколько раз. Например, для вычисления fib(45) нужно было один раз вычислить f(44), два раза — f(43), три раза — f(42), пять раз — f(41), и так далее.

    Занимательный факт
    При использовании наивной рекурсии количества вычислений предыдущих чисел Фибоначчи сами являются числами Фибоначчи. Разве это не поразительно? На самом деле не очень. С числами Фибоначчи постоянно такое, в конце поста будет пример поинтереснее.

    Так вот, теперь предыдущие значения будут вычисляться по одному разу, а при их повторном запросе — просто браться из кэша. Представляете, во сколько раз быстрее мы сможем теперь вычислить сорок пятое число Фибоначчи? Серьёзно, как вы думаете, во сколько?

    На самом деле — чуть-чуть медленнее. Я сознательно допустил классическую ошибку, часто совершаемую при мемоизации рекурсивных функций. При вызове fib(45) «под капотом» вызывается oldFib(45), которая для своих нужд вызывает oldFib(44) и oldFib(43)… Вы чувствуете подвох? Здесь и далее идут уже вызовы обычной, не мемоизированной функции. Конечно, при повторном вызове fib(45) мы мгновенно получим результат из кэша — однако первый вызов ничуть не ускорился. Чтобы это поправить, придётся всё-таки влезть oldFib под днище с гаечным ключом:

    const oldFib = n => {
      if(n <= 1){
        return n;
      }else{
        return fib(n - 1) + fib(n - 2);
      }
    }
    
    const memoize = f => {
      const cache = {};
      return arg => cache[arg] || (cache[arg] = f(arg));
    }
    
    const fib = memoize(oldFib);
    

    Замечательно! Теперь первый вызов fib(45) отработает со скоростью, сравнимой с версией с циклом. А дальнейшие вызовы вообще сработают за константное время… Оп! Опять обманул. Получение значения свойства объекта по ключу — это операция быстрая, но всё-таки O(1) только в среднем, в худшем случае она может деградировать до O(n). Чтобы стало совсем хорошо, в нашем случае мы можем сменить тип cache с объекта на массив.

    Разумеется, не стоит также забывать, что мемоизация требует памяти. И пока мы уменьшаем сложность по времени, сложность по памяти растёт с O(1) до O(n).

    Как ещё мы можем выпендриться? Например, продемонстрировав своё глубокое знание математики

    4. Мистер Бине


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

    $F_n = \frac{\left(\frac{1 + \sqrt5}{2}\right)^n - \left(\frac{1 - \sqrt5}{2}\right)^n}{\sqrt5}$



    Однако довольно языка математики, запишем это на языке JavaScript:

    const fib = n => {
      const a = (1 + 5 ** 0.5) / 2;
      const b = (1 - 5 ** 0.5) / 2;
      return (a ** n  - b ** n) / 5 ** 0.5;
    }
    

    Прогоним на первых нескольких числах. Замечательно, кажется, всё работает. Вот 13, вот 21, вот 34, вот… 54.99999999999999?

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

    $F_n = \left\lfloor\frac{\left(\frac{1 + \sqrt5}{2}\right)^n}{\sqrt5}\right\rceil$



    Здесь странные недоделанные квадратные скобки означают ближайшее целое число, то есть — округление. Перепишем наш код:

    const fib = n => {
      const a = (1 + 5 ** 0.5) / 2;
      return Math.round(a ** n / 5 ** 0.5);
    }
    

    Да, так гораздо лучше. Мы сможем увидеть и 55, и 89, и даже моё любимое число Фибоначчи — 144 (которое я люблю за то, что оно равняется двенадцати в квадрате). Всё будет хорошо до числа за номером 76. Которое должно быть равно 3416454622906707, а наша функция вычислит 3416454622906706. Потому что проблема ограниченной точности дробных чисел никуда не делась, мы просто затолкали её поглубже и надеялись, что она не всплывёт. Как показывает данный пример — надеялись напрасно.

    На самом деле мы можем сделать ещё кое-что, чтобы спасти этот метод. Но об этом ниже. А пока — шутки в сторону. Поговорим о методе суровом, хардкорном и брутальном.

    5. Следуй за белым кроликом.


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

    Что касается чисел Фибоначчи, для них на матричном языке можно записать вот такое очевидное тождество:

    $\begin{pmatrix} 0 & 1\\ 1 & 1 \end{pmatrix} \begin{pmatrix} F_{n - 1}\\ F_n \end{pmatrix} = \begin{pmatrix} F_n\\ F_{n+1} \end{pmatrix}$



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

    $\begin{pmatrix} 0 & 1\\ 1 & 1 \end{pmatrix}^n \begin{pmatrix} 0\\ 1 \end{pmatrix} = \begin{pmatrix} F_n\\ F_{n+1} \end{pmatrix}$



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

    $\begin{pmatrix} 0 & 1\\ 1 & 1 \end{pmatrix}^n = \begin{pmatrix} F_{n-1} & F_{n}\\ F_{n} & F_{n+1} \end{pmatrix}$



    Замечательно, не правда ли? Осталось понять, нафига попу гармонь, если он не филармонь. В смысле — зачем такие сложности на ровном месте. А ответ прост — быстрое возведение в степень.

    Сколько нужно выполнить элементарных умножений, чтобы вычислить, скажем, 210? Нормальный человек скажет, что девять. Дважды два — четыре. Дважды четыре — восемь. Дважды восемь — шестнадцать. И так далее. Хитрый человек скажет, что четыре.

    $2 \cdot 2 = 4\\ 4 \cdot 4 = 16\\ 2 \cdot 16 = 32\\ 32 \cdot 32 = 1024$



    Программист скажет. что он это число помнит наизусть, и ничего умножать не нужно. Однако вопросы мемоизации мы рассмотрели выше.

    Так вот, быстрое возведение в степень применимо и к матрицам, и таким образом позволяет уменьшить асимптотическую временную сложность нашей функции с O(n) до O(log n). И это очень круто — если, конечно, нам действительно так важна эта сложность. Давайте напишем код:

    //здесь я использую таинства деструктуризации, чтобы записать матричное умножение почти как в учебнике алгебры
    const mul = (
      [
        [a1, a2], 
        [a3, a4]
      ],   
      [
        [b1, b2], 
        [b3, b4]
      ]) => 
      [
        [a1 * b1 + a2 * b3, a1 * b2 + a2 * b4],
        [a3 * b1 + a4 * b3, a3 * b2 + a4 * b4]
      ];
    
    const matrix = [
      [0, 1],
      [1, 1]
    ];
    
    //единичная матрица, не айдишник
    const id = [
      [1, 0],
      [0, 1]
    ]
    
    const fib = n => {
      let result = id;
      const bits = n.toString(2); 
      //да простят мне такой колхоз любители битовой магии
      for(const bit of bits){
        result = mul(result, result);
        if(bit == "1"){
          result = mul(result, matrix);
        }
      }
      return result[1][0];
    }

    Вот мы и получили самый быстрый алгоритм на Диком Западе. И его, в отличие от большинства предыдущих, можно неиронично продемонстрировать на собеседовании. А в каких-нибудь математико-ёмких местах именно его от вас и будут ждать.

    P. S.


    Я обещал ремарку относительно того, как же нам спасти метод, основанный на формуле Бине. Ответ кроется вот в этой моей статье. Там я для нужд народного хозяйства написал специальный класс корень-из-пяти-рациональных чисел, которые могут без потери точности хранить результаты арифметических действий над целыми числами и корнем из пяти. Можно взять этот класс, дополнить его методом округления и использовать для поиска чисел Фибоначчи по формуле Бине. А затем впрыснуть закись азота, применив быстрое возведение в степень.

    И что самое интересное: если внимательно посмотреть, какие числа будут получаться в процессе, какие будут выполняться операции, то станет понятно, что этот метод — это то же самое матричное умножение, только под другим фасадом. Разница лишь в том, храним мы числа в двумерных массивах или в полях объекта специального класса.

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

    Есть ещё такой способ как fast doubling. Работает как и матричное умножение за O(log), но с меньшей константой в асимптотике (и на практике). Если кратко, то там используется две формулы, опираясь на которые можно быстро рекурсивно откатываться к вдвое меньшим индексам:

    F2n = Fn * (2*Fn+1 – Fn)
    F2n+1 = Fn2 + Fn+12

    Реализация, кстати, получается довольно компактная.

    Сравнение скорости работы разных методов
    image

    just_maksim
    Поделиться публикацией

    Похожие публикации

    Комментарии 130

      +40
      1. Быть проще, и люди к вам потянутся.

          next = prev + next;
          prev = next - prev;
      

      У вас кончились талончики на переменные?
        +14
        Справедливо. Сейчас дополню)
        0
        У вас с memoize точно всё Ok? Вроде fib вызывает именно fib, а не betterFib — т.е. «обёртка» не сработает (я даже проверил на случай, что я чего-то не вижу — добавив в fib console.log)
        Кажется, для срабатывания memoize функцию fib надо записать иначе. Например, fib = memoize(n => {...})
          +2
          Я, кажется, плохо сформулировал эту часть, нарушив конвенцию, что функция-результат именуется fib. Я сейчас это перепишу.
            –1
            Всё ещё нет. Добавьте в oldFib console.log(n) и посмотрите сами.

            Грубо говоря, вам надо, чтобы oldFib вызывала memoize(oldFib). Этого можно добиться несколькими методами, но вот просто скормить готовую рекурсивную функцию вашей реализации memoize — точно не выйдет (а вот если записать fib = memoize(n => {...}) — получится автоматически)
              +2
              Заголовок спойлера
              const oldFib = n => {
                console.log(n);
                if(n <= 1){
                  return 1;
                }else{
                  return fib(n - 1) + fib(n - 2);
                }
              }
              
              const memoize = f => {
                const cache = {};
                return arg => cache[arg] || (cache[arg] = f(arg));
              }
              
              const fib = memoize(oldFib);
              
              fib(10);


              Консоль говорит: 10 9 8 7 6 5 4 3 2 1 0. Как и ожидалось.
                +1
                Тут у вас oldFib вызывает fib, а не себя — нормально. А в посте пока неправильно.
                Упс, пардон, я был невнимателен, прочитал в посте версию с ошибкой (как-то не ждёшь такого — особенно перечитывая пост, точнее, ища в нём «oldFib»), а что после неё шла нормальная — не сразу заметил.

                P.S. Порой на хабре хочется видеть историю правок поста, как в wiki.
                  +1
                  Так у меня в посте два варианта. Первый — с сознательно допущенной ошибкой, на которую я же и указываю. Второй — тот, который я написал сейчас.
          +2
          if(n <= 1){
          return 1;
          У вас формула неправильная. Fib(0) должно возвращать 0.
            +6
            У меня не формула неправильная, а ТЗ =) Я там выбрал нумерацию так, чтобы первые примеры читались проще. Хотя я уже успел об этом пожалеть в процессе написания поста. И, возможно, действительно надо это исправить. Но с другой стороны исправления придётся внести в тысячу мест. Я ещё подумаю.
              +4
              Исправил. Действительно, бес меня попутал с этой нестандартной нумерацией, из-за неё вторая половина статьи превратилась в ад. Если найдёте ошибки, напишите, пожалуйста.
              0
              тут был устаревший коммент
              +6
              Больше года назад откликнулся на вакансию «php-программист», прислали ТЗ и там было задание с Фибоначчи: выбрать все четные числа Фибоначчи в диапазоне от 1 до 10000. Решил с помощью цикла(for). Еще там нужно было SQL-запрос составить на выборку ближайших дней рождений пользователей, что-то сверстать, точно не помню и какую-то функцию написать. Все сделал, отправил. Прислали ответ: «по итогам тестового задания Вы не приняты». Что конкретно им не понравилось так и не написали. Вот сейчас сижу и думаю, наверное все-таки из-за Фибоначчи пролетел… :)
                +2
                Если указаны такие границы, то идеальным решением будет предрасчитанный массив, который и будет выводится. При этом расчет массива в ответ не стоит включать.
                const answer = [2, 8, 34,… ]
                print(answer)
                  0
                  идеальным решением
                  Идеальным для кого? Для компьютера и для кода — да. Но на работу с таким кодом точно не возьмут (поэтому неидеально для собеседуемого), поэтому и стараться так не надо было :)
                    –1
                    Возможно для микроконтроллеров это самый подходящий вариант, например таблицы синусов и косинусов хранят во флеш памяти, а не вычисляют. На рекурсию там может стека не хватить.
                  –4
                  Тестовые задания шлют когда хотят отшить, если вы понравитесь они пойдут на встречу без факторов которые могут оттолкнуть, я сейчас вообще не 1 не делаю сразу говорю давайте думать над альтернативой.
                    +1
                    Тестовые задания шлют когда хотят отшить


                    На чем основано это утверждение?
                      +3
                      Я предположу, что на том, что когда xPomaHx говорит «давайте думать над альтернативой», его постоянно отшивают?
                        0
                        Ну чаще всего да, и это норм, по моему опыту из 30 вакансий 25 вообще не нужен сотрудник в данный момент, какой бы крутой я не был, если тока не готов мб за бесплатно работать.
                        Да и потом смысл есть дальше разговаривать если я уже сейчас вижу абсолютную бескомпромиссность, можно изучить опыт крупных компаний как они проводят собесы, там нет тесовых заданий, есть или онлайн лайв кодинг, или совместное изучение кода твоих проектов, ну и потом чаще всего или тестовый раб день, или что то типа долгого собеседовочного дня где да нужно будет решать задачи.
                        Я готов к тестовому если оно оплачивается, но если ты пообщался в скайпе по телефону и тебе говорят давайте сделайте тестовое еще, то это значит что ты уже не нужен им, по разным причинам.
                        Если отказываются обобщатся, а с начало просят сделать тестовое значит им вообще не нужен сейчас никто, просто так базу набирают или повышают свою известность.
                      +1
                      Это утверждение имеет смысл, если оно о романтических отношениях)
                    +1

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

                      +2

                      Что то я опять накосячил, при диагонализации должна получиться как раз формула Бине.
                      Не получится ускорится таким способом.

                        0
                        Ну, можно ускориться, если учитывать симметрию матрицы и не считать третий элемент.
                      –9
                      Знаете… Я наверное покажусь слишком токсичным, но:

                      1. У вас первая функция (остальные не проверял) не работает на отрицательном полупериоде
                      2. Одна из функций неверно возвращала значение при нуле — об этом уже выше написали
                      3. За использование стрелочных функций везде где только можно (а особенно в туторе) надо отрывать руки
                      4. Компанию, где на собеседовании такое спрашивают на должность программиста, а не рокетсайенс или сайенс, надо обходить стороной


                        +8
                        1. Вы ещё скажите, что функцию надо аналитически продолжить на всю комплексную плоскость)
                        2. Да, тут была путаница, я вроде исправил.
                        3. А чем плохи стрелочные функции?
                          –6
                          п1 — не надо возводить все до абсурда, если в ТЗ не оговорено ничего сверх, то речь об рациональной плоскости, и фя Фибоначчи должна работать на всей ней.

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

                            И чему же равно Pi**e-тое число Фиббоначчи?)

                              +8
                              Пи в степени е — не рациональное число. Корректнее было бы спросить, чему равно число Фибоначчи под номером полтора. Его можно вычислить по формуле Бине. Правда, оно получится комплексным.
                                +8
                                Пи в степени е — не рациональное число
                                — судя по вики, одна из открытых математических проблем: про пи в степени e неизвестно, является ли оно рациональным или нет. Не знаю, специально Вам такое число сказали или нет, просто глаз зацепился.
                                  +6
                                  Чёрт. Это было тонко, а я не заметил. Старею.
                                    0
                                    Судя по Вики
                                    число вида a^b где a — алгебраическое число, отличное от 0 и 1, а b — иррациональное алгебраическое число, всегда является трансцендентным

                                    Со ссылкой на Гильберта
                                      +4
                                      Пи — не алгебраическое число.
                                      Кроме того, a^b может быть вполне рациональным числом даже если a и b трансцендентны. Например: T^(log10[T]) = 10, где T — трансцендентное.
                                      0

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

                                      0
                                      del
                                      0

                                      Посчитал по обобщенной формуле Бине :) Fib(pi ^ e) = 22090.2876638248, -8.97932700936443E-06 * i.

                                      +7
                                      1. Обычно под числами Фибоначчи понимаются числа с натуральными номерами. Продолжение на отрицательную полуось существует, но редко упоминается и не считается частью ряда по умолчанию.

                                      3. Подскажите мне, пожалуйста, одну из этой кучи статей. Я прошу без всякой иронии, я допускаю, что вы правы, просто мне при беглом поиске не попадается статья, где написано, что именно неправильно именно в моём коде.
                                      –5
                                      > А чем плохи стрелочные функции?
                                      Плохо читаются.
                                      +3
                                      Что плохого в стрелочных функциях?
                                      +28
                                      А потом вы придете на собеседование в Додо Пицца и не пройдете, потому что с их точки зрения вы должны были написать этот код на Ассемблере для демонстрации вашей глубины понимания и широты интересов. Шутка.
                                      На самом деле спасибо за подробный разбор задачи. Я далек от JS, с опытом программирования в пару скетчей на Ардуино по типу «while робот далеко от стены analogWrite скорость 255», но мне было понятно и интересно читать. Именно такие статьи и мотивируют изучать языки, с мыслью «я понял идеологию, осталось написать такой код и поиграться с ним самому».
                                        +6
                                        Острота дискуссии с поста додо дошла и сюда :D
                                          +1
                                          Я всё пропустил(
                                          +11
                                          Заразите энергией. Может быть, у нас и нет вакансий с ассемблером, но ваша энергия подкупит.
                                            +3
                                            ARM пойдёт?

                                            AREA RESET,CODE,READONLY
                                            ENTRY

                                            MOV R5,10; Параметр
                                            MOV R1,0
                                            MOV R2,1

                                            loop ADD R3,R1,R2
                                            MOV R1,R2
                                            MOV R2,R3
                                            SUBS R5,R5,1
                                            BEQ theend
                                            BAL loop

                                            theend MOV R0,R3
                                            SWI 0
                                            END

                                            PS: Последний раз писал на ассемблере лет 15 назад.
                                            PS1: Про Фибоначчи помню смутно…
                                          +6
                                          Выражаясь грубым языком O-нотации, такое решение имеет временную сложность O(e^n).

                                          Это правильно, но слишком грубо. Можно получить более точную оценку числа вызов функции ~(1+sqrt(5)) fib(n) и красивое замечание "Для вычисления числа Фибонначи наивным рекуррентным методом понадобится вызовов функции в 3.2 раза больше чем само число Фибонначи".

                                            +11

                                            И мы получаем ещё один метод его вычисления. Надо просто запустить наивный рекурректный метод, подсчитать количество вызовов функции и разделить на 3.2!

                                            0
                                            Ох этот Фибоначчи. На недавнем собеседовании не смог написать его на листочке (через итератор на c#). Забавно, что в студии потом сделал за минуту.
                                              –1
                                              const fib = n => {
                                                let result = id;
                                                let m = matrix;
                                                const bits = n.toString(2); 
                                                for(const bit of bits){
                                                    if(bit == "1") 
                                                       result = mul(result, m);
                                                  m = mul(m, m);
                                                }
                                                return result[1][0];
                                                0
                                                А порядок битов никого не смущает?
                                                  0
                                                  да, тоже надо поправить
                                                    0
                                                    Хм, вы хотите сказать, мой код неправильный?
                                                      0
                                                      да.
                                                        0
                                                        Но я только что запустил его в браузере и проверил, что он выдаёт верные результаты. Что я делаю не так?
                                                          0
                                                          Алгоритм быстрого возведения в степень можно написать по-разному :)

                                                          Например, множитель возводится в квадрат и в зависимости от того, выставлен ли бит умножает результат, работает от младшего бита к старшему, например 2^10 r=1 (результат), m=2(множитель)
                                                          10 в двоичной это 1010, идя по битам от младшего к старшему 0101
                                                          0 m=2, r=1
                                                          1 m=4, r=r*m=4
                                                          0 m=16, r=4
                                                          1 m=256, r=r*m=1024
                                                          Т.е. 2^10 = 2^2*2^8
                                                          В двоичном виде степень меняется так:
                                                          0,10,010,1010

                                                          В приведённом алгоритме же порядок прохода битов от старшего к младшему, множитель не меняется, а сам результат возводится в квадрат, если бит 1 то ещё и домножается на множитель.
                                                          1 m=2, r=r*r*m=2
                                                          0 m=2, r=r*r=4
                                                          1 m=2, r=r*r*m=32
                                                          0 m=2, r=r*r=1024
                                                          Т.е. 2^10=(((2)^2)^2*2)^2
                                                          В двоичном виде степень меняется так:
                                                          1,10,101,1010

                                                          Всё верно, возведение в квадрат это дописать к степени в двоичном виде 0 справа, а если там должна быть единица то ещё домножить.
                                                          Однако я ожидал увидеть там немного другую реализацию — без нахождения старшего бита :).
                                                +3
                                                УУууу, а если ещё алгоритм сортировки попросят написать потребуют… Странно что что-то кроме кофе хлестать на ковролине могут потребовать. А если ещё про структуру данных какую-нибудь спросят… Нет, не меньше миллиона за такую работу.
                                                  0
                                                  Это задача по математике, а не по программированию. И именно математику спрашивают на собеседованиях. Программирование нафиг никому не нужно.
                                                    0
                                                    задача простейшая.
                                                      0
                                                      Что из того. Они все простейшие и все не по теме.
                                                      0
                                                      И как я понял надо было написать именно программу определяющую n число фибоначчи и тут можно было бы решить её динамическим подходом через рекурентное соотношение Fib(n) = Fib(n — 1) + Fib(n — 2), зарание обозначив что Fib(1) = 1, fib(2) = 1, Быстро и красиво!
                                                        0

                                                        Все нормальные способы вычисления чисел Фибоначчи (быстрое возведение матрицы в степень, разделяй и властвуй и особенно динамическое программирование) — вполне себе computer science.

                                                      0
                                                      del
                                                        +5
                                                        Я поступил проще: взял готовый ряд фибоначчи с сайта исо и загнал его в массив. В результате мое решение выдавало любое число фибоначчи за о(1) без всяких циклов и рекурсий.
                                                          0

                                                          Это конечно хорошо, но он сможет мне выдать 100000000 член ряда Фибоначчи?
                                                          Такой метод хорош для простых чисел...

                                                            +3
                                                            Стомиллионный член и мои функции не выдадут, тут уже нужна длинная арифметика)
                                                              +2
                                                              В python целочисленные вычисления ограничены, насколько я помню, только вашим терпением и ресурсами машины.
                                                              Милионное число посчиталось довольно быстро (секунд за 20), а вот для 10млн-го у меня уже не хватило терпения.
                                                                0
                                                                Пять минут.
                                                                  0
                                                                  Забавно то, что в ЛиКлипсе в два раза дольше (115 секунд) выполняется под Виндой на виндовом Пайтоне-3, чем в виртуальной дебиан здесь же у которой ещё и ядра до 50% (!!!) приспущены от исходного — 45 секунд!
                                                                  10 млн. члена не дождался… не знаю что там за комп у лысого выше, который в пять минут показал результат ))
                                                                  #Neocortexlab fibo bench one thread version
                                                                  import time
                                                                  targetNum = 1000000
                                                                  def fibo(x):
                                                                      if x==0:
                                                                          return(0)
                                                                      if x<=2:
                                                                          return(1)
                                                                      prev=0
                                                                      cur=1
                                                                      while x>1:
                                                                          next=cur+prev
                                                                          prev=cur
                                                                          cur=next
                                                                          x-=1
                                                                      return(cur)
                                                                  
                                                                  start = time.perf_counter()
                                                                  print(fibo(targetNum))
                                                                  stop = time.perf_counter()
                                                                  print ('%.2f seconds to done' % (stop-start))
                                                                  


                                                                  P.S> дождался ответа от сервера по поводу 10млн члена: 863.89 seconds to done — core i7 6700 3.4 ghz
                                                                    0
                                                                    Вот здесь переписал это для Си — onlinegdb.com/ByIZxre6V
                                                                    рекомендую для запуска любителям… только библиотеку gmp не забудьте добавить в линк. Намного быстрее пайтон-пых вариантов

                                                                    #include <stdio.h>
                                                                    #include <gmp.h>
                                                                    #include <time.h>
                                                                    #define TARGET_NUM 100000
                                                                    
                                                                    void fibo(int tn);
                                                                    
                                                                    mpz_t result,next,prev,cur;
                                                                    
                                                                    int main() {
                                                                    struct timespec ts;
                                                                    mpz_init(result);
                                                                    mpz_init_set_ui (cur,1);
                                                                    mpz_init(next);
                                                                    mpz_init(prev);
                                                                    long start,stop,start_sec,stop_sec;
                                                                    double whole_time;
                                                                    
                                                                    timespec_get(&ts, TIME_UTC);
                                                                    start  = ts.tv_nsec;
                                                                    start_sec = ts.tv_sec;
                                                                    
                                                                    fibo(TARGET_NUM);
                                                                    
                                                                    timespec_get(&ts, TIME_UTC);
                                                                    stop   = ts.tv_nsec;
                                                                    stop_sec = ts.tv_sec;
                                                                    
                                                                    gmp_printf("Fibo #%d = %Zd\n",TARGET_NUM,result);
                                                                    
                                                                    whole_time = stop_sec-start_sec;
                                                                    whole_time += (stop-start)/1000000000.0;
                                                                    printf("Whole time = %.2fs\n",whole_time);
                                                                    
                                                                    return(0);
                                                                    }
                                                                    
                                                                    void fibo(int tn) {
                                                                            if (tn==0) {
                                                                                    mpz_set_ui(result,0);
                                                                                    return;
                                                                            }
                                                                            if (tn<=2) {
                                                                                    mpz_set_ui(result,1);
                                                                                    return;
                                                                            }
                                                                    
                                                                            while(tn-->1) {
                                                                                    mpz_add(next,cur,prev);
                                                                                    mpz_set(prev,cur);
                                                                                    mpz_set(cur,next);
                                                                            }
                                                                            mpz_set(result,cur);
                                                                    }
                                                                    
                                                                0
                                                                > Это конечно хорошо, но он сможет мне выдать 100000000 член ряда Фибоначчи?
                                                                в задаче возвращаемое значение было int на Java, так что 100000000 член ряда не требовался
                                                              0
                                                              Ответ кроется вот в этой моей статье.
                                                              А написали ли вы уже игру «про деревянные домики и теорему Кёртиса-Хедланда-Линдона»?
                                                              Джва года уже прошли. (Или нет, так как «джва» может быть числом в совсем другой системе счисления.
                                                              К тому же это была только нижняя граница.)
                                                                0
                                                                Увы, пока мои успехи в геймдеве — одна незаконченная головоломка и две слегка начатых настолки)
                                                                  0

                                                                  Звучит дико интересно! Могли бы вы поделиться ссылкой на контекст?

                                                                    0
                                                                    Это («Ответ кроется вот в этой моей статье») цитата из текущей статьи (там (в статье, а не в моём комменте) есть ссылка на другую статью "Фиеричная система счисления, или почему 1 + 10 = 100", где автор в спойлере после слов
                                                                    Этот подход показался мне настолько забавным, что я написал небольшую игру, которая позволяет игроку ощутить всю его прелесть лично.
                                                                    упоминает домики и теорему.
                                                                  –2

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

                                                                    0

                                                                    Тогда надо Math.ceil для округления вверх.

                                                                      +4
                                                                      Именно до ближайшего. Там вычитаемое с переменным знаком. соответственно, уменьшаемое то больше, то меньше истинного целого значения, но всегда отстоит от него менее чем на 0.5.
                                                                      Вообще, извините, что я на вас побухтю, но такие вещи лучше сначала пробовать самому, а потом уже писать. Если подставите туда ceil, увидите, что расхождения начнутся сразу же, на каждом втором числе)
                                                                      0
                                                                      А где же арифметика для чисел с произвольной точностью? Асипмтотика роста-то экспоненциальная.
                                                                        0
                                                                        у нас в вузе классика была — факториал 100. ну или даже поболее.
                                                                        очень интересные решения встречались.
                                                                          +1
                                                                          Только начал изучать JavaScript, поэтому у меня возник вопрос: команды var и function теперь не используются?..
                                                                            +2
                                                                            var с приходом ES2015 используется только в легаси. Он ничем не лучше let и const, причин его использовать вместо них нет. А function вполне используется, у неё просто своя сфера применения. Стрелочные функции не имеют собственного this, поэтому обычные применяются там, где this нужен.
                                                                              0
                                                                              На самом деле между ними есть небольшая разница: let создает переменную в контексте блока, а var в контексте функции.

                                                                              developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Statements/let#Description
                                                                                0
                                                                                Разница есть, я не утверждал обратного. Но я не знаю ни одной реальной ситуации, в которой эта разница желательна (в пользу var).
                                                                                  +2
                                                                                  Например, в switch-case в разных ветках могут создаваться переменные с одинаковым именем. С let или const так делать нельзя, так как область видимости одна. Надо использовать var или загромождать код лишними конструкциями.

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

                                                                                  Наконец, const не добавляет ценности для работы движка и работает тупо медленнее чем var.
                                                                                    0
                                                                                    Например, в switch-case в разных ветках могут создаваться переменные с одинаковым именем. С let или const так делать нельзя, так как область видимости одна.


                                                                                    Заворачиваем код case-а в фигурные скобки, тем самым создаём новую область видимости, — проблема решена, сам так делал.
                                                                                      +1
                                                                                      И получается лишнюю строчку с закрывающей фигурной скобкой в и без того громоздкой конструкции. Плотность информации снижается, читаемость кода тоже за счёт излишней громоздкости. Костыль из-за не самого удачного решения.
                                                                            +3
                                                                            Ну очень интересно. Ищем 100 число Фибоначчи.
                                                                            «Правильная» рекурсия с пункта 2 дает нам — 354224848179262000000 за 0.571044921875ms
                                                                            Самый быстрый алгоритм на Диком Западе дает нам — 354224848179261900000 за 0.689208984375ms
                                                                            Но самое интересное что 100 число Фибоначчи то — 354224848179261915075
                                                                              0
                                                                              Заменить всё на BigInt или какую-нибудь библиотеку длинной арифметики — не проблема вообще. Да и самому какую-нибудь длинную арифметику написать не проблема, на олимпиадах десятки раз это делал. Но для неопытных разработчиков статья и так перегружена, а опытные и так понимают, что это сделать можно и что сути алгоритма это не меняет.

                                                                              RISENT, пожалуй, это ответ и вам тоже.
                                                                                0
                                                                                смысл был — именно написать свою длинную арифметику.
                                                                                к сожалению был явный запрет использовать архитектурные особенности.
                                                                                но, все же, вариаций было прилично.
                                                                                сделать то можно, но вариантов хватает(мой например с переносом)
                                                                                +4
                                                                                Невнимательно прочитал ваш комментарий. Насчёт скорости да, замечание справедливо. Для маленьких чисел (а стандартные инты маленькие) «самый быстрый алгоритм» вполне может быть медленнее из-за большой константы. Каюсь, не успел сделать тесты, хотел выложить статью до обеда) моя вина, насмехайтесь надо мной.
                                                                                  +1
                                                                                  Вы настоящий Сирион) Это была не насмешка, а заметка. Bazinga! =)
                                                                                0
                                                                                В 4 методе не хватает открывающей скобки.
                                                                                  0
                                                                                  А где конкретно?
                                                                                    +1
                                                                                    Извините что вчера без конкретики, с мобильного приложения писал. Уже отправил предложение исправить опечатку. Очень понравился Мистер Бине в 4 строки, поэтому и пробовал запускать. Спасибо за статью!
                                                                                  +2

                                                                                  Меня вот больше всего удивило, что


                                                                                  Получение значения свойства объекта по ключу — это операция быстрая, но всё-таки не O(1), а O(log(size))
                                                                                    –4
                                                                                    Ну, тут надо немножко представлять, как оно устроено внутри. Представьте себе, что у вас нет объектов, только массивы (а на низком уровне так оно и есть). Попробуйте на массивах реализовать нечто, в чём можно хранить пары «ключ-значение». Вам придётся искать в массиве ключ. Если делать это втупую, то это O(n). Если массив поддерживать в отсортированном состоянии, то O(log n). На самом деле, конечно, там используются какие-то хитрые вещи, хеш-таблицы, вот это вот всё. Но поиск асимптотически остаётся O(log n), хотя и с очень хорошей константой и для практических нужд почти О(1). Почти.
                                                                                      +8
                                                                                      Извините, но тут вы неправы. Объекты в JS — это хэш таблицы, а хэш таблицы хранятся не так как вы говорите — там нет никакой сортировки. Создаётся массив бакетов. Далее каждый ключ у объекта хэшируется в некоторое число N, и вместе со своим значением скидывается в бакет по индексу N. Чтобы получить значение по ключу делается то же самое — берется хэш от ключа, и совершается «прыжок» в нужное место за O(1).
                                                                                      Где тут подвох? Подвох в том, что хэши могут повторяться, и в бакетах может быть заметно больше одного элемента. Но даже в этом случае получить ассимптотически что-то большее чем O(1) можно только специально подбирая данные.
                                                                                      На синтетических тестах теория подтверждается практикой — чтение из объектов размером 100 имеет такой же перфоманс как и чтение из объектов размером 10М. Гугл подкинул мне вот такую ссылку stackoverflow.com/questions/12241676/javascript-objects-as-hashes-is-the-complexity-greater-than-o1, но думаю можно и лучше поискать
                                                                                        +2
                                                                                        Да, я наврал. Я помнил, что там хеш таблицы, но я забыл, какая у них асимптотика, и поленился перепроверить. Исправил в статье, спасибо, что бдите и не даёте мне погрязнуть во тьме заблуждений.
                                                                                          0
                                                                                          Где тут подвох? Подвох в том, что хэши могут повторяться,
                                                                                          Теоретически, если данные мы получаем «откуда-то», злые люди могут подобрать их так, что все хэши будут одинаковые.
                                                                                            0
                                                                                            Объекты в JS — это хэш таблицы, а хэш таблицы хранятся не так как вы говорите — там нет никакой сортировки
                                                                                            Свойства объектов в JS отсортированы в порядке добавления, по меньшей мере, они перечисляются в таком порядке, за исключением свойств с беззнаковыми 32-битными целочисленными ключами (в спеке начиная с ES2015).

                                                                                            Что касается реализации, могут быть варианты. Например, «быстрое» свойство в движке получается тремя ассемблерными инструкциями по заранее известному смещению.
                                                                                            0
                                                                                            Откуда вы взяли свое представление о работе объектов в JS? Starche в ответе практически прав, базово так оно и не только в JS работает. Пруф от разработчиков V8 — v8.dev/blog/fast-properties
                                                                                          –2

                                                                                          Интересно, сколько раз на Хабре были числа Фибоначчи на матрицах? Раз пять я, наверно, видел…

                                                                                            0
                                                                                            Наверное, да, где-то так. Я перед написанием статьи добросовестно прошерстил хабр, наткнулся на десяток, что ли, статей про вычисление данного ряда, но им всем, на мой вкус, не хватало системности. Я решил собрать в одном месте всё, что могу сказать по этому вопросу. На принципиальную новизну претендовать не смею)
                                                                                              0

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

                                                                                                0
                                                                                                Это, часом, не Бине ли получится в итоге, только с другой стороны?
                                                                                                  0
                                                                                                  Можно. Как я писал в комментариях выше, можно пользоваться симметричностью матрицы и не считать отдельно элементы [0][1] и [1][0]. Больше там вроде ничего особо не упростишь. Если диагонализировать, как предлагали выше, там полезут корни и будет неудобно.

                                                                                                  Так-то много чего можно добавить. И корень-из-пяти-рациональные числа выписать ещё раз специально для этого поста. И бенчмаркинг провести. Ещё можно было упомянуть про прикольную приблуду для питона, которая почти произвольный цикл может ускорить, переведя его в матричную форму и использовав быстрое возведение в степень. Но поля этой рукописи слишком узки…
                                                                                              +2
                                                                                              Матрицы — это регулярные выражения наоборот. Многие проблемы, если их переформулировать на языке матриц, решаются просто сами собой.

                                                                                              Если матрица — это обратное к регуляркам, то получится ли единичная проблема, если регулярные выражения решать через матрицы линейную алгебру?


                                                                                              Ну и fibs = 1 : 1 : zipWith (+) fibs (tail fibs) ничего не переплюнет, конечно же. Тут и мемоизация бесплатная, кстати.


                                                                                              Скрытый текст
                                                                                              > fibs !! 10000
                                                                                              54438373113565281338734260993750380135389184554695967026247715841208582865622349017083051547938960541173822675978026317384359584751116241439174702642959169925586334117906063048089793531476108466259072759367899150677960088306597966641965824937721800381441158841042480997984696487375337180028163763317781927941101369262750979509800713596718023814710669912644214775254478587674568963808002962265133111359929762726679441400101575800043510777465935805362502461707918059226414679005690752321895868142367849593880756423483754386342639635970733756260098962462668746112041739819404875062443709868654315626847186195620146126642232711815040367018825205314845875817193533529827837800351902529239517836689467661917953884712441028463935449484614450778762529520961887597272889220768537396475869543159172434537193611263743926337313005896167248051737986306368115003088396749587102619524631352447499505204198305187168321623283859794627245919771454628218399695789223798912199431775469705216131081096559950638297261253848242007897109054754028438149611930465061866170122983288964352733750792786069444761853525144421077928045979904561298129423809156055033032338919609162236698759922782923191896688017718575555520994653320128446502371153715141749290913104897203455577507196645425232862022019506091483585223882711016708433051169942115775151255510251655931888164048344129557038825477521111577395780115868397072602565614824956460538700280331311861485399805397031555727529693399586079850381581446276433858828529535803424850845426446471681531001533180479567436396815653326152509571127480411928196022148849148284389124178520174507305538928717857923509417743383331506898239354421988805429332440371194867215543576548565499134519271098919802665184564927827827212957649240235507595558205647569365394873317659000206373126570643509709482649710038733517477713403319028105575667931789470024118803094604034362953471997461392274791549730356412633074230824051999996101549784667340458326852960388301120765629245998136251652347093963049734046445106365304163630823669242257761468288461791843224793434406079917883360676846711185597501
                                                                                                +1
                                                                                                Не знаю, получится ли единичная проблема, но звучит как идея для ещё одной статьи в стиле «очумелые ручки»)

                                                                                                fibs = 1: 1: zipWith (+) fibs (tail fibs)


                                                                                                Красиво. Впрочем, тут же O(n) всё равно?
                                                                                                  0
                                                                                                  Не знаю, получится ли единичная проблема, но звучит как идея для ещё одной статьи в стиле «очумелые ручки»)

                                                                                                  Там, кстати, если сверху ещё алгебры навернуть, то можно и CFG парсить, а не только регулярные языки. Но в это я уже не вникал особо.


                                                                                                  Впрочем, тут же O(n) всё равно?

                                                                                                  Да, это рекурсивное решение.

                                                                                                    0
                                                                                                    fib n = head (apply (Matrix [[0,1], [1,1]] ^ n) [0,1])

                                                                                                    Говорят, что это "Hello, world!" of Haskell programming; здесь есть и другие решения: https://wiki.haskell.org/The_Fibonacci_sequence

                                                                                                  +5
                                                                                                  Есть ещё такой способ как fast doubling. Работает за как и матричное умножение за O(log), но с меньшей константой в асимптотике (и на практике). Если кратко, то там используется две формулы, опираясь на которые можно быстро рекурсивно откатываться к вдвое меньшим индексам:

                                                                                                  F2n = Fn * (2*Fn+1 – Fn)
                                                                                                  F2n+1 = Fn2 + Fn+12


                                                                                                  Реализация, кстати, получается довольно компактная.
                                                                                                  Сравнение скорости работы разных методов
                                                                                                  image

                                                                                                    0
                                                                                                    Интересно, не встречал такого. Когда мне надо было ускорить матричное возведение, я использовал полиномы (4 умножения против матричных 8), тоже с быстрым возведением.
                                                                                                      0

                                                                                                      Более того, этот подход обобщается на числа K-фибоначчи (т.е. каждое число — сумма K предыдущих). И он дает в K раз более хорошую асимптотика чем через матрицы (квадрат от K вместо куба).

                                                                                                      0
                                                                                                      Сам давно баловался с рекурсией. Заметил, что время наивного выполнения рекурсивных функций выполняет условие чисел Фибоначчи.
                                                                                                      -- ШУТКА
                                                                                                      function fib(n)
                                                                                                         timeBegin = os.clock()
                                                                                                      
                                                                                                         anyRecursion(n)
                                                                                                      
                                                                                                         timeEnd = os.clock()
                                                                                                      
                                                                                                         return ((timeEnd - timeBegin))
                                                                                                      end
                                                                                                      

                                                                                                      Невероятно, но факт! Время на рекурсивное выполнение каждой итерации равно сумме времени выполнения двух предыдущих итераций. Проверил сам, время выполнения с некоторого n выполняет правило чисел Фибоначчи (с погрешностью +-1).
                                                                                                        +1

                                                                                                        Как-будто Milfgard, только про алгоритмы. Качественно, свежо, здорово!

                                                                                                          +1
                                                                                                          Как для большого поклонника милфгарда, для меня это высочайшая оценка, спасибо)
                                                                                                          +2

                                                                                                          Как вам такое в 2 ночи:


                                                                                                          const fib = (n, i = 1, r1 = 0, r2 = 0) => (i >= n) ? r1 + r2 : fib(n, i + 1, (r2 || 1), r1 + r2);
                                                                                                            0

                                                                                                            Абсолютно нечитаемо, незачет

                                                                                                              0
                                                                                                              Да, это хороший, валидный вариант рекурсии, который, по идее, будет производительнее моего. Я таким пользовался, но для статьи решил выбрать вариант с возвратом кортежа в целях наглядности.
                                                                                                              0
                                                                                                              const fib = n => {

                                                                                                              Какое же это уродство. Попробуйте это прочесть: константа fib равна сопоставлению между n и каким-то огромным блоком. Стрелочные функции придумывались не для таких ситуаций. Они придумывались для повышения наглядности коротких, простых функций, в примерах вроде такого:


                                                                                                              var newUsers = users.filter(u => u.registered >= new Date('2014-01-01'));
                                                                                                              var karma = sum(user.comments.map(c => c.score));

                                                                                                              В вашем же случае гораздо лучше смотрится слово function, смотрите:


                                                                                                              function fib(n) {

                                                                                                              Прочтите: Функция fib с аргументом n и телом, которое идет ниже. Совсем другое дело. Уже по первому слову ясно, что перед нами. Если усложнять, то мне еще больше нравится что-то такое:


                                                                                                              /** Комментарий на великом, могучем */
                                                                                                              function fib(n: number): number {

                                                                                                              Какая прелесть!


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


                                                                                                              Внимательный читатель может возразить, что да, синтаксис уродский, но зато функцию нельзя переопределить благодаря const. Мой ответ: ущерб от уродского синтаксиса слишком большой и перевешивает выгоды. А по-хорошему, надо бы просто в строгом режиме и в модулях ES6 сделать все function с признаком const автоматически.


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


                                                                                                              А function вполне используется, у неё просто своя сфера применения. Стрелочные функции не имеют собственного this, поэтому обычные применяются там, где this нужен.

                                                                                                              Ага, у нее есть "своя область применения", но я вам про нее не скажу, тем более что я в этом не разбираюсь.


                                                                                                              Что касается потери точности при методе Бине, я подозреваю, аналогичная потеря точности будет и при "ручном" вычислении через плюсы и умножения. Так как в JS числа это float со всеми вытекающими.

                                                                                                                +1
                                                                                                                По поводу стрелочных функций: ну, вообще это вкусовщина, которую вы пишете в очень категоричном тоне.
                                                                                                                Ага, у нее есть «своя область применения», но я вам про нее не скажу, тем более что я в этом не разбираюсь.
                                                                                                                Вот здесь вы переходите к оскорблениям.
                                                                                                                Что касается потери точности при методе Бине, я подозреваю, аналогичная потеря точности будет и при «ручном» вычислении через плюсы и умножения. Так как в JS числа это float со всеми вытекающими.
                                                                                                                А вот здесь пишете откровенную глупость. Во-первых, не float, а double. Во-вторых, никакая потеря точности не может произойти, пока операнды и все результаты целые и не превосходят по модулю Number.MAX_SAFE_INTEGER.

                                                                                                                В общем, мне кажется, вам стоило бы умерить апломб и сменить тон. Но, разумеется, это всего лишь дружеская рекомендация, как не упасть в кармическую яму (тут я заглянул к вам в профиль) ещё глубже.
                                                                                                                +3
                                                                                                                Я бы еще поинтересовался у собеседующего, когда ему последний раз приходилось кодить какой-нибудь алгоритм, чтобы потом вместе повздыхать о том, что программирование нынче уже не то, формочки шлепать скучно, деградируем на этом фронтенде, но хоть денег много дают, нашу работу может выполнить даже макака, и скоро нас обоих заменят на нейронные сетки.

                                                                                                                У-у-у-у-у! Алгоритмы! Юра знает алгоритмы! Полтора года назад Юра обошел дерево в ширину алгоритмом, и вы представьте себе, это действительно было нужно сделать!
                                                                                                                  0
                                                                                                                  Ну так то мир фронтендом не ограничивается, сферы разные есть
                                                                                                                    0
                                                                                                                    Полтора года назад Юра обошел дерево в ширину алгоритмом, и вы представьте себе, это действительно было нужно сделать!

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


                                                                                                                    Заводить в команде отдельного "алгоритмиста" тоже не вариант по той же причине — остальные разработчики должны понять, что его нужно призвать. Или придется ему ревьювить все изменения в коде, что не скейлится.

                                                                                                                    0
                                                                                                                    «Вычисление ряда Фибоначчи» вполне логично оформить в виде генератора. Но формулировка задания неудачная.
                                                                                                                      0
                                                                                                                      Спасибо за отличную статью.
                                                                                                                      Всегда нравилось формулирование и решение задач через матрицы, но не знал, что так можно с классическими числами Фибоначчи сделать.

                                                                                                                      Осталось прикрутить перемножение матриц через gpu.js — и можно рассказывать на собеседованиях, что умеешь вычислять числа Фибоначчи на GPU (главное не упоминать при этом, что на матрицах такого размера оно от это только медленнее станет). :)
                                                                                                                        0

                                                                                                                        "Запомните этот вариант. Так делать не стоит. Не следует. Нельзя. Никогда. Это хуже, чем пинать щеночков, и сравнимо с небольшим холокостом."


                                                                                                                        Это довольно холиварное утверждение) потом вы сами описываете что существуют способы для ускорения работы рекурсии. В целом есть ряд декларативных языков программирования где кроме рекурсии и алгебраических типов нет возможности реализовать циклы. Например Haskell, и прочие некоторые функциональные языки программирования. И говоря про рекурсию это она в джс так ужасно работает. Существет определенный набор оптимизаций для ускорения работы рекурсии, мемоизация, трамплины, ленивое исполнение и тд.
                                                                                                                        Использование рекурсии не нужно избегать, для определеного типа задач больше подойдет именно рекурсия. Просто нужно знать что ты делаешь.
                                                                                                                        А вообще декларативный код vs императивный это отдельная тема холивара))


                                                                                                                        Хочу предложить еще один способ, который работает с мемоизацией. Реализован при помощи Y-комбинатора.


                                                                                                                        // condition lazy
                                                                                                                        var condL = x => tF => fF => x ? tF() : fF();
                                                                                                                        
                                                                                                                        // Y combinator
                                                                                                                        var Y = f => (x => x(x))(x => y => f(x(x))(y));
                                                                                                                        
                                                                                                                        // Memoized Y combinator
                                                                                                                        var Ymem = memory => F => F(x => condL(memory.has(x))(y => memory.get(x))(y => memory.set(x, Ymem(memory)(F)(x)).get(x)));
                                                                                                                        
                                                                                                                        // Fib function
                                                                                                                        var fibF = f => n => n === 0 || n === 1 ? 1 : f(n - 1) + f(n - 2);
                                                                                                                        
                                                                                                                        // memoized fi function
                                                                                                                        var fib = Ymem(new Map)(fibF);
                                                                                                                        
                                                                                                                        console.log(fib(160))
                                                                                                                          +1
                                                                                                                          Это довольно холиварное утверждение) потом вы сами описываете что существуют способы для ускорения работы рекурсии.
                                                                                                                          Именно. Ускоренную рекурсию — можно. Не ускоренную — нельзя. Если не понимаешь, сколько твоя рекурсия будет работать — совсем нельзя.
                                                                                                                          +1
                                                                                                                          Хорошая статья. По мне так тега математики не хватает.
                                                                                                                            0
                                                                                                                            Тега или хаба?
                                                                                                                              0
                                                                                                                              Хаба, наверное )

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

                                                                                                                          Самое читаемое