© 1999-2003, Flemming Koch Jensen
Alle rettigheder forbeholdt
Store tal
rev: 10. august 99

"..."

- ...

 

Abstract:

Java har to klasser BigDecimal og BigInteger til immutable repræsentation af tal med mange cifre og dermed stor nøjagtighed. De to klasser gennemgåes, undtaget de dele af BigInteger der retter sig mod kryptering med RSA. Disse dele berøres kun overfladisk, men gennemgåes nærmere i kapitlet om RSA-kryptering.

Forudsætninger:

Kendskab til talsystemer; grundtal og notation.

 

 

Meget nøjagtige tal Med store tal mener vi ikke alene tal der er meget langt fra 0, men også tal med meget stor præcision. java.math indeholder, trods sit generelle navn, kun to klasser: BigDecimal og BigInteger. Disse klasser giver mulighed for at repræsentere tal med mange decimaler efter kommaet henholdsvis heltal med mange cifre.
Klasserne har en del fællestræk. Det skyldes bla. et fælles interface Comparable og superklassen Number, begge fra java.lang:

Figur 1:
Klassediagrammet for de to klasser i java.math

Fælles  superklasse med get-agtige metoder Interfacet Comparable bidrager som altid beskedent mht. interfacet, men den fælles superklasse Number indeholder en række get-agtige metoder der kan levere tallet som en af de primitive numeriske typer.
Ud over det fælles interface fra Comparable og Number har de to klasser også andet til fælles og vi vil i det følgende lade "Big..." stå som en fælles betegnelse for dem.

 

1. Repræsentation

Vi vil først se hvilke tal man mere præcist kan repræsentere med Big..., og vi vil se hvorledes værdierne fortolkes.

 

1.1 Repræsentation af BigInteger

Intern repræsentation er array af bytes Den interne repræsentation består af et array af bytes, der fortolkes binært som big-endian uden fortegn. Big-endian skal i denne forbindelse forstås som at indgang 0 har den mest betydende byte. Fortegnet opbevares i en integer variabel der indeholder signum-værdien, som er givet ved følgende funktion:

Figur 2:
Signum funktionen

Sign Number En meget simpel funktion, og signum står da også for: sign number.
Begge klasser har en metode, der returnerer tallets fortegn som signum:
int signum()
Get 2. komplement BigInteger har også en get-metode vedr. byte-arrayet. Man skal dog bemærke at det er byte-arrayet som 2. komplement der returneres, og dermed ikke den interne repræsentation:
byte[] toByteArray()
Immutable som String Som nævnt er Big... immutable, dvs. konstant. Derfor vil der aldrig ske nogen udvidelse af byte-arrayet, men det vil altid tilpasses i størrelse, det tal som det repræsenterer. Ligesom man ud fra Strings kan lave andre strings af varierende længde, kan man tilsvarende lave Big... med et varierende antal cifre, alt efter hvad resultatet bliver. Vi skal senere se hvilke regneoperationer vi kan anvende.

 

1.2 Repræsentation af BigDecimal

Interne repræsentation er BigInteger og scale Cifrene i en BigDecimal opbevares i en BigInteger. Det eneste der derfor er tilbage, er at placere et komma et sted i disse cifre. Scale angiver indirekte dette sted, idet scale er givet ved:
Scale antal cifre efter kommaet Her er klassenavnene sat i anførselstegn, da anvendelsen skal fortolkes. "BigInteger" er den interne repræsentation af cifrene i BigDecimal. Værdien "BigDecimal" skal fortolkes som denne heltalsværdi ganget med ti i minus scale. Mao. skal scale antal af disse cifre står efter kommaet.
Scale regnes som 32 bits uden fortegn; hvilket med 65535 betydende decimaler efter kommaet skulle være nok til de fleste anvendelser.
Hvis de cifre vi har i den interne BigInteger f.eks. er:
83649263
og scale er 3, skal tallet i BigDecimal fortolkes som:
83649.263
get-metoder BigDecimal har et par get-metoder; hvis man skulle være interesseret i at få scale henholdsvis BigInteger fra en BigDecimal:
int scale()
BigInteger unscaledValue()
Efter vi nu har set hvordan det forholder sig med de værdier der repræsenteres i en Big..., så lad os lave nogle instanser.

 

2. Instantiering

Fælles konstruktor Én af konstruktorerne er fælles for BigInteger og BigDecimal. Det er:
Big...( String value )
som fortolker den tekstuelle repræsentation som et tal.
F.eks.:

BigInteger i = new BigInteger( "9638596268473" );
BigDecimal d = new BigDecimal( "341.243451113" );

System.out.println( i );
System.out.println( d );

9638596268473
341.243451113

 

2.1 Instantiering af BigInteger

Andet grundtal BigInteger har også en variant af denne konstruktor, der som anden parameter tager et grundtal: radix, der anvendes i fortolkningen af den tekstuelle rerpæsentation. F.eks.:

BigInteger i = new BigInteger( "-10011000", 2 );

System.out.println( i );

-152

Set-konstruktor Der findes også en ren set-konstruktor, der tager signum-fortegnet og byte-arrayet som parameter:

byte[] b = { (byte) 0xF3, (byte) 0x7E };

BigInteger i = new BigInteger( -1, b );

System.out.println( i );

-62334

2. komplement Man kan også angive den binære 2. komplement repræsentation, og dermed undvære et signum-fortegn med følgende konstruktor; hvor arrayet igen fortolkes som big-endian:

byte[] b = { (byte) 0xF3, (byte) 0x7E };

BigInteger i = new BigInteger( b );

System.out.println( i );

-3202

BigInteger har yderligere to konstruktorer
BigInteger( int bitLength, Random rnd )
BigInteger( int bitLength, int c, Random rnd )
der retter sig mod kryptering.

 

2.2 Instantiering af BigDecimal

Set-konstruktor BigDecimal har også en set-konstruktor, der tager scale og en BigInteger som parameter:

BigInteger i = new BigInteger( "83649263" );
BigDecimal d = new BigDecimal( i, 3 );

System.out.println( d );

83649.263

Fra BigInteger Man kan også konvertere en BigInteger til en BigDecimal med:

BigInteger i = new BigInteger( "83649263" );
BigDecimal d = new BigDecimal( i );

System.out.println( d );
System.out.println( d.scale() );

83649263
0

Vi har her inkluderet et kald af scale, for at understrege at der reelt er tale om et heltal.
Fra double Den sidste konstruktor tager udgangspunkt i den primitiv numerisk type double:

BigDecimal d = new BigDecimal( 0.1 );

System.out.println( d );
System.out.println( d.scale() );

0.1000000000000000055511151231257827021181583404541015625
55

Unøjagtighed Resultatet er nok lidt overraskende. Problemet er at 0.1 er en aldeles nydelig værdi i ti-talssystemet, men ikke i det binære; hvor i doublen er repræsenteret (se evt. kapitlet om typer vedr. repræsentation af double)
Brug evt. "tal til tekst" kneb Man bør derfor være tilbageholdende med at anvende denne konstruktor; hvis man ønsker nøjagtig konvertering. Her kunne vi med et numerisk literale naturligvis blot udskrifte det med det tilsvarende tekst-literale. Hvis man derimod har en double i en variabel som man vil konvertere til BigDecimal kan man bruge det primitive "tal til tekst" kneb:

double deci = 0.1;
BigDecimal d = new BigDecimal( "" + deci );

System.out.println( d );
System.out.println( d.scale() );

0.1
1

 

3. De almindelige regnearter

Vi vil i første omgang vente med BigDecimals division, da den er speciel mht. afrunding.
Alle metoderne tager anden operand som parameter (den er selv første operand) og returnerer resultatet som en ny instans:
Big...        add( Big...     value )
Big...  substract( Big...     value )
Big...   multiply( Big...     value )
BigInteger divide( BigInteger value )
Ingen decimaler går tabt Man kan notere sig at BigDecimal indstiller den resulterende scale så ingen decimaler går tabt.

 

3.1 Afrunding

Division kan kræve afrunding

I forbindelse med division kan det være nødvendigt for BigDecimal at foretage en afrunding, da resultatet kan indeholde vilkårligt mange decimaler.

BigDecimal har to metoder til division

BigDecimal divide( BigDecimal value, int roundingMode )
BigDecimal divide( BigDecimal value, int scale, int roundingMode )
De tager begge det tal der skal divideres med, som første parameter, sammen med en angivelse hvordan der evt. skal afrundes.
Scale Den anden af dem giver yderligere mulighed for at angive den scale, og dermed nøjagtighed, man ønsker resultatet skal have. Default er samme scale som den BigDecimal der divideres.
Syv forskellige former for afrunding

Man kan selv vælge hvilken form for afrunding man ønsker i forbindelse med hvert divide-kald. Der er i alt otte former for afrunding man kan anvende. Disse er givet ved otte static konstanter i BigDecimal-klassen:

Navn Betydning Eksempler
ROUND_UP
Afrunder væk fra 0
 1.25[3] ->  1.26
 1.25[5] ->  1.26
 1.25[7] ->  1.26
-1.25[3] -> -1.26
-1.25[5] -> -1.26
-1.25[7] -> -1.26
ROUND_DOWN
Afrunder mod 0
 1.25[3] ->  1.25
 1.25[5] ->  1.25
 1.25[7] ->  1.25
-1.25[3] -> -1.25
-1.25[5] -> -1.25
-1.25[7] -> -1.25
ROUND_CEILING
Afrunder op til den mest positive værdi
 1.25[3] ->  1.26
 1.25[5] ->  1.26
 1.25[7] ->  1.26
-1.25[3] -> -1.25
-1.25[5] -> -1.25
-1.25[7] -> -1.25
ROUND_FLOOR
Afrunder til den mest negative værdi
 1.25[3] ->  1.25
 1.25[5] ->  1.25
 1.25[7] ->  1.25
-1.25[3] -> -1.26
-1.25[5] -> -1.26
-1.25[7] -> -1.26
ROUND_HALF_UP
Afrunder mod nærmest. Ved lige afstand rundes op
 1.25[3] ->  1.25
 1.25[5] ->  1.26
 1.25[7] ->  1.26
-1.25[3] -> -1.25
-1.25[5] -> -1.25
-1.25[7] -> -1.26
ROUND_HALF_DOWN
Afrunder mod nærmest. Ved lige afstand runder ned
 1.25[3] ->  1.25
 1.25[5] ->  1.25
 1.25[7] ->  1.26
-1.25[3] -> -1.25
-1.25[5] -> -1.26
-1.25[7] -> -1.26
ROUND_HALF_EVEN
Afrunder mod nærmest. Ved lige afstand rundes mod den der er lige (i modsætning til den ulige)
 1.25[3] ->  1.25
 1.25[5] ->  1.26
 1.25[7] ->  1.26
-1.25[3] -> -1.25
-1.25[5] -> -1.26
-1.25[7] -> -1.26
ROUND_UNNECESSARY
Anvendes når man med sikkerhed ved at afrunding ikke bliver nødvendigt, og man samtidig ikke ønsker at angive nogen afrundingsmetode.
   
Eksemplerne skal læses på den måde, at tallet i kantet parantes skal rundes væk, så scale bliver 2. Det ekstra ciffer, der skal rundes væk, er fremkommet som et resultat af divisionen, men kan ikke bevares pga. begrænsningen i scale.

 

3.2 Modulus

BigInteger har en række metoder der giver mulighed for at arbejde med rest ved division.

Først og fremmest er der de to metoder:

BigInteger       mod( BigInteger value )
BigInteger remainder( BigInteger value )
mod returnerer altid positiv værdi mod og remainder adskiller sig fra hinanden ved at mod altid returnerer et positivt tal.
F.eks.:

BigInteger negative = new BigInteger( "-12" );
BigInteger positive = new BigInteger(  "12" );
BigInteger divisor  = new BigInteger(   "5" );

BigInteger positiveMod = positive.mod( divisor );
BigInteger positiveRemainder = positive.remainder( divisor );

BigInteger negativeMod = negative.mod( divisor );
BigInteger negativeRemainder = negative.remainder( divisor );

System.out.println( positiveMod );
System.out.println( positiveRemainder ); 

System.out.println( negativeMod );
System.out.println( negativeRemainder );

2
2
3
-2

Ud over disse metoder findes der også to andre:
BigInteger modInverse( BigInteger value )
BigInteger modPow( BigInteger exponent, BigInteger value )
Disse metoder retter sig mod kryptering.

 

4. Andre matematiske metoder

Ud over de almindelige regnearter har de to klasser også en række andre matematiske metoder til fælles:
Big... abs()
Big... min( Big... value )
Big... max( Big... value )
Big... negate()
abs returnerer den absolutte værdi (fjerner et evt. negativt fortegn).
Ændre fortegn negate returner Big... med modsat fortegn.
BigInteger har yderligere to metoder:
Først er der
Opløfte i potens
BigInteger pow( int exponent )
som opløfter BigInteger i den anførte exponent. At denne metode ikke findes for BigDecimal er lidt overraskende.
Dernæst er der
BigInteger gcd( BigInteger value )
Største fælles divisor som finder den største fælles divisor for BigInteger og parameteren. Denne metode retter sig bla. mod kryptering.

 

5. Scalering af BigDecimal

Det er muligt at ændre scale på flere måder.
Først og fremmest er der de direkte set-metoder
Set-metoder til scale
BigDecimal setScale( int scale )
BigDecimal setScale( int scale, int roundingMode )
Den første version kaster en ArithmeticException hvis den anførte scale er mindre end den oprindelige og en afrunding derfor bliver nødvendig. Den svarer til kaldet:
setScale( scale, ROUND_UNNECESSARY )
Den anden version benyttes når afrunding er nødvendig.
Ud over disse set-metoder er der også to "flytte kommaet" metoder:
Flytter kommaet
BigDecimal movePointLeft( int n )
BigDecimal movePointRight( int n )
Der flytter kommaet n positioner i en af retningerne.

 

6. Binære operationer på BigInteger

Først vil vi lige bemærke en speciel udgave af toString, der gør BigInteger nemmere at studere i forbindelse med andre talsystemer.
Tekstuel repræsentation i andet talsystem
String toString( int radix )
Metoden returnerer en tekstuel repræsentation af BigIntegers værdi i det talsystem der svarer til det anførte grundtal.
En lang række metoder giver mulighed for at arbejde med en BigInteger binært.
Først og fremmest er der de almindelige bit-vis logiske operationer:
Bit-vis logiske operationer
BigInteger and( BigInteger value )
BigInteger  or( BigInteger value )
BigInteger xor( BigInteger value )
BigInteger not()

hvor parameteren som altid er anden operand.

F.eks.:

BigInteger i1 = new BigInteger( "10011011", 2 );
BigInteger i2 = new BigInteger( "00110101", 2 );
BigInteger res;

res = i1.and( i2 );
System.out.println( res.toString( 2 ) );

res = i1.or( i2 );
System.out.println( res.toString( 2 ) );

res = i1.xor( i2 );
System.out.println( res.toString( 2 ) );
res = i1.not();
System.out.println( res.toString( 2 ) );

10001
10111111
10101110
-10011100

not er lidt rodet

Måske lidt overraskende fungerer not lidt som en blanding, idet den ikke alene vender bit'ene, men efterfølgende konverere/fortolker det derved fremkomne som 2. komplement.

Til at arbejde med en vilkårlig bit findes flg. metoder:
"bit-vender"-metoderne
BigInteger clearBit( int n )
BigInteger   setBit( int n )
BigInteger  flipBit( int n )
boolean     testBit( int n )

hvor n er bit-positionen.

flipBit vender bit'en, mens testBit returnerer true hvis den pågældende bit er sat.

F.eks.:

BigInteger i = new BigInteger( "10011011", 2 );
BigInteger res;

res = i.clearBit( 1 );
System.out.println( res.toString( 2 ) );

res = i.setBit( 2 );
System.out.println( res.toString( 2 ) );

res = i.flipBit( 3 );
System.out.println( res.toString( 2 ) );

System.out.println( i.testBit( 4 ) );

10011001
10011111
10010011
true

Shift Shift til højre henholdsvis venstre udføres med flg. metoder:
BigInteger shiftRight( int n )
BigInteger shiftLeft( int n )
hvor n er antallet af gange der skal shiftes.

F.eks.:

BigInteger i = new BigInteger( "10011011", 2 );
BigInteger res;

res = i.shiftRight( 3 );
System.out.println( res.toString( 2 ) );

res = i.shiftLeft( 2 );
System.out.println( res.toString( 2 ) );

10011
1001101100

Der findes tre andre metoder af lidt speciel beskaffenhed:

                

int bitCount()
int bitLength()
int getLowestSetBit()

Flg. eksempel illustrerer deres funktionalitet:

BigInteger positive = new BigInteger(  "101110", 2 );
BigInteger negative = new BigInteger( "-101110", 2 );
          // 2. komplement af 101110 er 010010

System.out.println( positive.bitCount() );
System.out.println( negative.bitCount() );

System.out.println( positive.bitLength() );
System.out.println( negative.bitLength() );

System.out.println( positive.getLowestSetBit() );
System.out.println( negative.getLowestSetBit() );

4
4
6
6
1
1

bitCount returnerer antallet af bits der er forskellige fra fortegns-bit'en. Hvis tallet er positivt er det antallet af 1'er, modsat antallet af 0'er hvis tallet er negativt.

bitLength er antallet af bits i tallet.

getLowestSetBit returnerer positionen på den den bit med lavest position der er sat (dvs. 1).

 

Repetitionsspørgsmål

1 Hvad repræsenterer BigInteger?
2 Hvad repræsenterer BigDecimal?
3 Hvilke metoder er der i Number-superklassen?
4 Hvad er den interne repræsentation i BigInteger?
5 Hvad gør signum-funktionen?
6 Hvad er den interne repræsentation i BigDecimal?
7 Hvad er scale?
8 Hvilke problemer er der med at bruge den af BigDecimals konstruktorer der tager en double som parameter?
9 I hvilken situation kan det være nødvendigt med afrunding?
10 Hvilken afrunding skal man bruge for at få normal matematisk afrunding?
11 Hvad er forskellen på mod og remainder?
12 Hvordan kan man ændre scaleringen?
13 Hvordan kan man udskrive en BigInteger i et andet talsystem?

 

Opgaver

1

Lav en klasse BigComplex, til repræsentation af komplekse tal med stor nøjagtighed.

Vælg selv passende konstruktorer og metoder, så BigComplex kan fungere som et supplement til BigInteger og BigDecimal.

 

Svar på Repetitionsspørgsmål

1 Heltal med mange cifre.
2 Komma-tal med mange decimaler efter kommaet - med fuld nøjagtighed!
3 Der er seks get-agtige metoder, der returnerer hver af de seks primitive numeriske typer.
4 Et array af bytes til den binære repræsentation og en integer med signum-fortegnet.
5 Afbilder alle heltal over i -1, 0 og 1, alt efter fortegn.
6 En BigInteger og en integer der indeholder scale.
7 Scale er antallet af cifre i BigInteger der skal placeres efter kommaet.
8 double er en binære repræsentation af et reelt tal, og da BigDecimal kan repræsentere et reelt tal med meget større nøjagtighed vil unøjagtigheden i doubles repræsentation slå igennem når der laves en BigDecimal ud fra den.
9 I forbindelse med division.
10 ROUND_HALF_UP
11 mod returnerer altid en positiv værdi.
12 Et ved at bruge en af de direkte set-metoder, eller en af de metoder der flytter kommaet relativt i forhold til dets nuværende position.
13 Der findes en overloaded version af toString der tager et grundtal som parameter. Den returnerede tekststreng kan blot udskrives.