Да уж, в очередной раз разочаровлся в функциональном программировании. Его продвигатели говорят, что функциональному программисту достаточно переписать на функциональный язык математематическое определение (то есть ответ на вопрос "Что нужно сделать?"), а компилятор сам сам определит "Как это сделать?", то есть сгенирует алгоритм. На практике получается если например перевести на функциональный язык математическое определение чесел Фибоначчи, генерируется тупой алгоритм и нужно думать как наставлить компилятор функционально языка на путь истинный. Не легче сразу использовать императивный язык и быть уверенным в том, что компилятор сделает то, что задумал программист?
Кто-нибудь сталкивался ещё с такими случаями когда по программе на ФЯ, представляющей собой математическое определение, генирится какой-нибудь плохой алгоритм?

Здравствуйте, nikov, Вы писали:

G>>LLVM умеет переводить наивные алгоритмы Фибоначчи и факториала в хвостовую рекурсию.

N>А асимптотика по времени какая получается?

Про LLVM не скажу, но GCC код

int fib(int n)
{
  if(n == 0 || n == 1) return n;
  return fib(n-1) + fib(n-2);
}

превращает в что-то вроде

int fib(int n) {
    int r = 0;
    while (n > 1) {
        r += fib(n-1);
        n -= 2;
    }
    return n + r;
}

Подробности:
http://eigenclass.org/hiki/legitimate-microbenchmarks
http://www.reddit.com/r/programming/comments/61tc0/legitimate_uses_of_microbenchmarks_parameter/c02kcpp

Здравствуйте, nikov, Вы писали:

G>>LLVM умеет переводить наивные алгоритмы Фибоначчи и факториала в хвостовую рекурсию.

N>А асимптотика по времени какая получается?

Проверил сейчас на http://llvm.org/demo/ -- что-то не очень результаты, раньше код вроде лучше генерировался. Сейчас для факториала такой код на LLVM-ассемблере выдаётся:

int factorial(int X) {
  if (X == 0) return 1;
  return X*factorial(X-1);
}

define i32 @factorial(i32 %X) nounwind readnone {
entry:
    %0 = icmp eq i32 %X, 0        ; <i1> [#uses=1]
    br i1 %0, label %bb2, label %bb1

bb1:        ; preds = %entry
    %1 = add i32 %X, -1        ; <i32> [#uses=2]
    %2 = icmp eq i32 %1, 0        ; <i1> [#uses=1]
    br i1 %2, label %factorial.exit, label %bb1.i

bb1.i:        ; preds = %bb1
    %3 = add i32 %X, -2        ; <i32> [#uses=1]
    %4 = tail call i32 @factorial(i32 %3) nounwind        ; <i32> [#uses=1]
    %5 = mul i32 %4, %1        ; <i32> [#uses=1]
    br label %factorial.exit

factorial.exit:        ; preds = %bb1.i, %bb1
    %6 = phi i32 [ %5, %bb1.i ], [ 1, %bb1 ]        ; <i32> [#uses=1]
    %7 = mul i32 %6, %X        ; <i32> [#uses=1]
    ret i32 %7

bb2:        ; preds = %entry
    ret i32 1
}

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

Здравствуйте, igor-booch, Вы писали:

<skipped/>

заменитк реализацию на использующую хвостовую рекурсию, и все будет

    private Fib(n : int) : long
    {
        def fib(v, x, y)
        {
            if (v == n)
                x
            else
                fib(v + 1, y, x + y)
        }
        
        fib(0, 1L, 1L)
    }

Здравствуйте, igor-booch, Вы писали:

IB>Решил протестировать способность Nemerle преобразоовать рекурсию в цикл. Написал простую функцию для вычисления n-го числа Фибоначчи:
IB> | n => Fib(n — 1) + Fib(n — 2)
IB>Судя по скорости выполнения никакого преобразования в цикл не произошло (IL не изучал).

В цикл преобразуется только хвостовая рекурсия. А это не хвостовая.

Здравствуйте, z00n, Вы писали:

Z>Можно, но в данном случае это не поможет — хвостовая рекурсия сэкономит стек, но для x = Fib(N) все равно понадобится примерно Fib(N) вызовов функции.

Можно написать алгоритм, имеющий сложность по времени O(Log(N)).

Здравствуйте, igor-booch, Вы писали:

IB>Здравствуйте, Mr.Cat, Вы писали:

MC>>Здравствуйте, igor-booch, Вы писали:
IB>>>Его продвигатели говорят, что функциональному программисту достаточно переписать на функциональный язык математематическое определение (то есть ответ на вопрос "Что нужно сделать?"), а компилятор сам сам определит "Как это сделать?", то есть сгенирует алгоритм.
MC>>Ни разу такого не слышал.

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

IB>Почему сложно угадывать? Если функция продекларирована как чистая, и вызывается два раза с одними и теме же параметрами, то второй раз её значение можно не расчитывать.
Вы на этапе компиляции можете узнать, что функция вызывается с одинаковыми аргументами? Я не про примитивную функцию, разумеется.
Если вы предлагаете мемоизировать всё, то вы меняете время на память. Только время у нас растяжимо, а память будет такими функциями пожираться постоянно.
Конкретную функцию вы можете мемоизировать вручную и без особых проблем.

IB>Кстати почему в это не делается в хаскеле и почему в nemercle нелязя декларировать чистоту функций?
Это не делается хотя бы потому, что эффект будет лишь в частных случаях, а зазря анализировать и тратить время компиляции — зачем?

Здравствуйте, igor-booch, Вы писали:

IB>Программист должен стремиться к тому чтобы как можно больше кода было чистым. Декларация чистоты отделяет чистый код от нечистого. А так получается, что всё смешивается и мы не можем задействовать преимущества функциональных языков.

IB>Кто-нибудь встречал императивно-декларативные языки с декларацией чистоты?
Ну, как известно, Haskell — лучший императивный язык

Решил протестировать способность Nemerle преобразоовать рекурсию в цикл. Написал простую функцию для вычисления n-го числа Фибоначчи:

using System;
using System.Console;
using Nemerle.Utility;

module Program
{
  Main() : void
  {
    def Fib(num : uint)
    {
      | 0U | 1U => 1 :> ulong
      | n => Fib(n - 1) + Fib(n - 2)
    }  
  
    WriteLine(Fib(100));
    ReadLine();
  }
}

Судя по скорости выполнения никакого преобразования в цикл не произошло (IL не изучал). Аналогичная программа на С# c использованием циклов выполняется мгновенно:

using System;

namespace ConsoleApplication10
{
  class Program
  {
    static void Main(string[] args)
    {
      ulong prev = 1;
      ulong next = 1;

      for (int i = 0; i < 99; i ++)
      {
        ulong tempNext = next;
        next = prev + next;
        prev = tempNext;
      }

      Console.WriteLine(next);
      Console.ReadLine();
    }
  }
}

Скорей всего для вычисления факториала было бы то же самое.

Здравствуйте, igor-booch, Вы писали:
IB> | n => Fib(n — 1) + Fib(n — 2)

IB>программа на С#
IB> ulong tempNext = next;
IB> next = prev + next;
IB> prev = tempNext;

Программы не эквивалентны.
Про хвостовую тебе уже сказали.

Спасибо, кажется понял.

Неспособность компилятора преобразовать в цикл нехвостовую рекурсию
является просто нереализованной фичей или есть какие-то фундаментальные (теоретические) ограничения? Если есть то какие?
Можно ли автоматически преобразовать нехвостовую рекурсию в хвостовую, а потом в цикл?

Здравствуйте, igor-booch, Вы писали:

IB>Спасибо, кажется понял.

IB>Неспособность компилятора преобразовать в цикл нехвостовую рекурсию
IB>является просто нереализованной фичей или есть какие-то фундаментальные (теоретические) ограничения? Если есть то какие?
Хвостовая рекурсия имеет такое свойство, что после рекурсивого вызова состояние локальных переменных не используется, поэтому оно может быть отброшено. Это позволяет не выполнять вызов рекурсивно, а заменить текущее состояние локальных переменных на то, которое бы они приняли будь такой вызов произведен, и просто передать управление на начало алгоритма.
Если локальные переменные нужны после рекурсивного вызова, то есть в случае нехвостовой рекурсии, то их пришлось бы сохранять и потом востанавливать, а это как раз то, что и так за нас делает любой вызов функции.

Здравствуйте, igor-booch, Вы писали:
IB>Можно ли автоматически преобразовать нехвостовую рекурсию в хвостовую, а потом в цикл?
Да. Например, с помощью т.н. cps-преобразования. Такое преобразование выполняют многие компиляторы scheme. Но там на то немного другие причины.
Однако простейшие преобразования не могут изменить space complexity. Т.е. если у тебя был факториал без хвостовой рекурсии с O(n) по памяти — то после cps O(n) никуда не денется.
Чтобы автоматически улучшать O(что-то) (например, чтобы переписать "неправильный" нехвостовой факториал на хвостовой вариант с аккумулятором) нужно не только распознавать такие вот "неправильные" функции, но и знать свойства выполняемых этими функциями операций. Подобную оптимизацию умеют всякие умные компиляторы (недавно был тред, где наблюдалась такая способность у gcc).

IB>Неспособность компилятора преобразовать в цикл нехвостовую рекурсию
IB>является просто нереализованной фичей или есть какие-то фундаментальные (теоретические) ограничения? Если есть то какие?
Если хитрых оптимизаций в компиляторе не реализовано, то простые тогда ни к чему. Сделаешь, например, cps-преобразование — и вместо роста стека вызовов получишь растущую функцию-континуацию. Шило на мыло.
За тем, чтобы рекурсия была хвостовой, там, где это необходимо (где нужно O(1) по памяти), обязан следить сам программист. Например, твоя реализация Фибоначчи на Nemerle имеет экспоненциальную сложность по памяти (сравни с константной на шарпе). Ну куда это годится?

Здравствуйте, igor-booch, Вы писали:

IB>Спасибо, кажется понял.

IB>Неспособность компилятора преобразовать в цикл нехвостовую рекурсию
IB>является просто нереализованной фичей или есть какие-то фундаментальные (теоретические) ограничения? Если есть то какие?
IB>Можно ли автоматически преобразовать нехвостовую рекурсию в хвостовую, а потом в цикл?

Можно, но в данном случае это не поможет — хвостовая рекурсия сэкономит стек, но для x = Fib(N) все равно понадобится примерно Fib(N) вызовов функции. Можно запоминать промежуточные результаты, как в вашей итеративной версии — тогда и с рекурсией будет очень быстро: N вызовов вместо Fib(N).

MC> Например, твоя реализация Фибоначчи на Nemerle имеет экспоненциальную сложность по памяти

По времени сложность тоже экспонентциальная:



Непонимаю почему, как на 50 простых рекурсивных вызовов может требоваться 15 (!) минут. Кто-нибудь может объяснить? Что происходит в районе 45 числа? Почему зависимость экспонетциальная?



Вот программа с помощью которой строился график:

using System;
using System.Console;
using Nemerle.Utility;

module Program
{
  Main() : void
  {
    def Fib(num : uint)
    {
        | 0U | 1U => 1 :> ulong
        | n => Fib(n - 1) + Fib(n - 2)
    }  
    
    mutable fibStatistics : string;
    mutable fibStatisticsLine : string;
    mutable startTicks : Int64;
    mutable finishTicks : Int64;
    
    for (mutable i = 0U; i <= 60; i++)
    {
        startTicks = DateTime.Now.Ticks;
        mutable fib = Fib(i);
        finishTicks = DateTime.Now.Ticks;
        
        
        fibStatisticsLine = string.Empty;
        fibStatisticsLine = fibStatisticsLine + i.ToString() + " ";
        fibStatisticsLine = fibStatisticsLine + fib.ToString() + " ";        
        fibStatisticsLine = fibStatisticsLine + (finishTicks - startTicks).ToString() + " ";   
        
        WriteLine(fibStatisticsLine);
        
        fibStatistics = fibStatistics + fibStatisticsLine + System.Environment.NewLine;    
    }
    
    ReadLine();
  }
}

Здравствуйте, igor-booch, Вы писали:
IB>По времени сложность тоже экспонентциальная:
Потому что ты такой алгоритм написал:
IB> | n => Fib(n — 1) + Fib(n — 2)
fib(n) = fib(n-1) + fib(n-2) = [fib(n-2) + fib(n-3)] + [fib(n-3) + fib(n-4)] = ...
Заметь, что fib(n-3) раздвоился. Т.е. алгоритм делает кучу повторных вычислений.

Да уж, в очередной раз разочаровлся в функциональном программировании. Его продвигатели говорят, что функциональному программисту достаточно переписать на функциональный язык математематическое определение (то есть ответ на вопрос "Что нужно сделать?"), а компилятор сам сам определит "Как это сделать?", то есть сгенирует алгоритм. На практике получается если например перевести на функциональный язык математическое определение чесел Фибоначчи, генерируется тупой алгоритм и нужно думать как наставлить компилятор функционально языка на путь истинный. Не легче сразу использовать императивный язык и быть уверенным в том, что компилятор сделает то, что задумал программист?
Кто-нибудь сталкивался ещё с такими случаями когда по программе на ФЯ, представляющей собой математическое определение, генирится какой-нибудь плохой алгоритм?

Здравствуйте, igor-booch, Вы писали:
IB>Его продвигатели говорят, что функциональному программисту достаточно переписать на функциональный язык математематическое определение (то есть ответ на вопрос "Что нужно сделать?"), а компилятор сам сам определит "Как это сделать?", то есть сгенирует алгоритм.
Ни разу такого не слышал.

IB>компилятор сам сам определит "Как это сделать?", то есть сгенирует алгоритм.
Это не всегда возможно. Например, функция Fib могла производить побочный эффект, поэтому компилятор не имеет права мемоизировать значения Fib(n) и потом повторно их использовать. По крайней мере — в nemerle, где наличие побочного эффекта никак не декларируется (сравни с хаскелем). Впрочем, и хаскель тоже автоматически не особо ничего не мемоизирует — в компиляторе сложно угадывать, нужно ли сохранять вычисленные значения или нет — такие такие вещи программист должен определять сам.

Здравствуйте, igor-booch, Вы писали:

IB>Да уж, в очередной раз разочаровлся в функциональном программировании. Его продвигатели говорят, что функциональному программисту достаточно переписать на функциональный язык математематическое определение (то есть ответ на вопрос "Что нужно сделать?"), а компилятор сам сам определит "Как это сделать?", то есть сгенирует алгоритм. На практике получается если например перевести на функциональный язык математическое определение чесел Фибоначчи, генерируется тупой алгоритм и нужно думать как наставлить компилятор функционально языка на путь истинный. Не легче сразу использовать императивный язык и быть уверенным в том, что компилятор сделает то, что задумал программист?
IB>Кто-нибудь сталкивался ещё с такими случаями когда по программе на ФЯ, представляющей собой математическое определение, генирится какой-нибудь плохой алгоритм?

Ещё один классический пример — quicksort на Хаскелле, который описывается очень коротко:

qsort []     = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

Но имеет плохие показатели при практическом использовании.

К сожалению, использование императивных языков дает лишь ложную уверенность в том, что компилятор сделает то, что задумал программист, с максимальной эффективностью. Как пример приведу обход прямоугольного массива в C и Паскале. В обоих языках это реализуется вложенным циклом. Но в одном языке во внутреннем цикле эффективнее «накручивать» первый индекс массива a[inner, outer], а в другом — второй: a[outer, inner]. Если вы о таких тонкостях не знаете, вам будет сложно найти в коде обхода проблему.

APL — функциональный язык программирования, известный своей лаконичностью. В нём явное использование оператора цикла является плохим программистким тоном. Во время исполнения интерпретатор выбирает наилучшую реализацию той или иной функции, рассчитанную именно на тот тип данных, над которым проводится операция. В результате, интерпретированные «однострочники» над динамично типизированными данными не уступают по эффективности аналогичным программам на С, не говоря уже о наследниках APL (например, J или K), которые ещё и автоматически распараллеливают вычисления.

Здравствуйте, Mr.Cat, Вы писали:

MC>Здравствуйте, igor-booch, Вы писали:
IB>>Его продвигатели говорят, что функциональному программисту достаточно переписать на функциональный язык математематическое определение (то есть ответ на вопрос "Что нужно сделать?"), а компилятор сам сам определит "Как это сделать?", то есть сгенирует алгоритм.
MC>Ни разу такого не слышал.

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



MC>Это не всегда возможно. Например, функция Fib могла производить побочный эффект, поэтому компилятор не имеет права мемоизировать значения Fib(n) и потом повторно их использовать. По крайней мере — в nemerle, где наличие побочного эффекта никак не декларируется (сравни с хаскелем). Впрочем, и хаскель тоже автоматически не особо ничего не мемоизирует — в компиляторе сложно угадывать, нужно ли сохранять вычисленные значения или нет — такие такие вещи программист должен определять сам.

Почему сложно угадывать? Если функция продекларирована как чистая, и вызывается два раза с одними и теме же параметрами, то второй раз её значение можно не расчитывать. Кстати почему в это не делается в хаскеле и почему в nemercle нелязя декларировать чистоту функций?

Здравствуйте, igor-booch, Вы писали:

IB>Почему сложно угадывать? Если функция продекларирована как чистая, и вызывается два раза с одними и теме же параметрами, то второй раз её значение можно не расчитывать. Кстати почему в это не делается в хаскеле и почему в nemercle нелязя декларировать чистоту функций?

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

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

Don't save anything you can calculate.

Здравствуйте, igor-booch, Вы писали:

IB>Насколько я понимаю, главный принцип декларативного программирования заключается в том, что программист декларирует в программе результат, который должен быть достигнут, не указывая (не приказывая) компилятору как должен быть достигнут результат (то есть алгоритм достижения результата). В императивном программировании программист приказавает (как император) компилятору как должен быть достигнут результат, то есть описывает алгоритм решения. При этом компилятор просто выполняет приказы программиста и ничего не знает о что будет достигнуто в рзультате выполнения этих приказов.
IB>Именно этим отличием меня и привлекло декларативное программирование, но получается что этот принцип на практике до конца не реализуется.

Мое мнение — компиляторы пока недостаточно умны для таких задач.

Здравствуйте, VoidEx, Вы писали:

IB>>Почему сложно угадывать? Если функция продекларирована как чистая, и вызывается два раза с одними и теме же параметрами, то второй раз её значение можно не расчитывать.
VE>Вы на этапе компиляции можете узнать, что функция вызывается с одинаковыми аргументами? Я не про примитивную функцию, разумеется.
VE>Если вы предлагаете мемоизировать всё, то вы меняете время на память. Только время у нас растяжимо, а память будет такими функциями пожираться постоянно.
VE>Конкретную функцию вы можете мемоизировать вручную и без особых проблем.

Меморизация результатов вычисления функций можно повесить на среду выполнения, наподобии CLR у NET или VM у java. Среда выполнения может в зависимости от объёмы выделенной памяти принимать решении о меморизации результатов вычисления функций. Почти то же самое делает системный кэш Windows: дисковые данные, к которым производится частое обращение записываются в память. Объем этих данных зависит от объёма физической памяти.

Кстати кто-нибуть встречал компиляторы декларативных языков, генерирующие код для исполнения в средах выполнения?


IB>>Кстати почему в это не делается в хаскеле и почему в nemercle нелязя декларировать чистоту функций?
VE>Это не делается хотя бы потому, что эффект будет лишь в частных случаях, а зазря анализировать и тратить время компиляции — зачем?

На мой взгляд декларация чистоты может дать многое:
1. Разлиные оптимизации, в том числе оптимизация о которой мы говорим
2. Автоматическое распараллерирование
3. Упрощение и автоматизация тестирования
То есть мы сможем все преимущества функциональных языков, о которых говорится в статье: http://www.rsdn.ru/article/funcprog/fp.xml

Автор(ы): Вячеслав Ахмечет
Дата: 16.09.2006
Данная статья достаточно кратко и вполне доступно, используя примеры на Java (!), знакомит читателя с базовыми понятиями функционального программирования.

.

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

Кто-нибудь встречал императивно-декларативные языки с декларацией чистоты?

Здравствуйте, nikov, Вы писали:

N>Мое мнение — компиляторы пока недостаточно умны для таких задач.

Согласен. Я верю что за декларативным программированием будующее. В каком направлении сейчас идет раввитие функцональных языков? Достигнут ли технолонический предел умности? Ведется ли разработка сред выполнения для функциональных языков ( я писал в одном из постов) или аппартных решений (например как ЛИСП — машина), позволяющих повысить производительность?

Здравствуйте, igor-booch, Вы писали:

N>>Мое мнение — компиляторы пока недостаточно умны для таких задач.

IB>Согласен. Я верю что за декларативным программированием будующее. В каком направлении сейчас идет раввитие функцональных языков?
Есть гибридные функционально-логические языки, например Curry.
Есть языки с зависимыми типами, например Agda 2.

IB>Достигнут ли технолонический предел умности?
А разве он есть?

Здравствуйте, igor-booch, Вы писали:

IB>Кто-нибудь встречал императивно-декларативные языки с декларацией чистоты?

Императивные есть, Digitalmars D http://www.digitalmars.com/d/2.0/function.html#pure-functions

Здравствуйте, nikov, Вы писали:

N>Можно написать алгоритм, имеющий сложность по времени O(Log(N)).

Напишите, пожалуйста

Здравствуйте, igor-booch, Вы писали:

IB>Здравствуйте, nikov, Вы писали:

N>>Можно написать алгоритм, имеющий сложность по времени O(Log(N)).

IB>Напишите, пожалуйста

http://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form
Ну, а возвести матрицу в степень N за O(Log(N)) уже несложно.

Здравствуйте, igor-booch, Вы писали:
IB>Напишите, пожалуйста
Есть в sicp с подробным объяснением.

Можно даже O(C) через формуле Бине:

http://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#.D0.A4.D0.BE.D1.80.D0.BC.D1.83.D0.BB.D0.B0_.D0.91.D0.B8.D0.BD.D0.B5

Можно даже O(C) через формуле Бине:

http://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#.D0.A4.D0.BE.D1.80.D0.BC.D1.83.D0.BB.D0.B0_.D0.91.D0.B8.D0.BD.D0.B5

Здравствуйте, Mr.Cat, Вы писали:

MC>Здравствуйте, igor-booch, Вы писали:
IB>>По времени сложность тоже экспонентциальная:
MC>Потому что ты такой алгоритм написал:
IB>> | n => Fib(n — 1) + Fib(n — 2)
MC>fib(n) = fib(n-1) + fib(n-2) = [fib(n-2) + fib(n-3)] + [fib(n-3) + fib(n-4)] = ...
MC>Заметь, что fib(n-3) раздвоился. Т.е. алгоритм делает кучу повторных вычислений.


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




Mathematica 7.0 его не решает:

a[n] == 1 + \!\(
\*UnderoverscriptBox[\(\[Sum]\), \(i = 0\), \(\(-2\) + n\)]\(a[
i]\)\) + \!\(
\*UnderoverscriptBox[\(\[Sum]\), \(i = 0\), \(\(-1\) + n\)]\(a[i]\)\)

Можно интересно решить такое

Здравствуйте, igor-booch, Вы писали:

IB>Можно даже O(C) через формуле Бине:

IB>http://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#.D0.A4.D0.BE.D1.80.D0.BC.D1.83.D0.BB.D0.B0_.D0.91.D0.B8.D0.BD.D0.B5

Каким алгоритмом будем иррациональное число в степень возводить?

Здравствуйте, nikov, Вы писали:

N>Каким алгоритмом будем иррациональное число в степень возводить?

Да не об этом речь, 32-битные или 64-битные числа вообще можно по табличке возвращать.

Здравствуйте, igor-booch, Вы писали:
IB>Попытался для интереса найти количество вызовов моей рекурсивной функции, как функцию от номера числа Фибоначчи, получилось рекурсивное уравнение
Если я правильно посчитал, то получается сумма чисел фибоначчи от 1-го до n-го за исключением n-1-го.

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, nikov, Вы писали:

N>>Каким алгоритмом будем иррациональное число в степень возводить?

А>Да не об этом речь, 32-битные или 64-битные числа вообще можно по табличке возвращать.

По какой табличке?

Здравствуйте, nikov, Вы писали:

N>Здравствуйте, igor-booch, Вы писали:

IB>>Можно даже O(C) через формуле Бине:

IB>>http://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#.D0.A4.D0.BE.D1.80.D0.BC.D1.83.D0.BB.D0.B0_.D0.91.D0.B8.D0.BD.D0.B5

N>Каким алгоритмом будем иррациональное число в степень возводить?

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

Интересно как с этой задачей справилась бы ЛИСП машина?

Здравствуйте, igor-booch, Вы писали:

А>>Да не об этом речь, 32-битные или 64-битные числа вообще можно по табличке возвращать.

IB>По какой табличке?

Имеется в виду, что в 64-битный интервал влезает меньше 100 первых чисел Фибоначчи. Можно их заранее посчитать, и потом доставать из таблицы за константное время.

Здравствуйте, nikov, Вы писали:

N>Мое мнение — компиляторы пока недостаточно умны для таких задач.

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

Здравствуйте, geniepro, Вы писали:

G>LLVM умеет переводить наивные алгоритмы Фибоначчи и факториала в хвостовую рекурсию.

Может, он заточен распознавать и переделывать именно эти алгоритмы? Чтобы приятно удивлять студентов и внушать им иллюзии всемогущего разгильдяйства.

Здравствуйте, geniepro, Вы писали:

G>LLVM умеет переводить наивные алгоритмы Фибоначчи и факториала в хвостовую рекурсию.

GCC тоже это делает давно.

Здравствуйте, D. Mon, Вы писали:

G>>LLVM умеет переводить наивные алгоритмы Фибоначчи и факториала в хвостовую рекурсию.

DM>GCC тоже это делает давно.


VC тоже но ему нужна подсказка:

#pragma inline_recursion(on)

И потом из фибоначчи в пару сишных строк получаем ассемблерный листинг в 10 тысяч строк, все что можно развернуто в CPS вызовы с хвостовой рекурсией

Здравствуйте, geniepro, Вы писали:


N>>Мое мнение — компиляторы пока недостаточно умны для таких задач.

G>LLVM умеет переводить наивные алгоритмы Фибоначчи и факториала в хвостовую рекурсию.

А асимптотика по времени какая получается?

Здравствуйте, geniepro, Вы писали:

G>>>LLVM умеет переводить наивные алгоритмы Фибоначчи и факториала в хвостовую рекурсию.

N>>А асимптотика по времени какая получается?

G>Проверил сейчас на http://llvm.org/demo/ -- что-то не очень результаты, раньше код вроде лучше генерировался. Сейчас для факториала такой код на LLVM-ассемблере выдаётся:
skip
G>Для фибоначчи код выглядит ещё хуже, хотя раньше вроде нормальный такой цикл выдавался...

Это регрессия, уже есть багрепорт (PR4919). Если написать факториал вручную на ассемблере LLVM и указать соответствующий проход, то получается нормально:

$ cat fac.ll
define i32 @factorial(i32 %n)
{
    %ifzero = icmp eq i32 %n, 0
    br i1 %ifzero, label %Return1, label %Recursion
Return1:
    ret i32 1
Recursion:
    %tmp1 = sub i32 %n, 1
    %tmp2 = call i32 @factorial(i32 %tmp1)
    %result = mul i32 %n, %tmp2
    ret i32 %result
}
$ llvm-as fac.ll -o - | opt -tailcallelim -o - | llvm-dis -o -
; ModuleID = '<stdin>'

define i32 @factorial(i32 %n) {
; <label>:0
  br label %tailrecurse

tailrecurse:                                      ; preds = %Recursion, %0
  %accumulator.tr = phi i32 [ 1, %0 ], [ %result, %Recursion ] ; <i32> [#uses=2]
  %n.tr = phi i32 [ %n, %0 ], [ %tmp1, %Recursion ] ; <i32> [#uses=3]
  %ifzero = icmp eq i32 %n.tr, 0                  ; <i1> [#uses=1]
  br i1 %ifzero, label %Return1, label %Recursion

Return1:                                          ; preds = %tailrecurse
  ret i32 %accumulator.tr

Recursion:                                        ; preds = %tailrecurse
  %tmp1 = sub i32 %n.tr, 1                        ; <i32> [#uses=1]
  %result = mul i32 %n.tr, %accumulator.tr        ; <i32> [#uses=1]
  br label %tailrecurse
}