diff options
| -rw-r--r-- | lib/pure/math.nim | 71 |
1 files changed, 37 insertions, 34 deletions
diff --git a/lib/pure/math.nim b/lib/pure/math.nim index 73a60e974..c9b2162e9 100644 --- a/lib/pure/math.nim +++ b/lib/pure/math.nim @@ -58,6 +58,7 @@ import std/private/since # of the standard library! import std/[bitops, fenv] +import system/countbits_impl when defined(nimPreviewSlimSystem): import std/assertions @@ -1229,40 +1230,42 @@ func gcd*[T](x, y: T): T = swap x, y abs x -func gcd*(x, y: SomeInteger): SomeInteger = - ## Computes the greatest common (positive) divisor of `x` and `y`, - ## using the binary GCD (aka Stein's) algorithm. - ## - ## **See also:** - ## * `gcd func <#gcd,T,T>`_ for a float version - ## * `lcm func <#lcm,T,T>`_ - runnableExamples: - doAssert gcd(12, 8) == 4 - doAssert gcd(17, 63) == 1 - - when x is SomeSignedInt: - var x = abs(x) - else: - var x = x - when y is SomeSignedInt: - var y = abs(y) - else: - var y = y - - if x == 0: - return y - if y == 0: - return x - - let shift = countTrailingZeroBits(x or y) - y = y shr countTrailingZeroBits(y) - while x != 0: - x = x shr countTrailingZeroBits(x) - if y > x: - swap y, x - x -= y - y shl shift - +when useBuiltins: + ## this func uses bitwise comparisons from C compilers, which are not always available. + func gcd*(x, y: SomeInteger): SomeInteger = + ## Computes the greatest common (positive) divisor of `x` and `y`, + ## using the binary GCD (aka Stein's) algorithm. + ## + ## **See also:** + ## * `gcd func <#gcd,T,T>`_ for a float version + ## * `lcm func <#lcm,T,T>`_ + runnableExamples: + doAssert gcd(12, 8) == 4 + doAssert gcd(17, 63) == 1 + + when x is SomeSignedInt: + var x = abs(x) + else: + var x = x + when y is SomeSignedInt: + var y = abs(y) + else: + var y = y + + if x == 0: + return y + if y == 0: + return x + + let shift = countTrailingZeroBits(x or y) + y = y shr countTrailingZeroBits(y) + while x != 0: + x = x shr countTrailingZeroBits(x) + if y > x: + swap y, x + x -= y + y shl shift + func gcd*[T](x: openArray[T]): T {.since: (1, 1).} = ## Computes the greatest common (positive) divisor of the elements of `x`. ## |