Opgaven 3

(i) Op een computer en in een omgeving waarin gehele getallen in 32-bit two's complement notatie worden voorgesteld: Wat is het grootste, en wat het kleinste gehele getal? Welk geheel getal heeft geen tegengestelde?

(ii) Bereken sin(10^100) - de sinus van 10 tot de macht 100 - in twee decimalen.

(iii) Bij rood-blauw hackenbush is er een grond, en een graaf met rode en blauwe kanten, waarvan sommige knooppunten op de grond liggen (en de rest erboven). Er zijn twee spelers, Rood en Blauw, die om beurten een zet doen. Een zet bestaat uit het weghalen van een kant in de eigen kleur, benevens alles wat door het weghalen van die kant niet meer aan de grond vastzit. Wie niet kan zetten verliest.

Het is duidelijk dat blauwe kanten die aan de grond vastzitten Blauw helpen: als er zeven zulke kanten zijn, houdt hij het zeker nog zeven zetten uit. Blauwe kanten die hoog in de lucht zweven, en alleen via rode kanten aan de grond vastzitten zijn minder zeker: misschien verwijdert Rood die kanten en vallen de hoge blauwe kanten er af zonder dat Blauw er plezier van heeft gehad. Het is mogelijk om bij elk plaatje uit te rekenen hoeveel zetten voorsprong dat aan Blauw geeft (en dit aantal hoeft geen geheel getal te zijn). Op deze manier ontstaat een getalrepresentatie met plaatjes, en in sommige praktijksituaties is dit nuttig.

Nu de vragen. Elk van mijn plaatjes zal een veld met gekleurde rietstengels zijn (stengels die op de grond staan zonder vertakkingen). De achtereenvolgende kleuren worden met B en R aangegeven, zodat BBR,RBRR een veld met twee rietstengels voorstelt, de eerste van onder af blauw, blauw, rood, de tweede van onder af rood, blauw, rood, rood.

(iiia) Een veld heeft waarde 0 als degene die aan zet is verliest. Het lege veld heeft waarde 0. Laat zien dat ook het veld B,R en het veld BBRBR,RRBRB de waarde 0 hebben.

(iiib) De stengel B heeft waarde 1. De stengel RR heeft waarde -2. Laat zien dat de stengel BR de waarde 1/2 heeft door het veld BR,BR,R te bekijken.

(iiic) Laat zien dat de stengel BBRR de waarde 5/4 heeft, en de stengel BRB de waarde 3/4.

(iiid) Is er een algemene regel om de waarde van een rood-blauwe stengel te vinden?

Antwoorden

(i) Het grootste getal op een 32-bit computer met 2's complement aritmetiek is het binaire getal 01111111111111111111111111111111, d.w.z. 2147483647 oftewel 2^31 - 1. Het kleinste getal is 10000000000000000000000000000000 (binair), d.w.z. -2147483648 oftewel -2^31. Dit laatste getal is het enige getal dat geen tegengestelde heeft: 2147483648 heeft geen voorstelling. (Bij `unsigned' aritmetiek is het kleinste getal 0 met voorstelling 00000000000000000000000000000000, en het grootste 11111111111111111111111111111111 (binair), d.w.z. 4294967295 (2^32 - 1).)

(ii) Eenvoudig aan Mathematica vragen levert het foute antwoord:

In[1]:= N[Sin[10^100],2]
Out[1]= -0.38
In[2]:= N[Sin[10^100],16]
Out[2]= -0.3806377310050283
In[3]:= N[Sin[10^100],17]

$MaxExtraPrecision::meprec: 
   $MaxExtraPrecision = 50. reached while evaluating 
    Sin[1000000000000000000000000000000000<<50>>00000000000000000]. Increasing
     the value of $MaxExtraPrecision may help resolve the uncertainty.

Out[3]= 0.
In[4]:= $MaxExtraPrecision = 70;

$MaxExtraPrecision::meprec: 
   $MaxExtraPrecision = 70. reached while evaluating 
    Sin[1000000000000000000000000000000000<<50>>00000000000000000]. Increasing
     the value of $MaxExtraPrecision may help resolve the uncertainty.

Out[5]= 0.
In[6]:= $MaxExtraPrecision = 71;

$MaxExtraPrecision::meprec: 
   $MaxExtraPrecision = 71. reached while evaluating 
    Sin[1000000000000000000000000000000000<<50>>00000000000000000]. Increasing
     the value of $MaxExtraPrecision may help resolve the uncertainty.

Out[7]= -0.4
In[8]:= $MaxExtraPrecision = 75;
In[9]:= N[Sin[10^100],17]

$MaxExtraPrecision::meprec: 
   $MaxExtraPrecision = 75. reached while evaluating 
    Sin[1000000000000000000000000000000000<<50>>00000000000000000]. Increasing
     the value of $MaxExtraPrecision may help resolve the uncertainty.

Out[9]= -0.37238
In[10]:= $MaxExtraPrecision = 100;
In[11]:= N[Sin[10^100],17]
Out[11]= -0.3723761236612767
Waarom levert Mathematica eerst zonder aarzelen 16 decimalen, en ziet hij later, bij veel nauwkeuriger rekenen, amper kans vijf decimalen te produceren? En zijn bijna alle decimalen die in eerste instantie gegeven werden incorrect? Dat is omdat Mathematica in machineprecisie (op deze computer is dat: 16 decimalen) rekent, en niet bijhoudt hoe betrouwbaar de tussenresultaten zijn. Het antwoord kan dus best een precisie van 0 decimalen hebben, kortom, volstrekt waardeloos zijn. Als de gebruiker vraagt om een hogere dan de machineprecisie dan houdt Mathematica precies bij hoeveel decimalen goed zijn.

(iiia) Genoemde velden zijn symmetrisch, dwz van de vorm x + (-x). Wie er ook begint, de ander kan de spiegelbeeldzet doen en de stand in y + (-y) overvoeren. Kennelijk verliest de beginner, en is x + (-x) = 0.

(iiib), (iiic) zie (iiid).

(iiid) De regel voor de waarde van een stengel is als volgt: breek de stengel in twee stukken: een stuk van 1 kleur dat aan de grond vastzat en een stuk waarvan de eerste kant nog dezelfde kleur heeft en de tweede kant de andere kleur. (Dus: BBBBRRBRB wordt BBB+BRRBRB en RBR wordt 0+RBR, waarbij 0 de stengel ter lengte 0 voorstelt.) Het monochromatische stuk heeft een waarde gelijk aan het aantal kanten, positief voor B, negatief voor R. (Dus: BBB heeft waarde 3, RR heeft waarde -2, 0 heeft waarde 0.) Het andere stuk heeft een waarde verkregen door de opeenvolgende kanten gewichten 1, 1/2, 1/4, 1/8, ... te geven, positief voor B en negatief voor R. (Dus BRRBRB heeft waarde 1 - 1/2 - 1/4 + 1/8 - 1/16 + 1/32 = 11/32 en RBR heeft waarde -1 + 1/2 -1/4 = -3/4.) De totale waarde is de som van die twee. (Dus BBBBRRBRB heeft waarde 3+11/32 en RBR heeft waarde 0-3/4.)

Dat is de regel. Maar waarom is dat nu zo? Stel we hebben een stand die volgens deze regel in totaal waarde 0 heeft. We moeten bewijzen dat de beginner verliest. Blauw is beleefd, en laat Rood beginnen. Als Rood een kant pakt, wordt de waarde (berekend volgens bovenstaande regel) groter (namelijk minstens 2^(-h) waarbij h de hoogte is van de stengel waarin Rood iets pakte, of h=0 als Rood uit een monochromatische stengel pakte). Nu zoekt Blauw de allerhoogste stengel die niet monochromatisch is, en pakt de hoogste blauwe kant daarin. Nu wordt de waarde 2^(-H) kleiner, als H de hoogte van deze laatste stengel is. Maar H is minstens zo groot als h, want een som van breuken met noemers 2^iets met precies 1 term met grootste noemer kan nooit nul zijn. Dus Blauw kan de waarde niet-negatief houden en wint.