From 8b96190ea92d02f908cab56d52e264842eb9990b Mon Sep 17 00:00:00 2001 From: Lucas Bajolet Date: Tue, 10 Jun 2014 15:41:51 -0400 Subject: [PATCH] lib/math: Added gcd method on Int. Signed-off-by: Lucas Bajolet --- lib/standard/math.nit | 24 ++++++++++++++++++++++++ 1 file changed, 24 insertions(+) diff --git a/lib/standard/math.nit b/lib/standard/math.nit index b7e1ae7..7db6fa3 100644 --- a/lib/standard/math.nit +++ b/lib/standard/math.nit @@ -27,6 +27,30 @@ redef class Int fun bin_or(i: Int): Int is extern "kernel_Int_Int_binor_0" fun bin_xor(i: Int): Int is extern "kernel_Int_Int_binxor_0" fun sqrt: Int `{ return sqrt(recv); `} + # Returns the greatest common divisor of `self` and `o` + # + # assert 54.gcd(24) == 6 + # assert -54.gcd(-24) == 6 + # assert 54.gcd(-24) == -6 + # assert -54.gcd(24) == -6 + # assert 12.gcd(6) == 6 + fun gcd(o: Int): Int + do + if self < 0 then return -(-self).gcd(o) + if o < 0 then return -(self.gcd(-o)) + if self == 0 or o == self then return o + if o == 0 then return self + if self.bin_and(1) == 0 then + if o.bin_and(1) == 1 then + return self.rshift(1).gcd(o) + else + return self.rshift(1).gcd(o.rshift(1)).lshift(1) + end + end + if o.bin_and(1) == 0 then return self.gcd(o.rshift(1)) + if self > o then return (self - o).rshift(1).gcd(o) + return (o - self).rshift(1).gcd(self) + end end redef class Float -- 1.7.9.5