ZuoTi.Pro
Question

The following variant of Euclid algorithm is suggested: Instead of replacing v by u mod v...

The following variant of Euclid algorithm is suggested: Instead of replacing v by u mod v in division step, replace it with |(u mod v)-v| if u mod v> 1/2 v. For example if u=26 and v=7 then the gcd(26,7) =〖 gcd〗⁡(-2,7); where -2 is the reminder of smallest magnitude when multiples by 7 are subtracted from 26. Compare this process with Euclid algorithm and estimate the average number of divisions this method saves (if any).

engineering   Computer-Science   
0 0
Add a comment Improve this question Transcribed image text
Next > < Previous
Sort answers by oldest

Homework Answers

Answer #1

0 0
Add a comment
Know the answer?
Add Answer to:
The following variant of Euclid algorithm is suggested: Instead of replacing v by u mod v...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions

  • We discuss the Euclidean algorithm that finds the greatest common divisor of 2 numbers u and...

    We discuss the Euclidean algorithm that finds the greatest common divisor of 2 numbers u and v. We want to extend and compute the gcd of n integers gcd⁡(u1,u2,….un). One way to do it is to assume all numbers are non-negative, so if only one of if uj≠0 it is the gcd. Otherwise replace uk by uk mod uj  for all k≠j where uj is the minimum of the non-zero elements (u’s). The algorithm can be made significantly faster if one...

  • We discuss the Euclidean algorithm that finds the greatest common divisor of 2 numbers u and...

    We discuss the Euclidean algorithm that finds the greatest common divisor of 2 numbers u and v. We want to extend and compute the gcd of n integers gcd⁡(u_1,u_2,….u_n). One way to do it is to assume all numbers are non-negative, so if only one of if u_j≠0 it is the gcd. Otherwise replace u_k by u_k mod u_j for all k≠j where u_j is the minimum of the non-zero elements (u’s). The algorithm can be made significantly faster if...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT