/ Forside / Karriere / Uddannelse / Højere uddannelser / Nyhedsindlæg
Login
Glemt dit kodeord?
Brugernavn

Kodeord


Reklame
Top 10 brugere
Højere uddannelser
#NavnPoint
Nordsted1 1588
erling_l 1224
ans 1150
dova 895
gert_h 800
molokyle 661
berpox 610
creamygirl 610
3773 570
10  jomfruane 570
kørselstid på modulo vs. gcd
Fra : Kim Schulz


Dato : 26-06-02 13:16

hejsa
hvordan ser det ud med kørselstiden på modulo i forhold gcd?


--
Kim Schulz - Freelance Development | Lizzie Borden took an axe, And
www.schulz.dk - En nørds bekendelser | plunged it deep into the VAX;
www.linuxia.dk - hverdagens små hacks | Don't you envy people who Do

 
 
Kasper Dupont (04-07-2002)
Kommentar
Fra : Kasper Dupont


Dato : 04-07-02 12:26

Kim Schulz wrote:
>
> hejsa
> hvordan ser det ud med kørselstiden på modulo i forhold gcd?

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.

Hvordan modulo så implementeres effektivt er et andet spørgsmål.
For små tal er det typisk gjort i hardware, for store tal
bliver det mere spændende.

--
Kasper Dupont -- der bruger for meget tid på usenet.
For sending spam use mailto:razor-report@daimi.au.dk

N/A (04-07-2002)
Kommentar
Fra : N/A


Dato : 04-07-02 22:56



Kasper Dupont (04-07-2002)
Kommentar
Fra : Kasper Dupont


Dato : 04-07-02 22:56

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

Henning Makholm (05-07-2002)
Kommentar
Fra : Henning Makholm


Dato : 05-07-02 11:57

Scripsit Kasper Dupont <kasperd@daimi.au.dk>

> 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 andet tilfælde vil der blive trukket mindst b fra a,

Faktisk "netop b"

--
Henning Makholm "Jeg mener, at der eksisterer et hemmeligt
selskab med forgreninger i hele verden, som
arbejder i det skjulte for at udsprede det rygte at
der eksisterer en verdensomspændende sammensværgelse."

Kasper Dupont (05-07-2002)
Kommentar
Fra : Kasper Dupont


Dato : 05-07-02 18:27

Henning Makholm wrote:
>
> Scripsit Kasper Dupont <kasperd@daimi.au.dk>
>
> > 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 andet tilfælde vil der blive trukket mindst b fra a,
>
> Faktisk "netop b"

Nå ja, hvis man trak 2b fra ville resultatet blive negativt.

--
Kasper Dupont -- der bruger for meget tid på usenet.
For sending spam use mailto:razor-report@daimi.au.dk

Søg
Reklame
Statistik
Spørgsmål : 177552
Tips : 31968
Nyheder : 719565
Indlæg : 6408849
Brugere : 218887

Månedens bedste
Årets bedste
Sidste års bedste