Closed
Description
As per D. E. Knuth's TAOPC (Vol 1), Extended Euclid (Section 1.2.1, page 13) can be written iteratively, I have seen performance improvement of over 50% when benchmarking it.
Here's a C++ implementation of the idea:
// solves: am + bn = gcd(m,n), m>n
int gcd_fast(int m, int n, int &a, int &b) {
if (!n) {
a = 1, b = 0;
return m;
}
int a_ = 1, b_ = 0, c = m, d = n, q = m / n, r = m % n;
for (a = 0, b = 1; r; q = c / d, r = c % d) {
c = d;
d = r;
tie(a, a_) = make_tuple(a_ - q * a, a);
tie(b, b_) = make_tuple(b_ - q * b, b);
}
return d;
}
I wonder whether this should be added to the tutorial for extended Euclid considering it is a little tricky to prove (mathematical induction btw), but not as tricky as Flows and Li Chao.
Metadata
Metadata
Assignees
Labels
No labels