# Euclidean algorithm: the number gets smaller with complexity log(k)

• Oct 31st 2013, 01:05 PM
huberscher
Euclidean algorithm: the number gets smaller with complexity log(k)
Hi there

Given the exercise

Let $1 \le d \in \mathbb{N} , k=f*d+h , h.

Firstly show that the variable h has (with respect to basis 2) less digits than k. Then conclude that the euclidean algorithm is (ends) in polynomial time in $log_2(k)$.

I don't find a meaningful beginning. I can write $k=k_{d_k} k_{d_k-1} ... k_1 k_0 \text{ while } k_i \in \{0,1\} \forall i$ as a representation of k in the dual System. Then

$k=k_{d_k} k_{d_k-1} ... k_1 k_0 = \underbrace{f_{d_f} ... f_0}_{=f} * \underbrace{d_{d_d} ... d_0}_{=d} + \underbrace{h_{d_h} ... h_0}_{=h}$

Ok that far. Now what is here the idea? I don't see a track honestly ...

Regards
• Oct 31st 2013, 01:14 PM
SlipEternal
Re: Euclidean algorithm: the number gets smaller with complexity log(k)
Edit:

Do you also have $0\le h < f$?
• Oct 31st 2013, 01:25 PM
huberscher
Re: Euclidean algorithm: the number gets smaller with complexity log(k)
Well it's not written on the exercise sheet but I think we can assume that all those numbers are non-negative integers...
• Oct 31st 2013, 02:20 PM
SlipEternal
Re: Euclidean algorithm: the number gets smaller with complexity log(k)
You have $h < f = \dfrac{k-h}{d}$. So, $h(d+1) < k$. This implies that $h < \dfrac{k}{d+1} \le \dfrac{k}{1+1} = \dfrac{k}{2}$. If $k$ has $n$ digits, then $k < 2^n$. So, since $h < \dfrac{k}{2}$, it must be that $h < \dfrac{k}{2} < 2^{n-1}$, implying $h$ has at most $n-1$ digits.