CS Challenge 3, Arbitrary Precision

Grundlæggende aritmetik med heltal og brøker er børnelærdom, men er i virkeligheden mere subtilt, end man tror. Fx er det nok i praksis de færreste gymnasieelever, der kan foretage en lang division i hånden.

Denne Challenge omhandler ikke-negative heltal og brøker med arbitrær præcision.

Klassen HugeNat.java implementerer heltal som en simpel sekvens af cifre. Hvert objekt indeholder et felt low af typen int, der repræsenterer et enkelt ciffer, og et felt high af typen HugeNat selv, der indeholder de højere cifre. Fx vil tallet 1024 være repræsenteret på denne måde:

Der må ikke være foranstillede nuller. Klassen HugeNat implementere operationerne plus, minus, mul, div, mod og gcd (største fællesnævner). De fire første er metoder med sideeffekter, så man fx kan skrive regneudtrykket:

x = (x*7)/y-z
som:
x.mul(7).div(y).minus(z)
Hvis man ikke ønsker en sideeffekt kan man beregne fx:
x+y
som:
x.clone().plus(y)
Derimod fungerer mod og gcd som statiske funktioner.
Metoderne er implementeret med en simpel linæer form for rekursion, hvor man arbejder sig gennem listen med rekursive kald, der giver svaret for high-delen. Fx er metoden equals implementert som:
public boolean equals(HugeNat h) {
  if (high==null && h.high!=null) return false;
  if (h.high==null && high!=null) return false;
  if (high!=null && h.high!=null && !high.equals(h.high)) return false;
  return low==h.low;
} 
Tilsvarende kan kort addition (1 ciffer) skrives på denne måde:
public HugeNat plus(int i) { // single digit
  if (i<0 || i>9) throw new NumberFormatException("not a digit");
  int carry = (low+i)/10;
  if (carry==0) low = low+i;
  else {
    low = (low+i)-10;
    if (high!=null) high.plus(carry);
    else high = new HugeNat(carry);
  }
  return this;
}

Ved meget store tal kan man få problemer ned Stack Overflow i Java,, hvilket kan afhjælpes ved at køre Java som:
java -Xss4m
for at allokere fx 4MB til stakken.

Spørgsmål A

Det n'te Fibonacci tal defineres som Fib0=0, Fib1=1 og Fibn=Fibn-1+Fibn-2. Benyt HugeNat til at beregne Fib1024.

Spørgsmål B

Skriv klassen HugeNat færdig ved at implementere metoden:
public HugeNat div(HugeNat h) 
så den beregner lang division på heltal. Hint: metoden mod implementerer allerede lang modulus.
Bemærk, at main-metoden laver en udmærket test ved at beregne 100!/250, der er lig med 82890330549595738924128375352277498403022775854137923684377543671801902285904897746019649652421639883795821220526555136000000000000000000000000i (Overvej, hvorfor det giver et heltal).
Klassen HugeRat.java bruger HugeNat til at implementere ikke-negative rationelle tal. Repræsentationen overholder altid, at nævneren er forskellig fra 0, og at tæller og nævner har største fællesnævner 1.
Klassen HugeRat implementerer de sædvanlige regneoperationer på brøker. Kun mangler der metoden:
public String decimal()
der giver en pæn decimaludgave at brøken. Den skal udnytte, at ethvert rationelt tal kan skrives som i rækkefølge en hel del, et punktum, et præfiks, og en periode. Fx giver 1/700 jo:
0.00142857142857142857142857...
hvilket så mere præcist af decimal vil blive skrevet som:
0.00{142857}
hvor den hele del er 0, præfikset er 00 og perioden er 142857. Overvej, hiorfor rationelle tal altid kan skrives på denne måde. Per konvention udskriver man aldrig perioden {0}. Overvej, hvorfor fx perioden {9} aldrig kan opstå. Bemærk, at perioden for 1/n i værste fald kan have længde n-1, hvilket fx opstår for 1/7 og 1/113.

Spørgsmål C

Implementer metoden decimal. Et godt hint er, at både præfikset og perioden for d/n,, hvor d<n afsløres af sekvensen af rester ved division, når man beregner d divideret med n ved lang division. Fx er sekvensen af rester ved divisionen 1/70:
1, 10, 30, 20, 60, 40, 50, 10, 30, 20, 60, 40, 50, 10, ...
Overbevis dig selv om, at du har forstået dette. Hint: måske kan klassen Periodizer.java bruges til noget?
Klassen HugeRat har en main-metode, der udskriver følgende test:
1/4 = 0.25
22/7 = 3.{142857}
355/113 = 3.{1415929203539823008849557522123893805309734513274336283185840707964601769911504424778761061946902654867256637168}
1/700 = 0.00{142857}
1/2212394296770203368013 = 0.{0000000000000000000004519989955948923} 

BlueJ version: NatRatBlueJ.zip.
Du deltager i vores Challenge ved senest 11. oktober at sende en e-mail til mis@cs.au.dk med subject Challenge 3 og svaret på spørgsmål A (i plain text) og svarene på spørgsmål B og C i form af attachments med nye udgaver af klasserne HugeNat.java, HugeRat.java og eventuelle ekstra klasser.