[gnome-calculator] Fixed modulo calculations

[Arth Patel <arthpatel src gnome org>]

commit 5a4b32820877517eee1ebd6928a3a649f76aab2a
Author: Garima Joshi <garimajoshi3 yahoo in>
Date:   Sun May 19 23:52:22 2013 +0530

    Fixed modulo calculations

 src/equation-parser.vala |   21 +++++++++++++++++++++
 src/number.vala          |   22 ++++++++++++++++++++++
 2 files changed, 43 insertions(+), 0 deletions(-)
---
diff --git a/src/equation-parser.vala b/src/equation-parser.vala
index acbdd9d..3df6c9a 100644
--- a/src/equation-parser.vala
+++ b/src/equation-parser.vala
@@ -474,6 +474,27 @@ public class ModulusDivideNode : LRNode
         base (parser, token, precedence, associativity);
     }
 
+    public override Number? solve ()
+    {
+        if (left is XPowYNode)
+        {
+            var base_value = left.left.solve ();
+            var exponent = left.right.solve ();
+            var mod = right.solve ();
+            if (base_value == null || exponent == null || mod == null)
+                return null;
+            return base_value.modular_exponentiation (exponent, mod);
+        }
+        else
+        {
+            var l = left.solve ();
+            var r = right.solve ();
+            if (l == null || r == null)
+                return null;
+            return solve_lr (l, r);
+        }
+    }
+
     public override Number solve_lr (Number l, Number r)
     {
         return l.modulus_divide (r);
diff --git a/src/number.vala b/src/number.vala
index 2ca0f62..12d52ef 100644
--- a/src/number.vala
+++ b/src/number.vala
@@ -1171,6 +1171,28 @@ public class Number
         return z;
     }
 
+    /* Sets z = x ^ y mod p */
+    public Number modular_exponentiation (Number exp, Number mod)
+    {
+        var ans = new Number.integer (1);
+        var base_value = modulus_divide (mod);
+        var exp_value = exp.copy ();
+        var two = new Number.integer (2);
+        while (!exp_value.is_zero ())
+        {
+            bool is_even = exp_value.modulus_divide (two).is_zero ();
+            if (!is_even)
+            {
+                ans = ans.multiply (base_value);
+                ans = ans.modulus_divide (mod);
+            }
+            base_value = base_value.multiply (base_value);
+            base_value = base_value.modulus_divide (mod);
+            exp_value = exp_value.divide_integer (2).floor ();
+        }
+        return ans.modulus_divide (mod);
+    }
+
     /* Sets z = sin x */
     public Number sin (AngleUnit unit = AngleUnit.RADIANS)
     {