search

EbTech / rust-algorithms

Common data structures and algorithms in Rust
MIT License
3.77k stars 220 forks source link

Implement extended_gcd_by_iter #9

Closed Nugine closed 5 years ago

Nugine commented 5 years ago

Another implemention of exgcd

Nugine commented 5 years ago

Reference: http://anh.cs.luc.edu/331/notes/xgcd.pdf http://math.cmu.edu/~bkell/21110-2010s/extended-euclidean.html

The iterative version is based on a algorithm different from the recursive version. For the purpose of education, I prefer to maintain both of them. In fact, The two versions have the same time complexity. Iteration does save time and memory, although the improvement is not obvious.