\(\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?