perf(calc): use exponentiation by squaring

move calc things in new module

3 files changed, 43 insertions, 36 deletions

diff --git a/lib/elixir_math_parser.ex b/lib/elixir_math_parser.ex
index 71baf3c..4a96daf 100644
--- a/lib/elixir_math_parser.ex
+++ b/lib/elixir_math_parser.ex
@@ -3,9 +3,10 @@ defmodule ElixirMathParser do
   Documentation for `ElixirMathParser`.
   """
   alias ElixirMathParser.Math.Rational
+  alias ElixirMathParser.Math.Calc
 
   defp reduce_to_value({:int, _line, value}, _state) do
-    {:ok, Rational.new(value, 1)}
+    {:ok, Rational.new(value)}
   end
 
   defp reduce_to_value({:var, line, var}, state) do
@@ -48,7 +49,7 @@ defmodule ElixirMathParser do
     with {:ok, op} <- reduce_to_value(lhs, state),
          true <- Rational.denominator(op) == 1,
          true <- Rational.numerator(op) >= 0 do
-      {:ok, factor(Rational.numerator(op), 1)}
+      {:ok, Calc.factorial(Rational.numerator(op)) |> Rational.new()}
     else
       {:error, line, reason} -> {:error, line, reason}
       false -> {:error, "must have a positive integer for the factorial"}
@@ -58,27 +59,18 @@ defmodule ElixirMathParser do
   defp reduce_to_value({:exp_op, lhs, rhs}, state) do
     with {:ok, op1} <- reduce_to_value(lhs, state),
          {:ok, op2} <- reduce_to_value(rhs, state) do
-      if Rational.denominator(op2) == 1 do
-        {:ok, expo(op1, Rational.numerator(op2), Rational.new(1, 1))}
-      else
-        {:error, "unsupported operation"}
-      end
+      {:ok,
+       Calc.pow(
+         op1,
+         if Rational.denominator(op2) == 1 do
+           Rational.numerator(op2)
+         else
+           op2
+         end
+       )}
     end
   end
 
-  # Functions for maths
-
-  defp factor(n, acc) when n > 0, do: factor(n - 1, acc * n)
-  defp factor(0, acc), do: Rational.new(acc, 1)
-
-  defp expo(value, exponent, acc) when exponent > 0,
-    do: expo(value, exponent - 1, Rational.mult(acc, value))
-
-  defp expo(value, exponent, acc) when exponent < 0,
-    do: expo(value, exponent + 1, Rational.div(acc, value))
-
-  defp expo(_value, 0, acc), do: acc
-
   defp evaluate_tree([{:assign, {:var, line, lhs}, rhs} | tail], state) do
     with {:ok, val} <- reduce_to_value(rhs, state) do
       evaluate_tree(tail, Map.merge(state, %{lhs => val}))
@@ -89,13 +81,7 @@ defmodule ElixirMathParser do
 
   defp evaluate_tree([{:eval, expr} | tail], state) do
     with {:ok, expr} <- reduce_to_value(expr, state) do
-      num = Rational.numerator(expr)
-      den = Rational.denominator(expr)
-
-      case den do
-        1 -> IO.puts(num)
-        _ -> IO.puts("#{num}/#{den}")
-      end
+      IO.puts(expr)
 
       evaluate_tree(tail, state)
     end
diff --git a/lib/math/Calc.ex b/lib/math/Calc.ex
new file mode 100644
index 0000000..7dc5fcc
--- /dev/null
+++ b/lib/math/Calc.ex
@@ -0,0 +1,28 @@
+defmodule ElixirMathParser.Math.Calc do
+  alias ElixirMathParser.Math.Rational
+  def factorial(n), do: factorial_rec(n, 1)
+  defp factorial_rec(n, acc) when n > 0, do: factorial_rec(n - 1, acc * n)
+  defp factorial_rec(0, acc), do: acc
+
+  def pow(value, exponent), do: pow_rec(value, exponent, Rational.new(1))
+
+  defp pow_rec(value, exponent, acc) when is_integer(exponent) do
+    case exponent do
+      0 ->
+        acc
+
+      _ when exponent < 0 ->
+        pow_rec(Rational.new(1, value), -exponent, acc)
+
+      _ when Kernel.rem(exponent, 2) == 0 ->
+        pow_rec(Rational.mult(value, value), Kernel.div(exponent, 2), acc)
+
+      _ ->
+        pow_rec(
+          Rational.mult(value, value),
+          Kernel.div(exponent - 1, 2),
+          Rational.mult(acc, value)
+        )
+    end
+  end
+end
diff --git a/lib/math/rational.ex b/lib/math/rational.ex
index 3aba567..018f69b 100644
--- a/lib/math/rational.ex
+++ b/lib/math/rational.ex
@@ -405,11 +405,8 @@ defmodule ElixirMathParser.Math.Rational do
   """
   def to_string(rational)
 
-  def to_string(%Rational{numerator: numerator, denominator: denominator}) do
-    "#{numerator}" <>
-      if denominator != 1 do
-        "/#{denominator}"
-      end
+  def to_string(%Rational{numerator: num, denominator: den}) do
+    "#{num}" <> if den != 1, do: "/#{den}", else: ""
   end
 
   defimpl String.Chars, for: Rational do
@@ -440,11 +437,7 @@ defmodule ElixirMathParser.Math.Rational do
         {denominator, numerator}
       end
 
-    # if denominator == 1 do
-    #   Kernel.div(numerator, gcdiv)
-    # else
     %Rational{numerator: Kernel.div(numerator, gcdiv), denominator: denominator}
-    # end
   end
 
   # Calculates the Greatest Common denominator of two numbers.