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
Expand |
---|
|
Code Block |
---|
| 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) |
---|
Widget Connector |
---|
url | https://www.youtube.com/watch?v=1VBnsEaz-lg |
---|
|
| Widget Connector |
---|
url | https://www.youtube.com/watch?v=lC3Jy8uVECM |
---|
|
| Widget Connector |
---|
url | https://www.youtube.com/watch?v=IE42ZNiVcMc |
---|
|
|
Introduksjon av problemet, og vanlig, enkel løsning. | Effektiv løsning. | Demonstrasjon av kjøretidsfordelen man kan få med denne teknikken. |
Løsningsforslag
Expand |
---|
title | Hvis du har prøvd selv, trykk her for å se svaret... |
---|
|
Code Block |
---|
| 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 |
|
Expand |
---|
title | Script som viser ytelsesfordelene ved preallokering |
---|
|
Expand |
---|
title | test_lag_lang_liste.m |
---|
| Code Block |
---|
title | 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-'); |
|
Expand |
---|
title | lag_lang_liste_utvid_liste.m |
---|
| Code Block |
---|
title | lag_lang_liste_utvid_liste.m |
---|
| function retur = lag_lang_liste_utvid_liste(n)
retur = [];
for i = 1:n
retur(i) = i;
end
end |
|
Expand |
---|
title | lag_lang_liste_gradvis_dobling.m |
---|
| Code Block |
---|
title | 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 |
|
Expand |
---|
title | lag_lang_liste_preallokering.m |
---|
| Code Block |
---|
title | 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 |
|
|