I read in this paper and know that Binary GCD Implementation is proven to be about 2 times faster than Normal GCD Implementation.
Binary Iterative GCD Implementation (wikipedia)
Normal Iterative GCD Implementation
I just wonder if there is an Efficient Binary Extended GCD Implementation and how fast can it be ?
I think Binary and Normal GCD hasn't got a very big complexity difference
Both of Their Complexity is Log2(N) ?
(If a have mistake sorry for that)
Yes, both have same complexity but the implementation could improve the code further more. Since this is one of well-known algorithms and useful in many mathematics problems (especially in divisor problems) I think I could learn something more when I try optimize them to use as a template
Normally, it is not needed, especially in ACM problems, but in some special cases of OI problems, algorithms implemented faster by 1.5x or 2x might get you more points when you cant find a better algorithms
Do you prepare to Olympiads? and which?
I'm prepare for other contest. This would not help me much but I am curious to know better algorithms to solve some old problems, and better implementations for some well-known algorithms