The code typed-in during the tutorial-session is as follows:-
//Buttons: Number Exp, Fib Num Gen
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Diagnostics;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
namespace Tutorial
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
//Exponentiation by Squaring
//4^16 = (4^2)^8
//16^8 = (16^2)^4
//256^4 = (256^2)^2
//65536^2 = (65536^2)^1
//4294967296 = 4294967296
//4^15 = 4 * (4^2)^7 = 4 * 16^7
//4 * 16^7 = 4 * 16 * (16^2)^3 = 64 * 256^3
//64 * 256^3 = 64 * 256 * (256^2)^1 = 16384 * 65536^1
//16384 * 65536^1 = 16384 * 65536
//1073741824
private static Int64 NumberExponentiation(Int64 num, Int64 power)
{
if (power == 0)
return 1;
if (power == 1)
return num;
if (power % 2 == 0)
return NumberExponentiation(num * num, power / 2);
else
return num * NumberExponentiation(num * num, (power - 1) / 2);
}
private void button1_Click(object sender, EventArgs e)
{
Int64 num = 11;
Int64 power = 5;
//11^5 = 161051.
MessageBox.Show(NumberExponentiation(num, power).ToString());
}
private static Int64 TraditionalFibGen(Int64 termNum)
{
//Fibonacci Series:-
//1, 1, 2, 3, 5, 8, 13, 21, 34...
Int64 prev = 1;
Int64 curr = 1;
Int64 fibNum = 0;
for (Int64 i = 3; i <= termNum; i++)
{
fibNum = prev + curr;
prev = curr;
curr = fibNum;
}
if (fibNum == 0)
return 1;
else
return fibNum;
}
private void button2_Click(object sender, EventArgs e)
{
Int64 termNum = 100000000;
Stopwatch sw = Stopwatch.StartNew();
Int64 tradFibNum = TraditionalFibGen(termNum);
sw.Stop();
string tradFibStatus = "Trad Fib Num: " + tradFibNum + "\nElapsed Ticks: " + sw.ElapsedTicks;
//MessageBox.Show(tradFibStatus);
//Fibonacci Series:-
//1, 1, 2, 3, 5, 8, 13, 21, 34...
//Matrix Method:-
//The count of numbers that don't depend on any previous number(s) is 2.
Int64[][] initialMatrix = new[] { new[] { 1L }, new[] { 1L } };
//Matrix Multiplication:-
// _ _ _ _ _ _ _ _
// | 1 2 | * | 2 1 | = | 1*2+2*2 1*1+2*1 | = | 6 3 |
// |_ 3 4 _| |_ 2 1 _| |_ 3*2+4*2 3*1+4*1 _| |_ 14 7 _|
//We need to find what transformation matrix when multiplied with the initial matrix yields the next set of Fib numbers.
//axb * 2x1 = 2x1
//b = 2
//a = 2
//The dimension of initialMatrix is 2x1.
//The dimension of the matrix after matrix-multiplication must be 2x1.
//Hence, the transformation matrix must have a 2x2 dimension.
// _ _ _ _ _ _
// | a b | * | 1 | = | 1 |
// |_ c d _| |_ 1 _| |_ 2 _|
// Equations:-
// a*1 + b*1 = 1
// c*1 + d*1 = 2
//Hence, a = 0; b = 1; c = 1; d = 1.
Int64[][] transformation = new[] { new[] { 0L, 1L }, new[] { 1L, 1L } };
//5th Fib Number Generation:-
// _ _ _ _ _ _
// | 0 1 | raised to power 4 * | 1 | = | 5 |
// |_ 1 1 _| |_ 1 _| |_ 8 _|
//This is not element-wise powering. It's matrix-multiplication powering.
//Detailed example for arriving at the 5th Fib number:-
// _ _ _ _ _ _ _ _
// | 0 1 | * | 0 1 | = | 0*0+1*1 0*1+1*1 | = | 1 1 |
// |_ 1 1 _| |_ 1 1 _| |_ 1*0+1*1 1*1+1*1 _| |_ 1 2 _|
// _ _ _ _ _ _ _ _
// | 1 1 | * | 0 1 | = | 1*0+1*1 1*1+1*1 | = | 1 2 |
// |_ 1 2 _| | 1 1 _| |_ 1*0+2*1 1*1+2*1 _| |_ 2 3_|
// _ _ _ _ _ _ _ _
// | 1 2 | * | 0 1 | = | 1*0+2*1 1*1+2*1 | = | 2 3 |
// |_ 2 3 _| |_ 1 1 _| |_ 2*0+3*1 2*1+3*1 _| |_ 3 5 _|
// _ _ _ _ _ _ _ _
// | 2 3 | * | 1 | = | 2*1+3*1 | = | 5 |
// |_ 3 5 _| |_ 1 _| |_ 3*1+5*1 _| |_ 8 _|
Int64 termNum2 = termNum - 1;
sw = Stopwatch.StartNew();
Int64[][] finalMatrix = MatrixMultiplication(MatrixExponentiation(transformation, termNum2), initialMatrix);
sw.Stop();
string fastFibStatus = "\nFast Fib Num: " + finalMatrix[0][0] + "\nElapsed Ticks: " + sw.ElapsedTicks;
MessageBox.Show(tradFibStatus + fastFibStatus);
}
// _ _ _ _ _ _ _ _
// | 1 2 | * | 2 1 | = | 1*2+2*2 1*1+2*1 | = | 6 3 |
// |_ 3 4 _| |_ 2 1 _| |_3*2+4*2 3*1+4*1 _| |_ 14 7 _|
private static Int64[][] MatrixMultiplication(Int64[][] a, Int64[][] b)
{
int aRows = a.GetLength(0);
int aCols = a[0].GetLength(0);
int bRows = b.GetLength(0);
int bCols = b[0].GetLength(0);
Int64[][] c = new Int64[aCols][];
for (int i = 0; i < aCols; i++)
c[i] = new Int64[bRows];
for (int i = 0; i < aRows; i++)
for (int j = 0; j < bCols; j++)
for (int k = 0; k < aCols; k++)
c[i][j] = (c[i][j] + a[i][k] * b[k][j]);
return c;
}
private static Int64[][] MatrixExponentiation(Int64[][] matrix, Int64 power)
{
if (power == 0)
return new[] { new[] { 0L, 1L }, new[] { 1L, 1L } };
if (power == 1)
return matrix;
if (power % 2 == 0)
return MatrixExponentiation(MatrixMultiplication(matrix, matrix), power / 2);
else
return MatrixMultiplication(matrix, MatrixExponentiation(MatrixMultiplication(matrix, matrix), (power - 1) / 2));
}
}
}
Thank you for reading this post and watching the videos. Please Subscribe, Comment, and Rate the channel of you liked the videos.
Goto C# Experiments to access more of such content! Thanks again!
No comments:
Post a Comment