/// <summary>
/// Stellt Methoden bereit um über die Liste der Fibonacci Zahlen zu iterieren.
/// </summary>
public struct Fibonacci
{
#region static
/// <summary>
/// Durchläuft alle Fibonacci Zahlen ab 1 bzw. dem angegebenen Nullbasierten Index.
/// </summary>
/// <param name="start">Der Nullbasierte Index der Fibonacci Zahl mit der gestartet werden soll.</param>
/// <returns>Eine Auflistung aller Fibonacci Zahlen ab 1 bzw. dem angegebenen Nullbasierten Index.</returns>
public static IEnumerable<Fibonacci> Enumerate(uint start = 0)
{
BigInteger a, b;
FibonacciAtPosition(start, out a, out b);
yield return new Fibonacci(start++, a);
while (true)
{
yield return new Fibonacci(start++, b);
var tmp = a;
a = b;
b = tmp + b;
}
}
/// <summary>
/// Berechnet 2 aufeinander folgende Fibonacci Zahlen an der angegebenen Position.
/// </summary>
/// <seealso href="http://dotnet-snippets.de/snippet/fibonacci-zahl-mittels-matrix-berechnen/3866"/>
static void FibonacciAtPosition(uint position, out BigInteger outA, out BigInteger outB)
{
++position;//position is zero based, the algorithm is not
BigInteger[,] fib = { { 1, 1 }, { 1, 0 } };
BigInteger[,] blu = { { 1, 0 }, { 0, 1 } };
while (position > 0)
{
if (position % 2 != 0)
blu = ProcessMatrix(blu, fib);
fib = ProcessMatrix(fib, fib);
position /= 2;
}
outA = blu[0, 1];
outB = blu[0, 0];
}
static BigInteger[,] ProcessMatrix(BigInteger[,] blu, BigInteger[,] fib)
{
return new BigInteger[,]
{
{
blu[0, 0] * fib[0, 0] + blu[0, 1] * fib[1, 0],
blu[0, 0] * fib[0, 1] + blu[0, 1] * fib[1, 1],
},
{
blu[1, 0] * fib[0, 0] + blu[1, 1] * fib[1, 0],
blu[1, 0] * fib[0, 1] + blu[1, 1] * fib[1, 1],
}
};
}
#endregion
#region instance
/// <summary>
/// Ruft die Position der Fibonacci Zahl ab.
/// </summary>
public uint Position { get; private set; }
/// <summary>
/// Ruft die Fibonacci Zahl ab.
/// </summary>
public BigInteger Number { get; private set; }
private Fibonacci(uint position, BigInteger number)
: this()
{
this.Position = position;
this.Number = number;
}
/// <summary>
/// Ruft eine Zeichenfolgendarstellung der Fibonacci Zahl mit ihrem Index ab.
/// </summary>
public override string ToString()
{
return string.Format("{0}: {1}", this.Position, this.Number);
}
#endregion
}