fibonacci.htm
Последовательность Фибоначчи
Пытаясь придумать пример для Явы из области помножить матрицы друг на друга, понял, что здесь у меня получается хороший пример для Scp4, пример, демонстрирующий его возможность упрощать арифметические вычисления.
Суперкомпилируется программа, в которой имеются функция вычисления скалярного произведения любых векторов, функция умножения вектора на матрицу, причем матрица представлена по строкам, а для умножения нужны столбцы. Обращаю внимание, что вычисляются два элемента последовательности Фибоначчи, хотя реально нужен лишь один элемент, второй уже имеется.
Суперкомпилятор благополучно разбирается, что вычисленное совпадает с имеющимся. Все умножения на 0 и на 1 упрощаются, сумма с 0 - тоже.
Ничего, в общем-то сверхестесственного, ответ понятен и ожидаем, приятно, что ожидания исполняются.
Привожу программу fibref.htm , которая по имеющемуся начальному отрезку последовательности Фибоначчи вычисляет последующий элемент последовательности.
Результат суперкомпиляции.
$ENTRY Fibonacci {
e.41 (e.102 ) (e.101 )
, <Add (e.102 ) e.101 >:e.122
= e.41 (e.102 ) (e.101 ) (e.122 ) ;
}
After elementary transformation
$ENTRY Fibonacci {
e.41 (e.102) (e.101) = e.41 (e.102) (e.101) (<Add (e.102) e.101>) ;
}
|
Дополнение по первому курсу университета, предмет "линейная алгебра".
Каждая последующая пара элементов последовательности Фибоначчи вычисляется через предыдущую пару путем умножения на соответствующую матрицу. В результате получается что-то похожее на геометрическую прогрессию - произвольная пара элементов выражается через первую пару
( F(k) , F(k+1) ) = ( F(0) , F(1) ) * A^k
Для возведения матрицы в произвольную степень существуют свои способы. Это является примером применения матриц к рекуррентным последовательностям, таким способом можно выводить формулы для общих членов последовательностей. Начальные значения могут быть любыми и в любом количество, матрица может быть любого размера, т.е. последующий элемент может выражаться через три или четыре и т.д. предыдущих элементов (не обязательно сумма). Таким образом происходит разделение начальных значений рекуррентной последовательности (они в начальном векторе) и закона образования последовательности (он в матрице).
При пуске на счет исходной программы получается 35 шагов, в результирующей программе будем считать, что 1 шаг. Таким образом, коэффициент ускорения по шагам - 35. Ясно, что для большей матрицы А коэффициент будет еще больше.
Почему суперкомпиляция просто примера умножения матрицы на вектор не представляет интереса, а этот пример - представляет.Причем как для суперкомпилятора рефала, так и для суперкомпилятора Явы одновременно.
Все дело в том, по чему происходит специализация. Здесь специализация происходит по матрице, имеющей смысл. Последовательность Фибиначчи здесь мало при чем - она выбрана исключительно в качестве всем понятного частного случая.
Более того, этот пример демонстрирует основную идею суперкомпиляции. Специализация общих методов по частным случаям. Я взял общий метод задания рекуррентных последовательностей матричным способом - отсюда получил обычную формулу суммы двух предыдущих членов.
Фиксированная матрица в остаточной программе отсутствует.
Возможные продолжения примера.
1. Менять последовательность путем изменения матрицы. Например, матрицами три на три можно задать последовательность кубов натуральных чисел.
2. В примере рассматривается суперкомпиляция вычисления одного очередного члена последовательности. Организовать дополнительный цикл вычисления заданного количества элементов.
3. Матрица А вычисляет очередной элемент, матрица А^2 - следующий, матрица A^2000 вычислит 2000-ый элемент исходя из первых элементов. Попробовать специализировать по степеням матрицы.
4. При специализации учитывать начальные элементы последовательности. Начальные значения - в начальном векторе, а закон образования последовательности заложен в матрице.
5. Рассматривая обратную матрицу, мы можем продолжать последовательность влево.
6. Имеются сходящиеся последовательности, например,
a ( k+2 ) = ( a ( k ) + a ( k+1) ) / 2
0, 1, 1/2 , 3/4 , ... сходится к 1/3 .
Что здесь можно получить суперкомпиляцией ?
7. Наконец, так как матрицы много где применяются, то что еще можно получить идя по этой дорожке ?