• Created by Unknown User (benjambj), last modified on 16.09.2016

I en tidligere oppgave lagde du en funksjon som estimerte hva kvadratroten av et tall var, ved å bruke iterasjoner av Newtons metode. Du har nå lyst til å analysere hvordan estimatene utvikler seg. I stedet for å skrive ut estimatene, har du lyst til å returnere dem i en vektor. Oppdater funksjonen til å fungere slik i stedet.

Utdelt kode

kvadratrot.m
function retur = kvadratrot(tall)
    x = 1;
    er_over_feilgrense = true;
    i = 1;
    while er_over_feilgrense
       ny_x = x + (tall - x^2)/(2*x);
       fprintf('Iterasjon #%d: x_%d = %.10f, x_%d = %.10f\n', i, i-1, x, i, ny_x);
       relativ_endring = abs(ny_x - x)/x;
       er_over_feilgrense = relativ_endring >= 1e-9;
       x = ny_x;
       i = i + 1;
    end
    retur = x;
end 

Videoforklaring (15:46)

Del 1 (4:00)Del 2 (9:12)Del 3 (2:34)
Introduksjon av problemet, og vanlig, enkel løsning.Effektiv løsning.Demonstrasjon av kjøretidsfordelen man kan få med denne teknikken.

Løsningsforslag

kvadratrot.m
function retur = kvadratrot(tall)
    x = 1;
    er_over_feilgrense = true;
    i = 1;
    N = 4;
    retur = zeros(1, N);
    retur(1) = x;
    while er_over_feilgrense
       ny_x = x + (tall - x^2)/(2*x);
       relativ_endring = abs(ny_x - x)/x;
       er_over_feilgrense = relativ_endring >= 1e-9;
       x = ny_x;
       i = i + 1;
       if i > N
           N = 2*N;
           retur(N) = 0;
       end
       retur(i) = x;
    end
    retur = retur(1:i);
end 
test_lag_lang_liste.m
teststorrelser = [10:10:100, 200:100:1000, 1000:1000:10000, 10000:10000:100000];
reps = 20;
res_gradvis_dobling = zeros(reps, length(teststorrelser));
res_utvid_liste = zeros(reps, length(teststorrelser));
res_preallokering = zeros(reps, length(teststorrelser));
for i = 1:length(teststorrelser)
    n = teststorrelser(i);
    for j = 1:reps
        fprintf('#%d - lag_lang_liste_gradvis_dobling(%d)\n', j, n);
        tic
        lag_lang_liste_gradvis_dobling(n);
        res_gradvis_dobling(j,i) = toc;
    end
    for j = 1:reps
        fprintf('#%d - lag_lang_liste_utvid_liste(%d)\n', j, n);
        tic
        lag_lang_liste_utvid_liste(n);
        res_utvid_liste(j,i) = toc;
    end 
    for j = 1:reps
        fprintf('#%d - lag_lang_liste_preallokering(%d)\n', j, n);
        tic
        lag_lang_liste_preallokering(n);
        res_preallokering(j,i) = toc;
    end 
end
fprintf('%15s %25s %25s %25s\n', 'Listestørrelse', 'Gradvis dobling [ms]', 'Utvid liste [ms]', 'Preallokering [ms]');
fprintf('%15d %25.3f %25.3f %25.3f\n', [teststorrelser; 1000*[mean(res_gradvis_dobling);  mean(res_utvid_liste); mean(res_preallokering)]]);
plot(teststorrelser, mean(res_gradvis_dobling), 'g-', teststorrelser, mean(res_utvid_liste), 'm-', teststorrelser, mean(res_preallokering), 'b-');
lag_lang_liste_utvid_liste.m
function retur = lag_lang_liste_utvid_liste(n)
    retur = [];
    for i = 1:n
        retur(i) = i;
    end
end 
lag_lang_liste_gradvis_dobling.m
function retur = lag_lang_liste_gradvis_dobling(n)
    N = 20;
    retur = zeros(1, N);
    for i = 1:n
        if i > N
            N = 2*N;
            retur(N) = 0;
        end
        retur(i) = i;
    end
    retur = retur(1:n);
end 
lag_lang_liste_preallokering.m
function retur = lag_lang_liste_preallokering(n)
    retur = zeros(1, n);
    for i = 1:n
        retur(i) = i;
    end
end 
  • No labels