armo
Dołączył: 14 Paź 2010
Posty: 40
Przeczytał: 0 tematów
Pomógł: 1 raz
Ostrzeżeń: 0/5
|
 Wysłany: Pią 18:04, 03 Cze 2011 Temat postu: |
|
|
Zadanie: opracować bibliotekę 4 podstawowych działań +-*/ dla długich liczb wymiernych
| Kod: |
package zpziui0arytmetykabigrational;
import java.math.BigInteger;
import java.util.logging.Level;
import java.util.logging.Logger;
/**
* Klasa ma realizować cztery proste działania arytmetyczne na wielkic liczbac
* wymiernych. Klasa wzorowana jest na niektórych funkcjach klasy BigInteger. <br/>
* W kodzie zawarte jest kilka algorytmów mnożenia dużych liczb:
* <ul>
* <li>{@link #bigIntegerMultiply(BigRational)} - Najprostsza wykorzystuje działania klasy BigIneger</li>
* <li>{@link #myMultiply(BigRational)} - Samodzielna operująca na pojedyńczych cyfrach</li>
* <li>{@link #myMultipyBetter(BigRational)} - poprawiona funkcja, która dokonuje operacji mnożenia z podziałem na 9-cyfrowe bloki (iloczyn dwch bloków mieści się w zmiennej typu long</li>
* <li>{@link #myMultipyBest(BigRational)} - wykorzystujący rekurencyjnie Algorytm Karatsuby i poprzednią funkcję w prostszych przypadkach </li>
* </ul>
* podstawowa funkcja mnożenia multiply wywołuje ostatnią z wymienionych funkcji. <br/>Inne podstawowe działania realizowane są za pośrednictwem klasy BigInteger.
* @author s370650 Artur Mańko
*/
public class BigRational {
/**
* funkcja główna słuzyła mi do testowania działania biblioteki.<BR>
* Bazuje na kodzie ze strony
* http://sourceware.org/ml/mauve-patches/2004/msg00055.html
* Podmieniłem tylko BigInteger na swoja klasę BigRational
* oraz zdefiniowałem własną obsługę wyniku.
* @param args the command line arguments
*/
public static void main(String[] args) {
try {
// TODO code application logic here
// some really simple cases
BigRational p1 = new BigRational("1");
BigRational p2 = new BigRational("2");
BigRational m1 = new BigRational("-1");
BigRational m2 = new BigRational("-2");
sprawdz(p1.multiply(p2).equals(p2));
sprawdz(p1.multiply(m2).equals(m2));
sprawdz(m1.multiply(p2).equals(m2));
sprawdz(m1.multiply(m2).equals(p2));
// some bigger numbers
BigRational bp1 = new BigRational("12345678901234567890123456789012345678901234567890");
BigRational bp2 = new BigRational("987654321098765432198765");
BigRational bm1 = new BigRational("-12345678901234567890123456789012345678901234567890");
BigRational bm2 = new BigRational("-987654321098765432198765");
BigRational resultp = new BigRational("12193263113702179523715891618930089161893008916189178958987793067366655850");
BigRational resultm = new BigRational("-12193263113702179523715891618930089161893008916189178958987793067366655850");
sprawdz(bp1.multiply(bp2).equals(resultp));
sprawdz(bp1.multiply(bm2).equals(resultm));
sprawdz(bm1.multiply(bp2).equals(resultm));
sprawdz(bm1.multiply(bm2).equals(resultp));
// check null argument
boolean pass = false;
try {
p1.multiply(null);
} catch (NullPointerException e) {
pass = true;
}
sprawdz(pass);
} catch (Exception ex) {
Logger.getLogger(BigRational.class.getName()).log(Level.SEVERE, null, ex);
}
}
static void sprawdz(boolean prawidlowy) throws Exception{
if(!prawidlowy)
throw new Exception("Sprawdzanie wyniku: wynik nieprawidłowy!");
else
loguj("OK");
}
BigInteger numerator;
BigInteger denominator;
/**
* Stała dla wartości jeden.
*/
public static BigRational ONE = new BigRational(BigInteger.ONE);
/**
* Stała dla wartości zero.
*/
public static BigRational ZERO = new BigRational(BigInteger.ZERO);
/**
* Buduje liczbe wymierną na podstawie łańcucha teksotwego. Łańcuch może
* mieć postać długij liczby całkowitej (interpretowanej przez
* BigInteger(String)), albo dwoch takic liczb rodzielonych ukośnikiem.
* Łańcuch nie powinien zawierać innych znaków w tym spacji przed liczbą,
* po liczbie ani w okolicahc ukośnika.
* @param val Łańcuch opisujący liczbę wymierną
*/
public BigRational(String val){
if(val.contains("/")){
numerator = new BigInteger(val.substring(1,val.indexOf("/")));
denominator = new BigInteger(val.substring(val.indexOf("/")+1,val.length()));
} else {
numerator = new BigInteger(val);
denominator = BigInteger.ONE;
}
}
/**
* Generuje wymierną na podstawie osobnych dzielnej i dzielnika.
* @param numerator - dzielna
* @param denominator - dzielnik
*/
public BigRational(BigInteger numerator, BigInteger denominator){
this.numerator = numerator;
this.denominator = denominator ;
}
/**
* Generuje wymierną na podstawie dzielnej z założeniem, że dzielnik ma
* wartośc jeden.
* @param numerator dzielna
*/
public BigRational(BigInteger numerator){
this.numerator = numerator;
this.denominator = BigInteger.ONE;
}
/**
* Dodawanie zbudowane na funkcjach BigInteger
* @param val wartośc do dodania
* @return nowy obiekt o wartości sumy
*/
public BigRational add(BigRational val){
return new BigRational(
// numerator * val.denominator + denominator * val.numerator
numerator.multiply(val.denominator).add(denominator.multiply(val.numerator)),
// denominator * val.denominator
denominator.multiply(val.denominator));
}
/**
* Odejmowanie zbudowane na funkcjach BigInteger
* @param val wartośc do odjęcia
* @return nowy obiekt o wartości różnicy
*/
public BigRational subtract(BigRational val){
return new BigRational(
// numerator * val.denominator - denominator * val.numerator
numerator.multiply(val.denominator).subtract(denominator.multiply(val.numerator)),
// denominator * val.denominator
denominator.multiply(val.denominator));
}
/**
* Funkcja wywołująca którys z algorytmów mnożenia.
* @param val argument przez który zostanie wymnożony ten obiekt
* @return nowy obiekt będący wynikiem mnożenia
*/
public BigRational multiply(BigRational val){
//return bigIntegerMultiply(val); // bazująca na działaniach BigInteger
//return myMultiply(val); // własna z zajęć
// return myMultipyBetter(val); // myMultiply ulepszona o grupowanie liczb w połowę long-ów
return myMultipyBest(val); // myMultipyBetter ulepszona o Karatzubę
}
/**
* największa long ma 19 cyfr<BR>
* mnożenie dwóch liczb da 18cyfrową liczbę i nawet dodana do innej
* 18-cyfrowej da co najwyżej 19-cyfrową<BR>
* grunt by normalizować takie grupy od razu po dodaniu
*/
private static final int MULTI_CIPHER = 9 ;
/**
* dzielnik dla MULTI_CIPHER
*/
private static final long MAX_M_CIPHER = 1000000000l;
/**
* Format drukowania liczb wielocyfrowych z poprzedzającymi zerami
*/
private static final String FORMAT_M_CIPHER = "%0"+MULTI_CIPHER+"d";
/**
* Ulepszona myMultipyBetter: dodany algorytm Karatsuby
* @param val argument przez który zostanie wymnożony ten obiekt
* @return nowy obiekt będący wynikiem mnożenia
*/
public BigRational myMultipyBest(BigRational val){
//loguj("myMultipyBest ( " + this + " , " + val + " ) START");
String[][] factors = new String[2][2];
factors[0][0]=numerator.toString();
factors[1][0]=denominator.toString();
factors[0][1]=val.numerator.toString();
factors[1][1]=val.denominator.toString();
// osobne mnożenie dzielnej i dzielnika
for(int i=0; i<2; i++){
factors[i][0] = karatsuba(factors[i][0], factors[i][1]);
}
//loguj("myMultipyBest ( " + this + " , " + val + " ) = " + new BigRational( new BigInteger(factors[0][0]), new BigInteger(factors[1][0]) ));
return new BigRational( new BigInteger(factors[0][0]), new BigInteger(factors[1][0]) );
}
private String karatsuba(String val1, String val2){
int[] lengths = new int[]{val1.length(),val2.length()};
// warunek stopu rekurencji
if( (lengths[0]>MULTI_CIPHER) && (lengths[1]>MULTI_CIPHER) ){
int lmax = Math.max(lengths[0], lengths[1]);
int lmin = Math.min(lengths[0], lengths[1]);
if( lmin*2>lmax ){
int lmid = lmax/2 + lmax%2;
String p = val1.substring(0, lengths[0]-lmid);
String q = val1.substring(lengths[0]-lmid);
String r = val2.substring(0, lengths[1]-lmid);
String s = val2.substring(lengths[1]-lmid);
String u = karatsuba(p,r);
String w = karatsuba(q,s);
String v = karatsuba( subtract(q,p), subtract(s,r) );
return add( multiple10n(u,2*lmid) ,add( multiple10n(add(u,subtract(w,v)),lmid) , w));
} else // przy duzym zroznicowaniu dlugosci czynnikow uzywamy poprzedniej metody
return myMultipyBetter(val1, val2);
} else // jesli ktorasz liczba jest krotka to uzywamy poprzedniej metody
// to takze warunek stopu rekurencji
return myMultipyBetter(val1, val2);
}
private static String add(String val1, String val2 ){
return new BigInteger(val1).add(new BigInteger(val2)).toString();
}
private static String subtract(String val1, String val2 ){
return new BigInteger(val1).subtract(new BigInteger(val2)).toString();
}
private static String multiple10n(String val1, int val2 ){
return val1 + String.format("%0"+val2+"d", 0);
}
/**
* Ulepszona myMultiply: zamiast mnożyć każdą
* cyfrę osobno, dokonuje grupowania cyfr tak aby ich iloczyn nie
* przekraczał zakresu long w Javie
* @param val argument przez który zostanie wymnożony ten obiekt
* @return nowy obiekt będący wynikiem mnożenia
*/
public BigRational myMultipyBetter(BigRational val){
loguj("myMultipyBetter ( " + this + " , " + val + " ) START");
String[][] factors = new String[2][2];
factors[0][0]=numerator.toString();
factors[1][0]=denominator.toString();
factors[0][1]=val.numerator.toString();
factors[1][1]=val.denominator.toString();
// osobne mnożenie dzielnej i dzielnika
for(int i=0; i<2; i++)
factors[i][0] = myMultipyBetter(factors[i][0], factors[i][1]);
loguj("myMultipyBetter ( " + this + " , " + val + " ): factors[0][0] = " + factors[0][0]);
loguj("myMultipyBetter ( " + this + " , " + val + " ): BigInteger(factors[0][0]) = " + new BigInteger(factors[0][0]));
loguj("myMultipyBetter ( " + this + " , " + val + " ): factors[1][0] = " + factors[1][0]);
loguj("myMultipyBetter ( " + this + " , " + val + " ): BigInteger(factors[1][0]) = " + new BigInteger(factors[1][0]));
loguj("myMultipyBetter ( " + this + " , " + val + " ) = " + new BigRational( new BigInteger(factors[0][0]), new BigInteger(factors[1][0]) ));
return new BigRational( new BigInteger(factors[0][0]), new BigInteger(factors[1][0]) );
}
private static String myMultipyBetter(String val1, String val2){
String[] factors = new String[]{ val1, val2 };
int[] lengths = new int[2];
int[] lengthsM = new int[2];
long[][] ciphers = new long[2][];
int minus[] = new int[2];
for(int j=0; j<2; j++){ // dla każdego z czynników
lengths[j] = factors[j].length();
if( factors[j].charAt(0) == '-' ){
lengths[j]--;
minus[j]=1;
}
lengthsM[j]= (MULTI_CIPHER-1+lengths[j]) / MULTI_CIPHER;
ciphers[j] = new long[ lengthsM[j] ];
for(int k=0;k<lengthsM[j];k++){
int left = lengths[j]-k*MULTI_CIPHER-MULTI_CIPHER+minus[j];
if(left<minus[j])
left = minus[j] ;
ciphers[j][k]=Integer.parseInt(
factors[j].substring(
left,
lengths[j]-k*MULTI_CIPHER+minus[j]
)
);
}
}
int outLength = lengthsM[0]+lengthsM[1];
long[] productInt = new long[outLength];
for(int p0=0; p0<lengthsM[0]; p0++)
for(int p1=0; p1<lengthsM[1]; p1++){
productInt[p0+p1]+=(ciphers[0][p0]*ciphers[1][p1]);
for(int j=p0+p1;(j<outLength-1) && (productInt[j]>=MAX_M_CIPHER);j++){
productInt[j+1] += (productInt[j] / MAX_M_CIPHER);
productInt[j] %= MAX_M_CIPHER ;
}
}
factors[0]="";
int j = outLength-1;
while((j>=0) && (productInt[j]==0l))
j--;
if(j<0)
factors[0]="0";
else {
if( (minus[0]+minus[1])%2 == 1 )
factors[0] = "-";
factors[0] = factors[0] + productInt[j];
for(j--;j>=0;j--)
factors[0] = factors[0] + String.format(FORMAT_M_CIPHER, productInt[j]);
}
return factors[0];
}
/**
* Oblicza iloczyn tego obiektu i argumentu.<BR>
* zgłasza NullPointerException jeśli argument jest null, analogicznie do BigInterger.multiply(BigInterger)
* @param val argument przez który zostanie wymnożony ten obiekt
* @return nowy obiekt będący wynikiem mnożenia
*/
public BigRational myMultiply(BigRational val){
loguj("myMultiply ( " + this + " , " + val + " ) START");
String[][] factors = new String[2][2];
factors[0][0]=numerator.toString();
factors[1][0]=denominator.toString();
factors[0][1]=val.numerator.toString();
factors[1][1]=val.denominator.toString();
for(int i=0; i<2; i++){
int[] lengths = new int[2];
int[][] ciphers = new int[2][];
int minus[] = new int[2];
for(int j=0; j<2; j++){
lengths[j] = factors[i][j].length();
if( factors[i][j].charAt(0) == '-' ){
lengths[j]--;
minus[j]=1;
}
ciphers[j] = new int[lengths[j]];
for(int k=0;k<lengths[j];k++)
ciphers[j][k]=Integer.parseInt(factors[i][j].substring(lengths[j]-k-1+minus[j], lengths[j]-k+minus[j]));
}
int outLength = lengths[0]+lengths[1];
int[] productInt = new int[outLength];
for(int p0=0; p0<lengths[0]; p0++)
for(int p1=0; p1<lengths[1]; p1++){
productInt[p0+p1]+=(ciphers[0][p0]*ciphers[1][p1]);
}
for(int j=0;j<outLength-1;j++){
productInt[j+1] += (productInt[j] / 10);
productInt[j] %= 10 ;
}
factors[i][0]="";
int j = outLength-1;
while((j>=0) && (productInt[j]==0))
j--;
if(j<0)
factors[i][0]="0";
else {
if( (minus[0]+minus[1])%2 == 1 )
factors[i][0] = factors[i][0] + "-";
for(;j>=0;j--)
factors[i][0] = factors[i][0] + productInt[j];
}
}
loguj("myMultiply ( " + this + " , " + val + " ) = " + new BigRational( new BigInteger(factors[0][0]), new BigInteger(factors[1][0]) ));
return new BigRational( new BigInteger(factors[0][0]), new BigInteger(factors[1][0]) );
}
/**
* Proste mnożenie bazujące na działaniach klasy BigInteger
* @param val argument przez który zostanie wymnożony ten obiekt
* @return nowy obiekt będący wynikiem mnożenia
*/
public BigRational bigIntegerMultiply(BigRational val){
loguj("bigIntegerMultiply ( " + this + " , " + val + " ) = " + new BigRational(
// numerator * val.numerator
numerator.multiply(val.numerator),
// denominator * val.denominator
denominator.multiply(val.denominator)));
return new BigRational(
// numerator * val.numerator
numerator.multiply(val.numerator),
// denominator * val.denominator
denominator.multiply(val.denominator));
}
/**
* Dzielenie zbudowane na funkcjach BigInteger
* @param val wartośc dzielnika
* @return nowy obiekt o wartości ilorazu
*/
public BigRational divide(BigRational val){
// denominator * val.numerator
if(val.compareTo(ZERO) == 0)
throw new ArithmeticException("BigRational divide by zero");
BigInteger newDenominator = denominator.multiply(val.numerator);
if( newDenominator.compareTo(BigInteger.ZERO) == 0)
throw new ArithmeticException("BigRational divide by zero");
return new BigRational(
// numerator * val.denominator
numerator.multiply(val.denominator),
// denominator * val.numerator
newDenominator);
}
/**
* Porównuje z inna wartością analogicznie jak w BigInteger
* @param val wartośc do porównania
* @return 1,0 lub -1 gdy val jest odpowiednio większe, równe i
* mniejsze bazowej wartości.
*/
public int compareTo(BigRational val){
return subtract(val).numerator.compareTo(BigInteger.ZERO);
}
@Override
public boolean equals(Object x){
if(x instanceof BigRational)
try{
if(((BigRational)x).compareTo(this) == 0)
return true;
}catch(Exception e){
}
return false;
}
/**
* Zwraca tekstoy opis liczby wymiernej
* @return Tekstowa reprezentacja liczby wymiernej (dwie liczby BigInteger rozdzielone ukośnikiem /
*/
@Override
public String toString(){
return numerator.toString()+"/"+denominator.toString();
}
private static void loguj(String komunikat){
//Logger.getLogger(BigRational.class.getName()).log(Level.INFO, komunikat);
System.err.println(komunikat);
}
}
|
Post został pochwalony 0 razy
|
|
