Sommige vierkantswortels zoals $$\sqrt{25}$$ of $$\sqrt{81}$$ kennen we van buiten, maar hoe berekenen we bijvoorbeeld $$\sqrt{17}$$? Vandaag de dag wordt doorgaans een rekenmachine of een computer gebruikt om de vierkantswortel van een getal $$s$$ te berekenen, maar hoe berekende men $$\sqrt{s}$$ in de tijd dat er nog geen rekenmachines of computers bestonden?

De methode van Heron is wellicht het oudste algoritme voor de berekening van $$\sqrt{s}$$. Ze werd vernoemd naar de Griekse wiskundige Heron van Alexandrië¹ die ruim 2000 jaar geleden de eerste expliciete beschrijving gaf van een methode voor het berekenen van de vierkantswortel van een willekeurig getal. Deze methode is ook gekend als de Babylonische methode — een verwijzing naar de Babyloniërs die ons de oudste gekende wiskundeteksten² achterlieten.

De Babylonische methode werkt op de volgende manier. Stel dat we de vierkantswortel willen berekenen van een strikt positief getal $$s \in \mathbb{R}$$. We starten met een initiële schatting van $$\sqrt{s}$$, en noemen die $$x_0$$. Daarna bereken we in elke stap een meer nauwkeurige benadering van de vierkantswortel op basis van de volgende formule: \[ x_{n+1} = \frac{1}{2} \left( x_n + \frac{s}{x_n} \right) \] Laten we dit algoritme bijvoorbeeld eens toepassen voor de berekening van $$\sqrt{17}$$. We kiezen $$x_0 = 6$$ als een initiële schatting voor $$\sqrt{17}$$. In een volgende stap bekomen we de volgende meer nauwkeurige benadering van de vierkantswortel: \[ x_1 = \frac{1}{2} \left( 6 + \frac{17}{6} \right) = 4.416666666666667 \] Daarna herhalen we de procedure om een nog nauwkeuriger benadering te bekomen: \[ x_2 = \frac{1}{2} \left( x_1 + \frac{17}{x_1} \right) = 4.1328616352201255 \] Op dezelfde manier blijven we de nauwkeurigheid van de benadering verder verbeteren: \[\begin{align} x_3 & = 4.12311714060797 \\ x_4 & = 4.12310562563374 \\ x_5 & = 4.123105625617661 \\ x_6 & = 4.123105625617661 \end{align}\] De Babylonische methode resulteert dus in een rij van getallen die zal convergeren naar $$\sqrt{17}$$. We controleren dit resultaat met math.sqrt uit de math module:

>>> import math
>>> math.sqrt(17)
4.123105625617661

We beschouwen de benadering $$x_k$$ uit stap $$k$$ als voldoende nauwkeurig als \[\frac{|x_k - x_{k-1}|}{x_k} \le 10^{-15}\] Het is dan niet langer zinvol om een betere benadering te berekenen en we mogen de procedure daar stoppen.

Invoer

De eerste regel van de invoer bevat een getal $$s \in \mathbb{R}$$. De tweede regel van de invoer bevat een initiële benadering $$x_0 \in \mathbb{R}$$ van $$\sqrt{s}$$.

Uitvoer

De Babylonische methode werkt alleen maar indien zowel $$s$$ als $$x_0$$ strikt positieve getallen zijn. Indien dit niet het geval is, dan moet de boodschap ongeldige invoer uitgeschreven worden. Als de invoer wel geldig is, dan moet de Babylonische methode toegepast worden om opeenvolgende benadering van $$\sqrt{s}$$ te bepalen. Voor elke stap moet het de index van $$x_i\ (i = 0, 1, 2, \ldots)$$ uitgeschreven worden, gevolgd door een dubbelpunt, een spatie en de benadering $$x_i$$. De methode stopt bij de eerste stap $$k$$ waarvoor geldt dat \[\frac{|x_k - x_{k-1}|}{x_k} \le 10^{-15}\] met $$x_k$$ de benadering die bekomen wordt in stap $$k$$ en $$x_{k-1}$$ de benadering die bekomen werd in de stap $$k-1$$.

Voorbeeld

Invoer:

17
6

Uitvoer:

0: 6.0
1: 4.416666666666667
2: 4.1328616352201255
3: 4.12311714060797
4: 4.12310562563374
5: 4.123105625617661
6: 4.123105625617661

Voorbeeld

Invoer:

2
0

Uitvoer:

ongeldige invoer