Iterative and Numeric Algorithms
Open in the Padhaiko app2.1 Algorithm for GCD and Fibonacci number
Iterative algorithms use explicit loops and constant or linear state rather than deep recursion, often reducing both asymptotic time and auxiliary stack space.
Greatest Common Divisor (GCD)
Iterative GCD (Division Method)
For two non-negative integers (not both zero), is the largest positive integer dividing both and . Using the Euclidean division identity with base case :
int gcd(int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return a;
}- Time Complexity: — every two iterations at least halve the smaller argument.
- Space Complexity: auxiliary space.
Fibonacci Numbers: Iterative vs. Naive Recursive
The Fibonacci sequence is defined by , , and for .
| Aspect | Iterative Fibonacci | Naive Recursive Fibonacci |
|---|---|---|
| Method | Maintain two variables prev and curr and loop | Recursively call fib(n-1) + fib(n-2) |
| Time Complexity | additions | where (exponential!) |
| Space Complexity | auxiliary space | call-stack space |
| Cause of Overhead | None; each computed once | Recomputes overlapping subproblems exponentially many times |
long long fib_iter(int n) {
if (n <= 1) return n;
long long prev = 0, curr = 1;
for (int i = 2; i <= n; i++) {
long long next = prev + curr;
prev = curr;
curr = next;
}
return curr;
}2.2 Sequential search
Sequential search (linear search) inspects elements of an unsorted array one by one from left to right until the target key is found or the array ends.
int sequentialSearch(int A[], int n, int key) {
for (int i = 0; i < n; i++) {
if (A[i] == key) {
return i; // found at index i
}
}
return -1; // not found
}- Best Case: key comparison .
- Worst Case: is at or not present key comparisons .
- Average Case (successful search, uniform probability at each index):
- Space Complexity: auxiliary space. (Works on unsorted arrays; no preprocessing needed.)
2.3 Review of bubble sort, selection sort, and insertion sort algorithms
All three classical elementary sorting algorithms sort an array in-place ( extra space) using worst-case comparisons, yet they differ sharply in best-case behavior, swaps, and stability.
void bubbleSort(int A[], int n) {
for (int i = 0; i < n - 1; i++) {
int swapped = 0;
for (int j = 0; j < n - 1 - i; j++) {
if (A[j] > A[j + 1]) {
int tmp = A[j]; A[j] = A[j + 1]; A[j + 1] = tmp;
swapped = 1;
}
}
if (!swapped) break; // early exit on already-sorted input
}
}
void selectionSort(int A[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (A[j] < A[minIdx]) minIdx = j;
}
int tmp = A[i]; A[i] = A[minIdx]; A[minIdx] = tmp;
}
}
void insertionSort(int A[], int n) {
for (int i = 1; i < n; i++) {
int key = A[i], j = i - 1;
while (j >= 0 && A[j] > key) {
A[j + 1] = A[j];
j--;
}
A[j + 1] = key;
}
}| Algorithm | Best Case Time | Average / Worst Time | Worst Swaps / Writes | Space | Stable | Adaptive |
|---|---|---|---|---|---|---|
| Bubble Sort (with early-exit flag) | swaps | Yes | Yes | |||
| Selection Sort | swaps () | No | No | |||
| Insertion Sort | shifts | Yes | Yes |
1
- Trace Insertion Sort on pass by pass, and count the exact number of element shifts (and key comparisons) performed.
- How many total function calls does the naive recursive Fibonacci algorithm make to compute (with base cases ), compared to the loop iterations of
fib_iter(6)?
Insertion Sort trace on :
- Pass (
key = 10): Compare (shift right) . ( comparison, shift) - Pass (
key = 14): Compare (shift ), then (false) . ( comparisons, shift) - Pass (
key = 37): Compare (false) . ( comparison, shifts) - Pass (
key = 13): Compare (all , shift all ), then (false) . ( comparisons, shifts)
Total element shifts , and total key comparisons .
Counting recursive calls for : Let be the number of calls made by fib(n): , and :
- recursive calls (note ).
By contrast, fib_iter(6) runs the for loop for — just iterations ().
- Sorted array: with element shifts and comparisons.
- Naive recursive
fib(6)makes function calls, whereasfib_iter(6)executes loop iterations to return .
2.4 Number theoretic notations
Number-theoretic algorithms operate on integers and modular rings .
Core Number-Theoretic Notations and Theorems
- Divisibility (): Integer divides if for some ; otherwise .
- Division Theorem: For any and , there exist unique integers (quotient) and (remainder) such that:
- Congruence Modulo (): Holds iff , equivalently .
- Greatest Common Divisor & Coprimality: is the largest positive common divisor. Two integers are relatively prime (coprime) if .
- Modular Multiplicative Inverse (): An integer such that . It exists if and only if .
- Euler's Totient Function : The count of integers in coprime to , equal to (the multiplicative group modulo ). For :
For a prime , .
2.5 Euclid's and Extended Euclid's algorithms
Euclid's Algorithm
Euclid's GCD Recursion Theorem & Lamé's Bound
For any integers and :
Lamé's Theorem (Running Time): If Euclid's algorithm takes division steps on with , then and . Consequently, the number of divisions is (at most times the number of decimal digits of ).
Extended Euclidean Algorithm
The Extended Euclidean Algorithm computes not only , but also integer Bézout coefficients satisfying:
int extendedGcd(int a, int b, int *x, int *y) {
if (b == 0) {
*x = 1;
*y = 0;
return a;
}
int x1, y1;
int d = extendedGcd(b, a % b, &x1, &y1);
*x = y1;
*y = x1 - (a / b) * y1;
return d;
}Finding Modular Inverses: If , then , so is the unique multiplicative inverse .
2
- Use the Extended Euclidean Algorithm to find and integers such that .
- Find the multiplicative inverse , and solve the modular linear equation .
Extended Euclid on : Forward divisions:
- .
Back-substitution (or recursive unwinding ):
- .
Check: .
Modular inverse and solving :
- For : , , . Thus , so .
- For : . Since , there are distinct solutions modulo . Dividing by gives . Since , . Thus:
The solutions modulo are and .
- with ().
- ; has solutions: .
2.6 Solving modular linear equations using Chinese remainder theorem
Chinese Remainder Theorem (CRT)
Let be pairwise relatively prime positive integers ( for ), and let . Then the system of congruences:
has a unique solution modulo , given explicitly by:
where and (computed via the Extended Euclidean Algorithm).
When solving a single modular linear equation where factors into pairwise coprime moduli, we can split it into smaller congruences , solve each modulo , and recombine with CRT.
2.7 Fermat's theorem
Fermat's Little Theorem
If is a prime number, then for every integer not divisible by ():
Equivalently, for every integer (whether or ):
Applications:
- Fast Modular Exponentiation (
MODULAR-EXPONENTIATION): Using repeated squaring on the binary expansion of exponent , takes modular multiplications, and Fermat's theorem reduces large exponents modulo when is prime. - Fermat Primality Test (and Carmichael Numbers): If for some , then is definitely composite ( is a Fermat witness). However, the converse fails: composite numbers that satisfy for all coprime to are called Carmichael numbers (smallest: ).
2.8 Miller-Rabin randomized primality test and algorithm
The Miller-Rabin primality test overcomes Carmichael numbers by exploiting a stronger property of primes: modulo a prime , the equation has only two square roots, namely and (no nontrivial square roots of unity).
Miller-Rabin Witness Decomposition
Write an odd integer as:
For a randomly chosen base , compute , then square repeatedly for :
- If or for some , then passes for base ( is probably prime).
- Otherwise, is a witness to the compositeness of : either or a nontrivial square root of modulo was found, proving is definitely composite.
// Returns 1 if a is a definite witness that n is composite, 0 if n passes
int witness(long long a, long long n) {
long long d = n - 1;
int s = 0;
while (d % 2 == 0) { d /= 2; s++; }
long long x = modPow(a, d, n); // a^d mod n via repeated squaring
if (x == 1 || x == n - 1) return 0;
for (int r = 1; r < s; r++) {
x = (x * x) % n;
if (x == n - 1) return 0;
if (x == 1) return 1; // nontrivial square root of 1 found
}
return 1; // composite
}
// Runs k independent random trials; error probability <= (1/4)^k
int millerRabin(long long n, int k) {
if (n < 2) return 0;
if (n == 2 || n == 3) return 1;
if (n % 2 == 0) return 0;
for (int i = 0; i < k; i++) {
long long a = 2 + rand() % (n - 3);
if (witness(a, n)) return 0; // definitely composite
}
return 1; // probably prime
}- Correctness & Complexity: For every odd composite , at least of bases are Miller-Rabin witnesses. Thus after independent random trials, the probability that a composite number passes all tests is at most (zero false negatives for primes). Total time complexity is bit operations (or modular multiplications).
3
- Solve the simultaneous congruences using the Chinese Remainder Theorem:
- Apply the Miller-Rabin witness test to the Carmichael number with base , and show explicitly how it detects compositeness even though .
Chinese Remainder Theorem solution: Here ; ; (pairwise coprime), so .
- : .
- : .
- : .
Combine:
Check: , , .
Miller-Rabin test on with : Factor , so and .
- Compute : since , .
- Square repeatedly ():
Since appeared immediately after , is a nontrivial square root of ! Thus proves is composite (even though ).
- Unique CRT solution: .
- For () and , the squaring sequence is , revealing the nontrivial square root of and proving is composite.
Exercises
Exercises — Iterative and Numeric Algorithms
Write iterative and recursive algorithms to compute the -th Fibonacci number (). Compare their time and space complexities, and determine the exact number of recursive calls needed to compute .
Iterative vs. recursive algorithms and complexity:
- Iterative: Loops updating
prev, currin time and space. - Naive Recursive: Calls
fib(n-1) + fib(n-2), yielding recurrence time and call-stack space.
Exact call count for : Using and : , , , and calls (returning ).
Iterative Fibonacci takes time and space; naive recursive Fibonacci takes time and space, making recursive calls to compute .
Compare Bubble Sort, Selection Sort, and Insertion Sort on the array by counting the exact number of element swaps performed by Selection Sort vs. element swaps performed by standard Bubble Sort (without early exit, and with early exit). Which of the three is both stable and adaptive?
Selection Sort swaps on ():
- : min in is (idx 1), swap ( swap)
- : min in is (idx 3), swap ( swap)
- : min in is (idx 2), swap with self or skip ( effective swaps; unconditional swap gives swaps)
- : min in is (idx 3), already in place.
Total effective swaps (at most swaps total), while comparisons are always .
Bubble Sort swaps on :
- Pass 1 (): swap ; swap ; swap ; no swap. ( swaps)
- Pass 2 (): ok; swap ; ok. ( swap)
- Pass 3 (): , ok early exit triggers here ( swaps); without early exit, Pass 4 also runs with swaps.
Total swaps (equal to the inversion count of ). Both Bubble Sort (with early exit) and Insertion Sort are stable and adaptive; Selection Sort is neither.
Selection Sort performs comparisons and effective swaps (at most ); Bubble Sort performs swaps (terminating after Pass 3 with early exit). Bubble Sort (with early exit) and Insertion Sort are both stable and adaptive.
- Apply the Extended Euclidean Algorithm to find and integers satisfying .
- Find the multiplicative inverse of modulo .
Extended Euclid on :
- .
Back-substituting:
So .
Multiplicative inverse :
- .
Thus , so .
- with .
- .
Using the Chinese Remainder Theorem, find the smallest positive integer satisfying the system of congruences:
Computing , , and inverses : Moduli are pairwise coprime, so :
- : .
- : .
- : .
Combining into the unique solution modulo :
Reducing modulo : .
The smallest positive solution is (unique modulo ).
- Use Fermat's Little Theorem to compute .
- Explain what a Carmichael number is (using ) and why the Miller-Rabin randomized primality test detects composite numbers that fool the simple Fermat test, stating the error probability after independent trials.
Evaluating : Since is prime and , Fermat's Little Theorem gives . Since :
Carmichael numbers vs. Miller-Rabin: A Carmichael number is a composite integer (e.g. ) that satisfies for every coprime to , causing the simple Fermat test to misclassify it as prime for almost all bases. Miller-Rabin decomposes and inspects the squaring chain : any nontrivial square root of (an whose square is ) proves is composite. For any odd composite , at most of bases lie; after independent trials, the false-prime error probability is at most .
- .
- Carmichael numbers pass for all coprime , defeating the Fermat test; Miller-Rabin catches them by detecting nontrivial square roots of , achieving error probability after random trials.