Closed howsiwei closed 4 years ago
On an unrelated note, this is my preferred way of implementing Extended Euclidean algorithm (which is shorter and clearer but may be slightly slower).
void extEuclid(int& d, int& x, int& y, int a, int b) {
if (a == 0) {
d = b; x = 0; y = 1;
return;
}
extEuclid(d, y, x, b % a, a);
x -= b / a * y;
}
https://github.com/stevenhalim/cpbook-code/blob/666991eaa9c08d22228ae469710b1176b35cd35e/ch9/heliocentric.cpp#L9-L11 is not needed in most places since in most intermediate steps it doesn't hurt to have negative values so we only need to ensure the positiveness at the very end. Using %
instead of mod
results in shorter and faster code.
for better readability, the code can be written as follows. tie(a, b) = tuple(b, a%b); tie(x, xx) = tuple(xx, x-qxx); tie(y, yy) = tuple(yy, y-qyy);
Accepted, this is Pythonic way, and I am using C++17 anyway so ok
this is my preferred way of implementing Extended Euclidean algorithm
better not, we prefer iterative?
is not needed in most places since in most intermediate steps it doesn't hurt to have negative values leave it :), it makes the explanation simpler, no need to chase for constant factor speed
Ok, I'll change the multiple assignment code and leave the other two unchanged.
https://github.com/stevenhalim/cpbook-code/blob/666991eaa9c08d22228ae469710b1176b35cd35e/ch9/heliocentric.cpp#L18-L20 use a temporary variable
t
to achieve multiple assignments. For better readability, the code can be written as follows.The downside is that it's slightly longer and requres C++17 for https://en.cppreference.com/w/cpp/language/class_template_argument_deduction. For C++11 and C++14,
make_tuple
can be used instead.