Блог пользователя SPyofgame

Автор SPyofgame, история, 4 года назад, По-английски

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 ?

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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)

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Do you prepare to Olympiads? and which?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        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