gcd_11

[Marco Bodrato]

Ciao,

Il Sab, 17 Agosto 2019 9:15 am, Niels Möller ha scritto:
> nisse at lysator.liu.se (Niels Möller) writes:
>
>> Seems to work, but not particularly fast :-(
>
> And I think I understand why... I think progress for a gcd algorithm
> like this needs to be measured in terms of bitsize (a) + bitsize (b),
> not bitsize (max (a,b)).

> I now think that any efficient iteration for small-size gcd ought to
> care which one of a, b is smallest, and make it impossible or very
> unlikely that the iteration makes min(a,b) grow.

Well, the smallest is a candidate result, so I agree, it should never be
lost.

Moreover... if u and v has more or less the same size, then u+3v is around
4u, even if we can divide it by 8... well, we obtain something around u/2,
we gained just one bit...
With |u-v|/2 we surely gain one bit because of the division, and maybe we
gain something more thanks to cancellation of the highest bits.

If v << u, then it is probably better to explore u-3v or even larger
multiple of v... but maybe this exploration is not much more efficient
than the current loop...

Ĝis,
m