V

Algorithm Visualizer

ZHEN
Share on WeiboShare on XGitHub repositoryAuthor website
Learning ToolsAlgorithm Complexity ReferenceAlgorithm Learning Paths
Data StructuresArrayLinked ListStackQueue and DequeBinary Search TreeBinary HeapHash TableGraphTrieDisjoint Set UnionLRU CacheSkip ListSegment TreeB+ TreeBloom FilterFenwick Tree
SortingBubble SortCocktail Shaker SortBitonic SortSelection SortInsertion SortBinary Insertion SortShell SortMerge SortTop-Down Merge SortQuick SortThree-Way Quick SortDual-Pivot Quick SortHeap SortCounting SortRadix SortBucket Sort
Graph AlgorithmsDijkstra's Shortest PathKruskal's Minimum Spanning TreePrim's Minimum Spanning TreeBellman-Ford Shortest PathsTopological SortFloyd-WarshallStrongly Connected Components2-SATMaximum FlowBipartite MatchingLowest Common AncestorEulerian Path
Dynamic ProgrammingEdit Distance0/1 KnapsackUnbounded KnapsackLongest Common SubsequenceLongest Increasing SubsequenceCoin ChangeStone MergingTraveling Salesperson DPTree Dynamic ProgrammingDigit DPRerooting DP
Backtracking and SearchN-QueensSubsetsPermutationsCombination SumMaze Solving with DFSNumber of IslandsWord SearchSudoku SolverA* Search
StringsKMP String MatchingRabin-Karp String MatchingBoyer-Moore String MatchingManacher's Longest Palindromic SubstringSuffix ArrayLCP ArrayAho-Corasick AutomatonZ Function
Math and Number TheorySieve of EratosthenesLinear SieveEuclidean AlgorithmBinary ExponentiationExtended Euclidean AlgorithmChinese Remainder TheoremEuler's Totient FunctionMiller-Rabin Primality TestFast Fourier TransformPollard's Rho Factorization
Computational GeometryConvex HullRotating CalipersClosest Pair of PointsLine Segment IntersectionBentley-Ottmann Sweep Line
SearchingBinary SearchLower and Upper BoundSearch in a Rotated Sorted ArrayBinary Search on the AnswerTernary Search

Euclidean Algorithm

Greatest common divisors through repeated remainders

Replace a pair without changing its common divisors

The key identity is gcd(a, b) = gcd(b, a mod b). Any number dividing both a and b also divides their remainder, and the converse follows from a = qb + r. Replacing the pair repeatedly makes the second value strictly smaller.

See remainders as leftover rectangles

A geometric interpretation asks for the largest square tile that can cover an a x b rectangle. Cutting as many short-side squares as possible leaves a rectangle whose side is a mod b. Repeating the tiling performs the same recurrence as the arithmetic algorithm.

The player computes gcd(30, 18). Amber outlines squares cut in the current division step, while the dashed rectangle is the remainder still to tile. The smallest final square has side 6.

Find gcd(30, 18) by repeatedly cutting the largest possible squares from a 30 x 18 rectangle.

1function gcd(a: number, b: number): number {
2 while (b !== 0) { // continue while the remainder is nonzero
3 const r = a % b; // remainder of a / b, the leftover rectangle side
4 a = b; // divisor becomes dividend
5 b = r; // remainder becomes divisor
6 }
7 return a; // when b=0, a is the GCD (smallest square side)
8}
Rectangle30×18
Recurrencegcd(30,18) = gcd(18,12) = gcd(12,6) = gcd(6,0) = 6
1 / 5

Logarithmic convergence

The remainder sequence reaches zero in O(log min(a, b)) steps and needs O(1) iterative space. Consecutive Fibonacci numbers produce the classic worst-case sequence because their remainders shrink as slowly as possible.

The extended Euclidean algorithm carries coefficients through the same recurrence to solve ax + by = gcd(a, b), which enables modular inverses.

Start the number-theory path with batch prime generation in the Sieve of Eratosthenes.