009
25.09.2002, 10:51 Uhr
~0xdeadbeef
Gast
|
| Zitat: |
Leif führt seine Rechnungen im Zehnersystem durch, java.math.BigInteger rechnet mit einer Zahldarstellung zur Basis 2^32. Das allein sollte Java *erheblich* schneller machen als Leifs Programm, und es ist insofern keine Vergleichbarkeit der verwendeten Algorithmen gegeben.
|
Jepp, das ist mir inzwischen auch aufgefallen (use the force, read the source ;-) ). Wie dem auch sei, ich hab das Programm mal nach Java übersetzt (s.u.); bei mir läuft es in 57 Sek. durch.
@ Leif: Lass dasProgramm mal bei dir laufen; ich kann deine anderen Codes nicht kompilieren, hab also keine Vergleichswerte. Hier der Code:
| C++: |
//Bench.java
import java.util.*;
import java.sql.*;
class Bench {
public static void main(String[] args) {
try {
GregorianCalendar start, stop;
System.out.println("Zwei zwanzigstellige Zahlen werden 1'000'000mal multipliziert...");
String sZahl1 = "31415926535897932384"; //$\pi \cdot 10^{19}$
String sZahl2 = "27182818284590452354"; //$ e \cdot 10^{19}$
CLangzahl a = new CLangzahl(10, 40);
CLangzahl b = new CLangzahl(10, 40);
for(int i=0; i<20; i++) a.SetStelle(i, (int) (sZahl1.charAt(i) - '0'));
for(int i=0; i<20; i++) b.SetStelle(i, (int) (sZahl2.charAt(i) - '0'));
start = new GregorianCalendar();
for(int iCounter=0; iCounter<1000000; iCounter++) a.Mult(b);
stop = new GregorianCalendar();
System.out.println("Fertig, Dauer: " + new Time(stop.getTimeInMillis() - start.getTimeInMillis() - 60 * 60 * 1000 /*GMT ausgleichen*/));
} catch (Exception e) {
e.printStackTrace();
}
}
}
//CLangzahl.java
class CLangzahl {
private int iStellen; // Anzahl der Stellen der Zahl
private int iBasis; // Basis des verwendeten Zahlsystems
private int[] aiZiffern; // Die Zahl im Speicher
private static String sZeichen = "0123456789ABCDEF";
public CLangzahl(int Basis, int Stellen) throws Exception {
if(Basis<2 || Basis > 16)
throw new Exception("CLangzahl.CLangzahl: Basis < 2 || Basis > 16");
iStellen = Stellen;
iBasis = Basis;
aiZiffern = new int[Stellen];
SetNull();
}
public void SetNull() {
for(int i=0; i<iStellen; i++) aiZiffern[i] = 0;
}
public void SetStelle(int Stelle, int Value) throws Exception {
if(Stelle>=iStellen) throw new Exception("CLangzahl.SetStelle: Indexfehler");
if(Value>=iBasis) throw new Exception("CLangzahl.SetStelle: Basisfehler");
aiZiffern[iStellen-1-Stelle] = Value;
}
private void ArrayAdd(int[] aiZiel, int[] aiS1,
int[] aiS2, int iS2Start) {
int iTeilsumme, iUebertrag=0;
int iAnzahlZiffern = Math.min(aiS1.length, Math.min(aiS2.length,
aiZiel.length));
for(int i=0; i<iS2Start; i++)
aiZiel[aiZiel.length-1-i] = aiS1[aiS1.length-1-i];
for(int i=iS2Start; i<iAnzahlZiffern; i++) {
iTeilsumme = aiS1[aiS1.length-1-i] + iUebertrag +
aiS2[aiS2.length-1-i+iS2Start];
iUebertrag = (iTeilsumme >= iBasis) ? 1 : 0;
aiZiel[aiZiel.length-1-i] = (iUebertrag == 0) ? iTeilsumme :
(iTeilsumme - iBasis);
}
}
public void Mult(CLangzahl aZahl) throws Exception {
if(aZahl.iBasis != iBasis) throw new Exception("CLangzahl.Mult: Unterschiedliche Zahlsysteme");
if(aZahl.iStellen != iStellen) throw new Exception("CLangzahl.Mult: Unterschiedliche Stellenzahl");
int[][] aiMultiplikation = new int[iBasis][];
aiMultiplikation[0] = new int[iStellen+1];
for(int i=1; i<iBasis; i++) {
aiMultiplikation[i] = new int[iStellen+1];
ArrayAdd(aiMultiplikation[i], aiMultiplikation[i-1],
aiZiffern, 0);
}
SetNull();
for(int i=0; i<iStellen; i++)
if(aZahl.aiZiffern[i] != 0)
ArrayAdd(aiZiffern, aiZiffern,
aiMultiplikation[aZahl.aiZiffern[i]],
iStellen-i-1);
}
}
|
GNUß,
0xdeadbeef |
