Liczba kroków Euklidesa

0

Witam!
Mam tak kod:

typedef unsigned long long ULL;
ULL euklides(ULL a, ULL b)
{
    ULL c, licz = 1;
    while(a != b)
    {
        if(a > b)
           a = a - b;
        else
            b = b - a;
        licz++;
    }
    return licz;

    /*if(a == b)            **WERSJA REKURENCYJNA**
        return 1;
    if(a > b)
        return 1 + euklides(a-b, b);
    else
        return 1 + euklides(a, b-a);*/
} 

Potrzebuję wyznaczyć wartość zmiennej licz, tj. liczbę kroków w algorytmie. Da się do zrobić jakoś w sensowym czasie, tj. nie odejmując naiwnie a od b i b od a? moje a i b są do 10^18...

pozdrawiam
piternet

0

Algorytm Euklidesa to raczej jak tutaj na wiki. Algorytm dość dobrze się uwija w wyznaczaniu NWD dwóch liczb. Zobacz sobie na wiki, jest opis algorytmu, pseudokod, nawet implementacje w C++ i innych językach.

0
Mrowa napisał(a)

Algorytm Euklidesa to raczej jak tutaj na wiki. Algorytm dość dobrze się uwija w wyznaczaniu NWD dwóch liczb. Zobacz sobie na wiki, jest opis algorytmu, pseudokod, nawet implementacje w C++ i innych językach.

Eee, no tak, ale ja chcę obliczyć ilość iteracji przy 'naiwnym' euklidesie, tj. z odejmowaniem. Nie bardzo rozumiem o co ci chodzi.

0
ULL euclid(ULL a, ULL b){
	ULL c,licz=1; 
	if( 0==a ) return licz; // return b;
	while( 0!=b ) 
		if( a > b ) {
			//a=a-b;
			if(b==0) return licz; //return a;
			c=a%b; licz+=a/b;
			a=c;
		} else {
			//b=b-a
			if(a==0) return licz; //return b;
			c=b%a; licz+=b/a;
			b=c;
		}
	return licz;}  //return a;} 

1 użytkowników online, w tym zalogowanych: 0, gości: 1