Предыстория:
Меня «перетянули», когда я увидел этот вопрос: Выражение закрытой формы Фибоначчи в Haskell
, когда автор изначально помечался многими другими языками, но позже сосредоточился навопрос Хаскеля.К сожалению, у меня нет никакого опыта работы с Haskell, поэтому я не мог принять участие в этом вопросе.Однако один из ответов привлек мое внимание, когда ответчик превратил его в чисто целочисленную математическую задачу.Для меня это звучало удивительно , поэтому мне пришлось выяснить, как это работает, и сравнить это с рекурсивной реализацией Фибоначчи, чтобы увидеть, насколько точной она была.У меня такое ощущение, что если бы я только вспомнил соответствующую математику, включающую иррациональные числа, я мог бы сам все решить (но я не знаю).Поэтому первым шагом для меня было перенести его на язык, с которым я знаком.В этом случае я делаю C #.
К счастью, я не совсем в неведении.У меня большой опыт работы с другим функциональным языком (OCaml), поэтому мне он показался мне знакомым.Начиная с преобразования, все казалось простым, поскольку оно в основном определяло новый числовой тип, чтобы помочь с вычислениями.Тем не менее, я преодолел несколько препятствий в переводе, и у меня возникли проблемы с его завершением.Я получаю совершенно неверные результаты.
Анализ:
Вот код, который я перевожу:
data Ext = Ext !Integer !Integer
deriving (Eq, Show)
instance Num Ext where
fromInteger a = Ext a 0
negate (Ext a b) = Ext (-a) (-b)
(Ext a b) + (Ext c d) = Ext (a+c) (b+d)
(Ext a b) * (Ext c d) = Ext (a*c + 5*b*d) (a*d + b*c) -- easy to work out on paper
-- remaining instance methods are not needed
fib n = divide $ twoPhi^n - (2-twoPhi)^n
where twoPhi = Ext 1 1
divide (Ext 0 b) = b `div` 2^n -- effectively divides by 2^n * sqrt 5
Итак, основываясь на моих исследованиях и на том, что я могу сделать вывод(поправьте меня, если я где-то ошибаюсь), первая часть объявляет тип Ext с конструктором, который будет иметь два параметра Integer (и я предполагаю, что унаследует типы / модули Eq и Show).
Далее следует реализация Ext, которая "наследуется" от Num.fromInteger выполняет преобразование из Integer.negate является унарным отрицанием, а затем есть бинарные операторы сложения и умножения.
Последняя часть - это фактическая реализация Фибоначчи.
Вопросы:
В ответе,Хаммар (отвечающий) упоминает, что возведение в степень обрабатывается реализацией по умолчанию в Num.Но что это значит и как это на самом деле применяется к этому типу?Есть ли неявное число «поле», которое я пропускаю?Применяет ли оно возведение в степень к каждому соответствующему числу, которое оно содержит?Я предполагаю, что он делает последнее, и в итоге получается код C #:
public static Ext operator ^(Ext x, int p) // "exponent"
{
// just apply across both parts of Ext?
return new Ext(BigInt.Pow(x.a, p), BigInt.Pow(x.b, p));
// Ext (a^p) (b^p)
}
Однако это противоречит тому, как я понимаю, зачем нужен negate, он не понадобится, если это действительно произойдет.
Теперь мясо кода.Я читаю первую часть
divide $ twoPhi^n - (2-twoPhi)^n как:
делим результат следующего выражения: twoPhi ^ n - (2-twoPhi) ^ n.
Довольно просто,Поднимите twoPhi до n -й степени.Вычтите из этого результат отдыха.Здесь мы делаем двоичное вычитание, но мы реализовали только унарное отрицание.Или мы не?Или можно подразумевать двоичное вычитание, потому что оно может состоять из сложения и отрицания (что у нас есть)?Я предполагаю последнее.И это облегчает мою неуверенность относительно отрицания.
Последняя часть - фактическое деление:
divide (Ext 0 b) = b `div` 2^n.Две проблемы здесь.Из того, что я нашел, нет оператора деления, только функция
`div`.Так что мне просто нужно разделить числа здесь.Это правильно?Или есть оператор деления, но отдельная функция
`div`, которая делает что-то особенное?
Я не уверен, как интерпретировать начало строки.Это просто простое совпадение с образцом?Другими словами, будет ли это применяться, только если первый параметр был 0?Каков будет результат, если он не совпадет (первый был ненулевым)?Или я должен интерпретировать это, так как мы не заботимся о первом параметре и применяем функцию безоговорочно?Это кажется самым большим препятствием, и использование любой интерпретации все еще дает неверные результаты.
Я где-нибудь делал неправильные предположения?Или все в порядке, и я только что неправильно реализовал C #?
Код:
Вот перевод (нерабочий) и полный исходный код (включая тесты) пока на всякий случай.
// code removed to keep post size down
// full source still available through link above
Прогресс:
Хорошо, так что, глядя на ответы и комментарии, я думаю, что знаю, куда идтиздесь и почему.
Возведение в степень просто необходимо, чтобы сделать то, что оно обычно делает, умножить p раз, учитывая, что мы реализовали операцию умножения.Мне никогда не приходило в голову, что мы должны делать то, что нам всегда говорили на уроках математики.Подразумеваемое вычитание из наличия сложения и отрицания также довольно удобная функция.
Также обнаружил опечатку в моей реализации.Я добавил, когда я должен был умножить.
// (Ext a b) * (Ext c d) = Ext (a*c + 5*b*d) (a*d + b*c)
public static Ext operator *(Ext x, Ext y)
{
return new Ext(x.a * y.a + 5*x.b*y.b, x.a*y.b + x.b*y.a);
// ^ oops!
}
Вывод:
Итак, теперь все готово.Я реализовал только для основных операторов и переименовал его немного.Назван так же, как комплексные числа.Пока что соответствует рекурсивной реализации даже при действительно больших входах.Вот окончательный код.
static readonly Complicated TWO_PHI = new Complicated(1, 1);
static BigInt Fib_x(int n)
{
var x = Complicated.Pow(TWO_PHI, n) - Complicated.Pow(2 - TWO_PHI, n);
System.Diagnostics.Debug.Assert(x.Real == 0);
return x.Bogus / BigInt.Pow(2, n);
}
struct Complicated
{
private BigInt real;
private BigInt bogus;
public Complicated(BigInt real, BigInt bogus)
{
this.real = real;
this.bogus = bogus;
}
public BigInt Real { get { return real; } }
public BigInt Bogus { get { return bogus; } }
public static Complicated Pow(Complicated value, int exponent)
{
if (exponent < 0)
throw new ArgumentException(
"only non-negative exponents supported",
"exponent");
Complicated result = 1;
Complicated factor = value;
for (int mask = exponent; mask != 0; mask >>= 1)
{
if ((mask & 0x1) != 0)
result *= factor;
factor *= factor;
}
return result;
}
public static implicit operator Complicated(int real)
{
return new Complicated(real, 0);
}
public static Complicated operator -(Complicated l, Complicated r)
{
var real = l.real - r.real;
var bogus = l.bogus - r.bogus;
return new Complicated(real, bogus);
}
public static Complicated operator *(Complicated l, Complicated r)
{
var real = l.real * r.real + 5 * l.bogus * r.bogus;
var bogus = l.real * r.bogus + l.bogus * r.real;
return new Complicated(real, bogus);
}
}
А вот и полностью обновленный источник .