SPyofgame's blog

By SPyofgame, history, 6 weeks ago, In English,

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 ?

 
 
 
 
  • Vote: I like it
  • +4
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

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)

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Do you prepare to Olympiads? and which?

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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