[Algorytmy] Ile czasu pochłania rozszerzony algorytm euklidesa?

[matemix]

Chcę rozwiązywać równania typu:

\(\displaystyle{ a \cdot 2^{x+y} - b \cdot g^{y} = 1}\)

rozszerzonym algorytmem euklidesa dla losowych \(\displaystyle{ x+y=128}\), będących liczbami naturalnymi z zerem. Czy ktoś ma pomysł jak ustalić ile to może średnio zająć komputerowi dla całkowitego \(\displaystyle{ g}\) wynoszącego powiedzmy \(\displaystyle{ 5}\)? Dodam tylko, że nie umiem programować, więc nie jestem w stanie napisać sobie żadnych testów (dopiero rozważam zlecenie napisania komuś programu).

Tutaj jest przykładowa implementacja rozszerzonego algorytmu euklidesa:

Kod: Zaznacz cały

http://www.algorytm.edu.pl/rozszerzony-algorytm-euklidesa.html

Niestety nie wiem jak policzyć średni przypadek algorytmu. A kombinacji \(\displaystyle{ x+y}\) równych 128 jest 128:

\(\displaystyle{ 0+128=128}\)
\(\displaystyle{ 1+127=128}\)
\(\displaystyle{ 2+126=128}\)
...
\(\displaystyle{ 64+64=128}\)
\(\displaystyle{ 65+63=128}\)
...
\(\displaystyle{ 128+0=128}\)

Więc może ktoś z Was byłby w stanie po prostu policzyć je wszystkie i sprawdzić średni czas?

[Gosda]

Liczba kroków do wykonania w algorytmie Euklidesa to co najwyżej pięciokrotność liczby cyfr w zapisie dziesiętnym mniejszej z liczb. Lame pokazał w 1844, że najmniejszą parą liczb, która wymaga \(\displaystyle{ n}\) kroków, jest para kolejnych wyrazów w ciągu Fibonacciego: \(\displaystyle{ F_{n+1}, F_{n+2}}\).

[matemix]

Ok, to dużo wnosi. Jeśli chodzi o tę liczbę kroków jako pięciokrotność, to, gdzie znaleźć to twierdzenie, ma ono jakaś nazwę?

I czy mogę przenieść to w prosty sposób na rozszerzony algorytm euklidesa, czyli przyjąć, że, jeśli mam równanie:

\(\displaystyle{ a \cdot 2^{x+y} - b \cdot g^{y} = 1}\)

gdzie \(\displaystyle{ a}\) i \(\displaystyle{ b}\) są niewiadomymi, a \(\displaystyle{ x}\), \(\displaystyle{ y}\), \(\displaystyle{ g}\), będą dane z góry, to liczba kroków będzie nie większa niż pięciokrotność liczb w zapisie dziesiętnym \(\displaystyle{ g^{y} }\) lub \(\displaystyle{ 2^{x+y} }\)?

[Dudenzz]

Wpisz w przeglądarce hasło "python online", otwórz pierwszy lepszy interpreter i pobaw się tym kodem:

Kod: Zaznacz cały

import numpy as np

g = 5
sumaxy = 512
liczba_losowan = 1000

def f1(x,y):
    return 2 ** (x+y)

def f2(x,y):
    return g ** (y)

def euklides(z1,z2,a,b,iteracje):
    if z2 != 0:
        iteracje += 1
        (a,b,iteracje) = euklides(z2,z1%z2,a,b,iteracje)
        pom = b
        b = a - int(z1/z2)*b
        a = pom
        return (a,b,iteracje)
    else:
        return (a,b,iteracje)


for _ in range(liczba_losowan):
    x = np.random.randint(0,sumaxy+1)
    y = sumaxy - x
    [z1,z2] = [f1(x,y),f2(x,y)]
    (a,b,iteracje) = euklides(z1,z2,1,0,0)
    if z1*a+z2*b == 1:
        print('2^(%d+%d) i %d^%d są względnie pierwsze' %(x,y,g,y))
        print('\twspółczynniki równania:\n\t\ta\t%d\n\t\tb\t%d' % (a,b))
        print('\tliczba iteracji = %d' % iteracje)
    else:
        print('2^(%d+%d) i %d^%d NIE są względnie pierwsze' %(x,y,g,y))