Henning Makholm wrote:
>
> Scripsit Kasper Dupont <kasperd@daimi.au.dk>
>
> > Hvad tænker du helt præcist på? Den eneste gcd algoritme, jeg
> > kender gør brug af modulo beregninger en del gange. Jeg tror
> > nok antal kald af modulo i værste fald vil være logaritmisk,
> > men jeg kan ikke bevise det på stående fod.
>
> logn er nedre grænse: gcd(fib(i),fib(i+1)) foretager i skridt.
Det lyder rimeligt nok.
>
> logn er øvre grænse: hvis vi formulerer algoritmen som
>
> hvis a > b så ombyt a og b
> gentag følgende:
> # invariant 0 <= a <= b
> hvis a = 0 så returner b
> b <- b mod a
> hvis b = 0 så returner a
> a <- a mod b
>
> kan det let ses at hver omgang i løkken mindst halverer a.
Ja, det kan let ses, hvis man tænker sig om:
Efter b <- b mod a ved vi i hvert fald: b<a.
Vi kan nu betragte to tilfælde: b<=a/2 og b>a/2
I første tilfælde vil a blive mindre end b og
dermed blive mindst halveret.
I andet tilfælde vil der blive trukket mindst b
fra a, når der trækkes mindst a/2 fra a bliver
det mindst halveret.
--
Kasper Dupont -- der bruger for meget tid på usenet.
For sending spam use mailto:razor-report@daimi.au.dk