diff options
Diffstat (limited to 'stdlib/source/lux/data/number')
-rw-r--r-- | stdlib/source/lux/data/number/int.lux | 20 | ||||
-rw-r--r-- | stdlib/source/lux/data/number/nat.lux | 4 |
2 files changed, 23 insertions, 1 deletions
diff --git a/stdlib/source/lux/data/number/int.lux b/stdlib/source/lux/data/number/int.lux index 8d24d729d..e5b753725 100644 --- a/stdlib/source/lux/data/number/int.lux +++ b/stdlib/source/lux/data/number/int.lux @@ -127,7 +127,25 @@ (-> Int Int Int) (case b +0 a - _ (gcd b (..mod b a)))) + _ (gcd b (..% b a)))) + +(def: #export (co-prime? a b) + (-> Int Int Bit) + (..= +1 (..gcd a b))) + +## https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm +(def: #export (extended_gcd a b) + {#.doc "Extended euclidean algorithm."} + (-> Int Int [[Int Int] Int]) + (loop [x +1 x1 +0 + y +0 y1 +1 + a1 a b1 b] + (case b1 + +0 [[x y] a1] + _ (let [q (/ b1 a1)] + (recur x1 (- (* q x1) x) + y1 (- (* q y1) y) + b1 (- (* q b1) a1)))))) (def: #export (lcm a b) {#.doc "Least Common Multiple."} diff --git a/stdlib/source/lux/data/number/nat.lux b/stdlib/source/lux/data/number/nat.lux index b1504f048..267846c89 100644 --- a/stdlib/source/lux/data/number/nat.lux +++ b/stdlib/source/lux/data/number/nat.lux @@ -129,6 +129,10 @@ 0 a _ (gcd b (..% b a)))) +(def: #export (co-prime? a b) + (-> Nat Nat Bit) + (..= 1 (..gcd a b))) + (def: #export (lcm a b) {#.doc "Least Common Multiple."} (-> Nat Nat Nat) |