From 30ba27aadb6f3dc9f51c3f5fb6dae56b2aabfbf1 Mon Sep 17 00:00:00 2001
From: arphaman <arphaman@gmail.com>
Date: Thu, 5 Sep 2013 12:44:38 +0100
Subject: changed ipow to use exponentation by squaring

---
 lib/Numerical/Integer.cpp | 14 +++++++++-----
 test/Unit/ipow.cpp        |  4 ++++
 2 files changed, 13 insertions(+), 5 deletions(-)

diff --git a/lib/Numerical/Integer.cpp b/lib/Numerical/Integer.cpp
index fd3060e..4ddd785 100644
--- a/lib/Numerical/Integer.cpp
+++ b/lib/Numerical/Integer.cpp
@@ -1,14 +1,18 @@
 #include "Numerical/Integer.h"
 
+// Exponentation by squaring
 template<typename T>
 static T ipow(T x, T y) {
-  if(y >= 0) {
-    T result = 1;
-    for(; y != 0; --y)
+  if(y < 0) return 0;
+
+  T result = 1;
+  while (y != 0) {
+    if ((y & 1) == 1)
       result *= x;
-    return result;
+    y >>= 1;
+    x *= x;
   }
-  return 0;
+  return result;
 }
 
 LIBFLANG_ABI int8_t  libflang_pow_i1_i1(int8_t x, int8_t y) {
diff --git a/test/Unit/ipow.cpp b/test/Unit/ipow.cpp
index 0956bb2..91cff22 100644
--- a/test/Unit/ipow.cpp
+++ b/test/Unit/ipow.cpp
@@ -34,5 +34,9 @@ int main() {
     return 1;
   if(testPowI4(-1,-1,0))
     return 1;
+  if(testPowI4(1000,2,1000000))
+    return 1;
+  if(testPowI4(1000,3,1000000000))
+    return 1;
   return 0;
 }
-- 
cgit v1.2.1