klefki.algorithms
¶
Module Contents¶
Functions¶
|
Returns a three-tuple (gcd, x, y) such that |
|
Returns the result of n * x, computed using |
-
klefki.algorithms.
extended_euclidean_algorithm
(a: int, b: int, one=1, zero=0) → Tuple[int, int, int]¶ Returns a three-tuple (gcd, x, y) such that a * x + b * y == gcd, where gcd.
This function implements the extended Euclidean algotithm and runs in O(log b) in the worst case
-
klefki.algorithms.
double_and_add_algorithm
(times: int, x: T, init: T) → T¶ Returns the result of n * x, computed using the double and add algorithm.