Tag

algorithms

4 entries tagged algorithms.

Computing & AI

RecursionRecursion is when a definition or procedure refers to a smaller or simpler instance of itself.

Fast Modular Powers: Repeated SquaringComputing 13²⁷ as an ordinary integer creates a large number only to discard almost all of it when taking a remainder. Repeated squaring keeps the part we need at every step.
GCD and the Euclidean AlgorithmImagine cutting two ropes into equal-length pieces without leaving a remainder. The longest possible piece length is their greatest common divisor, abbreviated gcd. For integers, divisors are exact: 6 divides both 48 and 18, and no larger positive integer does.
Modular Inverses and Extended EuclidAn ordinary reciprocal undoes multiplication: multiplying by 3 and then by 1/3 returns the starting value. Modulo n, we need an integer that undoes multiplication up to a remainder.