Integer exponentiation should avoid using floats (#3163)

* Int exponentation is now correctly processed using exponentiation by squaring
crystal-lang · Aug 18, 2016 · 2300f7c · 2300f7c
1 parent e872c71
commit 2300f7c
Showing 2 changed files with 14 additions and 2 deletions.
diff --git a/spec/std/int_spec.cr b/spec/std/int_spec.cr
@@ -33,6 +33,12 @@ describe "Int" do
       end
     end
 
+    it "should work with large integers" do
+      x = 51_i64 ** 11
+      x.should eq(6071163615208263051_i64)
+      x.should be_a(Int64)
+    end
+
     describe "with float" do
       assert { (2 ** 2.0).should be_close(4, 0.0001) }
       assert { (2 ** 2.5_f32).should be_close(5.656854249492381, 0.0001) }

diff --git a/src/int.cr b/src/int.cr
@@ -189,8 +189,14 @@ struct Int
       raise ArgumentError.new "cannot raise an integer to a negative integer power, use floats for that"
     end
 
-    # TODO: this can probably be optimized by not using float pow
-    self.class.new(to_f ** exponent)
+    result = self.class.new(1)
+    k = self
+    while exponent > 0
+      result *= k if exponent & 0b1 != 0
+      k *= k
+      exponent = exponent.unsafe_shr(1)
+    end
+    result
   end
 
   # Returns the value of raising *self* to the power of *exponent*.