• Support PF! Buy your school textbooks, materials and every day products Here!

Euclidean Algorithm terminates in at most 7x the digits of b

  • #1
317
26

Homework Statement


please see the image

Homework Equations


I'm not sure if this is relevant:
##r_2 \leq \frac{1}{2}r_1## ... ##r_n \leq (\frac{1}{2})^nr_1##

The Attempt at a Solution


i have shown that ##r_{i+2} < r_i## by showing the ##r_{i+2} - r_i## is negative, but how do I show that the number of steps is at most ##2 \log_{2}b##
 

Attachments

Answers and Replies

  • #2
andrewkirk
Science Advisor
Homework Helper
Insights Author
Gold Member
3,830
1,417
i have shown that ##r_{i+2} < r_i##
That is not what the question requires though. It requires to show that ##r_{i+2} < \frac12 r_i##. Have you shown that?
how do I show that the number of steps is at most ##2 \log_{2}b##
Once you have shown ##r_{i+2} < \frac12 r_i## you can work out how many steps it takes to reduce the remainder to 1 or less, as the algorithm terminates when the remainder reaches 1 or 0. Use the fact that the remainder halves every two steps and that initially it is no greater than ##b##..
 
  • #3
317
26
That is not what the question requires though. It requires to show that ##r_{i+2} < \frac12 r_i##. Have you shown that?
Once you have shown ##r_{i+2} < \frac12 r_i## you can work out how many steps it takes to reduce the remainder to 1 or less, as the algorithm terminates when the remainder reaches 1 or 0. Use the fact that the remainder halves every two steps and that initially it is no greater than ##b##..
Sorry I meant ##2r_{i+2} < r_i##
 
  • #4
317
26
Use the fact that the remainder halves every two steps and that initially it is no greater than bbb..
I am not sure if I am doing this completely right or wrong.

proof of ##r_{i+2} < \frac{1}{2}r_i:##

Let ##a - bq_1 = r_1## s.t. ##b=r_0##

##(case 1):##
If ##b=r_0< \frac{1}{2}a## then ##q_1 \geq 2## so that ##r_1 < r_0##.
Furthermore, in ##r_0 - r_1q_2 = r_2##, since ##r_1 \leq \frac{1}{2}r_0## then it must be that ##q_2 \geq 2## so that ##r_2 < r_1##.
Therefore, ##r_2 < r_1 < \frac{1}{2}r_0## or ##r_{i+2}<r_{i+1}< \frac{1}{2}r_i## or simply ##r_{i+2}<\frac{1}{2}r_i##.

##(case 2):##
If ##b=r_0> \frac{1}{2}a## then ## a- r_0q_1 = r_1## such that ##r_1 < \frac{1}{2}a## and ##r_1 < r_0## and ##q_1=1##

##(subcase 2.1):## If ##r_1 > \frac{1}{2}r_0## then definitely, ##r_2 < \frac{1}{2}r_0## or ##r_{i+2}<\frac{1}{2}r_i##

##(subcase 2.2)## If ##r_1 < \frac{1}{2}r_0## then ##q_2 \geq 2## so that ##r_2 < r_1##.
Therefore, ##r_2<r_1< \frac{1}{2}r_0## or ##r_{i+2}<r_{i+1}< \frac{1}{2}r_i##

From here, I am struggling to apply logarithms to show the final step. Can you give me hints?
 
  • #5
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,315
1,005
You may get more response if you show the image rather than just giving the link. I'll do that much for you.

The image for the link you posted:
ch5-1-png.png

Notice that if ##\ b\ ,\ ## which is also ##\ r_0\ ,\ ## has k decimal digits, then b < 10k .
 
Last edited:
  • Like
Likes Terrell
  • #7
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,315
1,005
Can you give me hints?
Another hint:

What upper bound on rn will ensure that the algorithm terminates in at most n steps.
 
  • #8
317
26
I figured that the inequality ##b(\frac{1}{2})^\frac{n}{2} < 1## then taking the log of both sides should be enough...?
 
  • #9
317
26
What upper bound on rn will ensure that the algorithm terminates in at most n steps.
##r_n \leq 1##

Notice that if b , b , \ b\ ,\ which is also r0 , r0 , \ r_0\ ,\ has k decimal digits, then b < 10k .
yes i do notice, but can this be helpful to particularly show that it takes less than 7 times the no. of digits of b?
 
  • #10
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,315
1,005
I figured that the inequality ##b(\frac{1}{2})^\frac{n}{2} < 1## then taking the log of both sides should be enough...?
It's probably enough for ##\displaystyle b(\frac{1}{2})^\frac{n}{2} < 2\ .\ ## Right.

Combine this with b < 10k .

So if ##\displaystyle 10^k (\frac{1}{2})^\frac{n}{2} < 2\ ,\ ## then ...
 
  • Like
Likes Terrell
  • #11
317
26
Combine this with b < 10k
##2\log_2(b)<n## then by letting ##b = 10^k## we get ##2k\log_2(10)<n##. Also ##2\log_2(b)=6.6438...## therefore it can be at most 7 times the number of digits of ##b##. Thank you Sammy!
 

Related Threads on Euclidean Algorithm terminates in at most 7x the digits of b

  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
3
Views
2K
Replies
2
Views
601
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
6
Views
333
Replies
3
Views
7K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
0
Views
2K
Top