Skip to content

Instantly share code, notes, and snippets.

@Vake93

Vake93/Program.cs

Last active August 13, 2019 09:26
Show Gist options
  • Save Vake93/70276331a82c226e38fbc8b9331fbec7 to your computer and use it in GitHub Desktop.
Save Vake93/70276331a82c226e38fbc8b9331fbec7 to your computer and use it in GitHub Desktop.
Download ZIP
TailCallElimination
Raw
Program.cs
using System;
using System.Numerics;
using System.Reflection.Emit;
namespace TailCallElimination
{
public class Program
{
public static BigInteger Fibonacci(BigInteger n, BigInteger a, BigInteger b)
{
if (n == 0)
return a;
if (n == 1)
return b;
return Fibonacci(n - 1, b, a + b);
}
static void Main(string[] args)
{
var parameterTypes = new Type[]
{
typeof(BigInteger),
typeof(BigInteger),
typeof(BigInteger)
};
var dynamicMethod = new DynamicMethod("Fibonacci", typeof(BigInteger), parameterTypes);
var methodIL = dynamicMethod.GetILGenerator();
var indexNotZeroLabel = methodIL.DefineLabel();
var indexNotOneLabel = methodIL.DefineLabel();
methodIL.Emit(OpCodes.Ldarg_0);
methodIL.Emit(OpCodes.Ldc_I4_0);
methodIL.Emit(OpCodes.Conv_I8);
methodIL.EmitCall(OpCodes.Call, typeof(BigInteger).GetMethod("op_Equality", new Type[] { typeof(BigInteger) , typeof(long) }), null);
methodIL.Emit(OpCodes.Brfalse_S, indexNotZeroLabel);
methodIL.Emit(OpCodes.Ldarg_1);
methodIL.Emit(OpCodes.Ret);
methodIL.MarkLabel(indexNotZeroLabel);
methodIL.Emit(OpCodes.Ldarg_0);
methodIL.Emit(OpCodes.Ldc_I4_1);
methodIL.Emit(OpCodes.Conv_I8);
methodIL.EmitCall(OpCodes.Call, typeof(BigInteger).GetMethod("op_Equality", new Type[] { typeof(BigInteger), typeof(long) }), null);
methodIL.Emit(OpCodes.Brfalse_S, indexNotOneLabel);
methodIL.Emit(OpCodes.Ldarg_2);
methodIL.Emit(OpCodes.Ret);
methodIL.MarkLabel(indexNotOneLabel);
methodIL.Emit(OpCodes.Ldarg_0);
methodIL.Emit(OpCodes.Ldc_I4_1);
methodIL.EmitCall(OpCodes.Call, typeof(BigInteger).GetMethod("op_Implicit", new Type[] { typeof(int) }), null);
methodIL.EmitCall(OpCodes.Call, typeof(BigInteger).GetMethod("op_Subtraction"), null);
methodIL.Emit(OpCodes.Ldarg_2);
methodIL.Emit(OpCodes.Ldarg_1);
methodIL.Emit(OpCodes.Ldarg_2);
methodIL.EmitCall(OpCodes.Call, typeof(BigInteger).GetMethod("op_Addition"), null);
methodIL.Emit(OpCodes.Tailcall);
methodIL.Emit(OpCodes.Call, dynamicMethod);
methodIL.Emit(OpCodes.Ret);
var fibonacci = (Func<BigInteger, BigInteger, BigInteger, BigInteger>)dynamicMethod.CreateDelegate(
typeof(Func<BigInteger, BigInteger, BigInteger, BigInteger>));
var n = 8000;
Console.WriteLine($"\nDynamic Method(n = {n}): ");
var fibonacciNumber = fibonacci(new BigInteger(n), BigInteger.Zero, BigInteger.One);
Console.WriteLine($"Result: {fibonacciNumber}");
Console.ReadLine();
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment