Kvadratrøtter

Kvadratrøtter#

Hva er kvadratroten av \(16\)? Jo, \(4\), fordi \(4\cdot 4=16\). Da skriver vi \(\sqrt{16}=4\).

Definisjon: Kvadratrot

Kvadratroten av et 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.

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

Prøv selv!

Prøv å implementere Herons algoritme i Python selv!

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.

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