Ile czasu zajmie komputerowi rozszerzony algorytm euklidesa?

Article View: pl.comp.programming

Article #216594

Back to pl.comp.programming Previous Next

#216594

From: osobliwy nick
Date: Fri, 06 Dec 2019 22:25

23 lines
2112 bytes

Chcę rozwiązywać równania typu:

a*2^(x+y)+b*g^y = 1

rozszerzonym algorytmem euklidesa dla losowych 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 "g" wynoszącego powiedzmy 
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:

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

Niestety nie wiem jak policzyć średni przypadek algorytmu. A kombinacji x+y równych 128 jest 128:

0+128=128
1+127=128
2+126=128
...
64+64=128
65+65=128
...
128+0=128

Więc do policzenia byłoby 128 przypadków użycia tego rozszerzonego algorytmu euklidesa. Chyba, że można to oszacować jak szybciej?

Technical Details

Message-ID: <ed31de14-90d3-405e-96e3-a82fcc32b9cc@googlegroups.com>

Path:

mbox-mo1.pugleaf.net!news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed.pionier.net.pl!feeder.erje.net!2.eu.feeder.erje.net!proxad.net!feeder1-2.proxad.net!209.85.160.216.MISMATCH!g89no1086467qtd.0!news-out.google.com!w29ni316qtc.0!nntp.google.com!g89no1086456qtd.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail

Show Full Headers

Complete Article Headers

X-Received: by 2002:a05:620a:12c4:: with SMTP id e4mr9809813qkl.359.1575671155872;        Fri, 06 Dec 2019 14:25:55 -0800 (PST)
X-Received: by 2002:a05:620a:136e:: with SMTP id d14mr15649808qkl.137.1575671155666; Fri, 06 Dec 2019 14:25:55 -0800 (PST)
Path: mbox-mo1.pugleaf.net!news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed.pionier.net.pl!feeder.erje.net!2.eu.feeder.erje.net!proxad.net!feeder1-2.proxad.net!209.85.160.216.MISMATCH!g89no1086467qtd.0!news-out.google.com!w29ni316qtc.0!nntp.google.com!g89no1086456qtd.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail
Newsgroups: pl.comp.programming
Date: Fri, 6 Dec 2019 14:25:55 -0800 (PST)
Complaints-To: groups-abuse@google.com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=185.186.156.102; posting-account=5sNFBgoAAAAxlae8lv99mPyGsDs6ynwB
NNTP-Posting-Host: 185.186.156.102
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <ed31de14-90d3-405e-96e3-a82fcc32b9cc@googlegroups.com>
Subject: Ile czasu zajmie komputerowi rozszerzony algorytm euklidesa?
From: osobliwy nick <osobliwy.nick@gmail.com>
Injection-Date: Fri, 06 Dec 2019 22:25:55 +0000
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit