Kvadratrøtter

Kvadratrøtter#

Kvadratrtoten av \(16\) er \(4\), fordi \(4\cdot 4=16\). Da skriver vi \(\sqrt{16}=4\).

Definisjon: Kvadratrot

Kvadratroten av et positivt tall \(N\) er det positive tallet som ganget med seg selv gir \(N\). Vi skriver det tallet som \(\sqrt{N}\).

… men hva er \(\sqrt{15}\) eller \(\sqrt{2}\)?

Definisjonen sier oss ingenting om hvordan vi regner ut disse røttene. Den sier oss hva en kvadratrot er, men ikke hvordan man regner de ut.

For å svare på hvordan kan vi finne frem en algoritme som ble skrevet ned for \(2000\) år siden av en fyr som het Heron (eller Hero).

Herons algoritme

Herons algoritme for å regne ut \(\sqrt{N}\):

  1. Gjett et tall i nærheten av det du tror kvadratroten er.

  2. Regn ut neste forslag med formelen \(\text{neste}=\frac{1}{2}\left( \text{forrige} + \frac{N}{forrige}\right)\).

  3. Gjenta steg 2. til du er fornøyd.

Herons algoritme for hånd ✍️#

La oss regne ut en approksimasjon for \(\sqrt{2}\) med to iterasjoner av algoritmen.

\[\begin{split}\begin{align*} 1.&\quad 1 \\ 2.&\quad \frac{1}{2}\left( 1 + \frac{2}{1}\right)=\frac{3}{2}=1.5\\ 3.&\quad \frac{1}{2}\left( \frac{3}{2} + \frac{2}{\frac{3}{2}} \right)=\frac{1}{2}\left( \frac{3}{2} + 2\cdot \frac{2}{3} \right)=\frac{1}{2}\left( \frac{9}{6} + \frac{8}{6} \right)=\frac{17}{12}\approx 1.42 \end{align*}\end{split}\]

Oppgave

Regn ut approksimasjoner for kvadratrøttene med to iterasjoner av Herons algoritme.

  • \(\sqrt{3}\)

  • \(\sqrt{5}\)

  • \(\sqrt{15}\)

Sammenlikn svaret ditt med svaret fra en kalkulator.

Vi kan fortsette å regne så lenge vi ønsker og få en bedre og bedre approksimasjon, men det blir kanskje litt kjedelig. La oss overlate resten av regningen til datamaskinen, som klarer å regne tusenvis av steg på bare noen få millisekunder.

Men, før datamaskinen kan regne ut kvadratrøtter, må vi oversette algoritmen til et språk som datamaskinen forstår – vi må programmere.

Herons algoritme med Python 🐍#

Det er lett å finne kvadratrøtter ved å bruke sqrt()-funksjonen fra math-pakken.

from math import sqrt
print(sqrt(2))

1.4142135623730951

Effektivt og enkelt, men det lærer oss ingenting om algoritmene som ligger under. sqrt blir en black-box, en funksjon vi putter ting inn i og får ting ut fra, men uten å vite hva som egentlig skjer inne i boksen.

Prøv selv!

Prøv å implementere Herons algoritme i Python selv!

Enkel løkke#

La oss lage vårt eget program som kjører Herons algoritme noen ganger.

N = 2
rot = 1
for n in range(4):
	rot = 0.5*(rot + N/rot)
	print(rot)

1.5
1.4166666666666665
1.4142156862745097
1.4142135623746899

Vi ser at Heron’s algoritme fort blir ganske sikker på desimalene, men i stedet for å kjøre algoritmen fast \(4\) ganger, kan vi heller stoppe den når vi er fornøyd.

Dynamisk stopping#

Vi vet at algoritmen blir nærmere og nærmere den riktige verdien. Differansen mellom neste og forrige sier oss noe om hvor forskjellig den neste iterasjonen blir fra den forrige.

N = 2
forrige = 1
neste = 0.5*(forrige + N/forrige)
print(neste)
while abs(neste - forrige) > 0.000001:
	forrige = neste
	neste = 0.5*(forrige + N/forrige)
	print(neste)

1.5
1.4166666666666665
1.4142156862745097
1.4142135623746899
1.414213562373095

Flott! Nå gjenstår det bare å tilpasse while-løkken med en enda mindre verdi 1e-15, pakke alt inn i en funksjon, og bare skrive ut den siste verdien vi regner ut.

def sqrt(N):
	forrige = 1
	neste = 0.5*(forrige + N/forrige)
	while abs(neste - forrige) > 1e-15:
		forrige = neste
		neste = 0.5*(forrige + N/forrige)
	return neste

print(sqrt(2))

1.414213562373095

Nå har vi vår egen implementasjon av sqrt()-funksjonen. Rått! 🤓

Oppgaver#

Ta gjerne utgangspunkt i det siste eksempelet når du gjør disse oppgavene.

Oppgave 1 #️⃣

Utvid programmet til å skrive ut hvor mange iterasjoner algoritmen har regnet.

Oppgave 2 ⁉️

Programmet vårt reagerer litt rart på noen ting.

  • Hva skjer når man kjører programmet vårt med \(0\)?

  • Hva skjer når man kjører programmet vårt med et negativt tall?

Fiks programmet med if-setninger slik at:

  1. Kvadratroten av 0 blir nøyaktig lik 0.

  2. Programmet skriver ut Kan ikke ta kvadratroten av et negativt tall! når man skriver inn et negativt tall.

Oppgave 3 1️⃣

Undersøk hvor viktig den første gjetningen er ved å…

  1. … ta kvadratroten av et veldig stort tall

  2. … gjøre forskjellige første gjetninger

  3. … se hvor mange iterasjoner algoritmen har måtte regne for å komme frem til et svar

Hva tenker du er en god første gjetning? Kanskje \(\frac{N}{2}\), eller \(\frac{N}{10}\)? Eller kanskje det ikke har så mye å si?

Contents