Matematik
Talteoretisk problem
25. august 2007 af
math-freak++ (Slettet)
Hvordan bestemmer jeg den øvre grænse af euklidske algoritme-skridt for 100-cifrede tal?
Svar #1
26. august 2007 af peter lind
Du finder a(i+1) som resten ved division af a(i-1) med ai. a(i+1) er således altid mindre end ai undtagen eventuel ved start. Hvis ai er mindre end det halve af a(i-1), bliver a(i+1) mindre end det halve af
a(i-1). Hvis ai = = ½a(i-1) bliver a(i+1) = 0. Hvis ai er større end det halve af a(-1) bliver a(i+1) = a(i-1) - ai, hvilket også er mindre end det halve af a(i-1). a(i+1) er altså højst det halve af a(i-1), hvis man undtager den første iteration.
a(i-1). Hvis ai = = ½a(i-1) bliver a(i+1) = 0. Hvis ai er større end det halve af a(-1) bliver a(i+1) = a(i-1) - ai, hvilket også er mindre end det halve af a(i-1). a(i+1) er altså højst det halve af a(i-1), hvis man undtager den første iteration.
Skriv et svar til: Talteoretisk problem
Du skal være logget ind, for at skrive et svar til dette spørgsmål. Klik her for at logge ind.
Har du ikke en bruger på Studieportalen.dk?
Klik her for at oprette en bruger.