Milli en Mu hebben in de vakantie een eigen computer gekregen. "Maar wat heb je nou aan een computer?" is de eerste vraag die boven komt bij Milli. "Wel, die kun je dingen voor je laten doen," is het nuchtere antwoord van Phi. "Alleen moet je de computer dan precies uitleggen wat er moet gebeuren. Stel bijvoorbeeld dat je de getallen van $1$ tot en met $100$ wilt optellen. Dat is saai en …" Mu valt meteen in de rede, "Daar heb ik geen computer voor nodig, want het antwoord is natuurlijk $5050$. Dat wist Gauss al toen hij acht was." "Oké, oké," vervolgt Phi, "ik bedoelde vermenigvuldigen. Het resultaat heet honderd faculteit, geschreven als $100!$. Je kunt de berekening ervan in kleine stapjes opdelen: begin met $1$ en vermenigvuldig dit telkens met het volgende getal, tot je met $100$ vermenigvuldigd hebt." Phi tikt het volgende Python programma in:

En klikt vervolgens een paar keer om het programma uit te voeren. In een mum van tijd verschijnt een getal van $158$ cijfers op het scherm. (Op hoeveel nullen eindigt het?)

In Python staat  met $a \le b$ voor de rij van $b - a$ gehele getallen $i$ met $a \le i < b$. Het interval met $n$ gehele getallen vanaf $a$ kan geschreven worden als . En  rekent het product van een rij getallen uit.

Pi stelt voor om een iets moeilijker probleem op te lossen. Wat is, bij benadering, de wortel uit honderd faculteit? Wat preciezer gezegd, zoek een geheel getal $w \ge 0$ met $w^2 \le 100! < (w + 1)^2$. Je kunt natuurlijk beginnen met $w = 0$ en zolang $(w + 1)^2 \le 100!$, telkens $w$ met $1$ verhogen. Dit heet lineair zoeken. Het werkt, maar het gaat wel erg lang duren (voor de wortel uit $20!$ duurt het al enkele minuten). "Kan het niet efficiënter?" vraagt Pi. Milli en Mu zijn even uit het veld geslagen. Plots suggereert Milli: "Je kunt toch stapjes van $2$ nemen en op het einde eventueel één stapje terug doen? Dan gaat het twee keer zo snel." Waarop Mu meteen reageert met, "Dan kan ik het nog wel twee keer sneller, door stapjes van $4$ te nemen." Voordat het uit de hand loopt, grijpt Phi in: "Waarom dan niet meteen stapjes van $8$ of nog meer? En hoe zit het dan op het einde?" Daar moeten ze toch even over nadenken, want met stapjes van $1$ terug is natuurlijk niet handig. En als je met grotere stappen terug gaat, dan is dat mogelijk te veel en moet je weer vooruit. Het wordt zo wel erg ingewikkeld.

"Laten we even een stapje terug doen," stelt Phi voor, "en vooraan beginnen." Om de wortel uit $n$ te berekenen beginnen we met $w = 0$ en stapgrootte $s = 1$. Zolang $(w + s)^2 \le n$ is, verhogen we $w$ met $s$ als nieuwe benadering van de wortel (doen een stap van grootte $s$). Om te zorgen dat het niet te langzaam blijft gaan, verdubbelen we meteen de stapgrootte $s$. Deze herhaling eindigt met $w^2 \le n < (w + s)^2$. Als $s > 1$ is, dan zijn we er mogelijk te ver overheen gestapt en moeten we terug. Merk op dat $s$ een macht van $2$ is. We kunnen een half $s$ proberen en, afhankelijk van of dat te veel of te weinig is, weer vooruit gaan of juist verder terug gaan. En dat dan herhalen tot $s = 1$ is. In Python ziet dat er zo uit:

Dit is efficiënt genoeg om te gebruiken met $n = 100!$. Het gaat zelfs heel erg snel. Er blijkt nu maar $525$ keer een kwadratering gedaan te zijn. De techniek in dit programma heet binair zoeken. Eerst zoekt het programma met verdubbelen een interval $[w, w + s)$ waarbinnen de wortel ligt en vervolgens wordt het interval telkens gehalveerd totdat er nog maar één getal in zit.

Probeer nu zelf driehoeksgetallen te vinden die een kwadraat zijn. Dit zijn de getallen die je krijgt als je getallen van tot $1$ en met $n$ optelt. Voor $n = 100$ levert dat $5050$. Er is bewezen dat er oneindig veel kwadraten onder de driehoeksgetallen zijn. Doorloop daartoe de driehoeksgetallen vanaf $1$ en controleer telkens of het een kwadraat is. Dat laatste kun je efficiënt doen door de gehele wortel te trekken (zie hierboven) en dan te controleren of het kwadraat ervan gelijk is aan het driehoeksgetal. De Python code is beschikbaar op de website.

Binair zoeken komt vaker van pas, bijvoorbeeld om snel een naam in een gesorteerde lijst te zoeken. Maar ook om in een rij van getallen, waarvan het eerste getal groter is dan het laatste, twee getallen te vinden die in de rij naast elkaar staan en waarvan het linkse groter is dan het rechtse.

Probleem voor volgende keer

Schud een pakje van $52$ speelkaarten en leg vijftien kaarten open naast elkaar op tafel. Is het altijd mogelijk om de rij in tweeën te delen zodanig dat het aantal zwarte kaarten in het linkerdeel gelijk is aan het aantal rode kaarten in het rechterdeel? Het is toegestaan dat een deel leeg is. Hint: Bedenk een handig algoritme om zo’n tweedeling te maken.