search

flintlib / arb

Arb has been merged into FLINT -- use https://github.com/flintlib/flint/ instead
http://arblib.org/
GNU Lesser General Public License v2.1
457 stars 137 forks source link

add fmpzi_gcd_shortest #435

Closed tthsqe12 closed 2 years ago

tthsqe12 commented 2 years ago

This is the nemo version

fredrik-johansson commented 2 years ago

Nice! Want me to figure out the cutoffs for using it?

tthsqe12 commented 2 years ago

Sure, but unfortunately its complexity has completely different characteristcs from the Euclidean algorithm. If Euclid does just a few iterations, it will be hard to beat that.

fredrik-johansson commented 2 years ago

So for huge numbers, you'd want a version of the Euclidean algorithm that quits after a few iterations?

fredrik-johansson commented 2 years ago

After some quick testing, your algorithm seems to win pretty consistently for balanced GCDs above 64 bits. (So perhaps a 2-limb Euclidean (or binary) GCD would be useful.)

However, your algorithm seems to perform much worse than the Euclidean one for highly unbalanced operands. For example, it is slower for gcd(10^6 bits, 10^5 bits).

I think instead of changing your algorithm, the main fmpzi_gcd function could just check if the operands are unbalanced, then do a single divrem or divrem_approx before dispatching to the right algorithm. Does that make sense?

tthsqe12 commented 2 years ago

For the first question, probably "no" because the second question is probably "yes": do some divisions until the operands are balanced.

tthsqe12 commented 2 years ago

Ideally you would want a quasi-linear algorithm that deals directly with the quotient sequence, but that is a lot of work, so this is a compromise.

fredrik-johansson commented 2 years ago

Sure.