Здравствуйте, 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

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

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

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

Здравствуйте, 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 вызовы с хвостовой рекурсией