Wichtige Frage (Überlauf erkennen)
lima-city → Forum → Programmiersprachen → Java
algorithmus
anwendung
beitrag
bit
determinante
division
funktion
gren
long
lsung
multiplikation
mglicherweise
overflow
point
positiv
prozessor
rundungsfehler
ungefhr
verfahren
vorzeichen
-
Hallo,
weiß jemand wie ich in Java herausfinden kann, ob die Multiplikation von zwei (positiven) Longs einen Überlauf erzeugt hat?
Im Augenblick habe ich eine Lösung, die ungefähr so aussieht:
public static long mul(long a, long b){
long c = -1;
if (Long.Max_Long / a < b) {
//Fehlerbehebung
}else{
c = a*b;
}
return c;
}
Da kommt aber eine zeitaufwändige Division rein, die ich sehr gern vermeiden würde (ist der bottleneck in meinem Programm) -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
-
schau mal hier nach (Galileo Computing):
http://www.java-tutor.com/javabuch/javainsel6/javainsel_05_002.htm#mj999cf871a3433f0ca0ccd852898a72a1
Dort verwenden die BigInteger, um zu prüfen, ob ein Überlauf stattgefunden hat.
BigInteger arbeitet intern mit Strings. Ob das schneller geht, als die Division
kann ich nicht sagen
--dcsh -
Hallo,
weiß jemand wie ich in Java herausfinden kann, ob die Multiplikation von zwei (positiven) Longs einen Überlauf erzeugt hat?
Im Augenblick habe ich eine Lösung, die ungefähr so aussieht:
public static long mul(long a, long b){
long c = -1;
if (Long.Max_Long / a < b) {
//Fehlerbehebung
}else{
c = a*b;
}
return c;
}
Da kommt aber eine zeitaufwändige Division rein, die ich sehr gern vermeiden würde (ist der bottleneck in meinem Programm)
Du könntest überprüfen, ob beide Zahlen kleiner als 2^31 sind.
Dann hast du zwei vergleiche.
Allerdings sind es dann ja eigentlich nur noch int's.
Jens -
dank für die Antworten.
Schade, dass das nicht einfacher geht (mit C lässt sich ein overflow ja ohne Zeitverlust erkennen)
BigInteger ist extrem langsam.
Und der zweite Vorschlag hilft mir auch nicht weiter, da ich eine long Variable benutze, weil sie die Summe von zwei Integern aufnehmen soll (also möglicherweise mehr als 32 Bit). -
ich gehe mal davon aus, dass du unsigned int verwendest.
mache die gleiche operation doch mit einem Float wert.
wenn die beiden ergebisse nicht übereinstimmen, stimmt was nicht.
hatt es in java Float?
wenn ja, solltest du eine erhöhte genauigkeit nehmen.
und wenn es einen datentyp mit mehr bits hat, mache einfach die addition mit dem, anstatt dem float, des is performanter. -
hi,
nur interessehalber: was für eine applikation versuchst du eigentlich zu programmieren? Möglicherweise kann man deinen algorithmus parallelisieren und über mehrere prozesse laufen lassen, was das ganze beschleunigen würde.
Grüße
Martin -
@chaoscode: Java hat dummerweise nur signed.
Java hat natürlich float (sogar double
)
Ich werde das mal ausprobieren mit den Vergleichen von float/long, kann mir aber nicht vorstellen, dass das schneller geht.
Aber wenn ich nur float nehme, kriege ich ja Rundungsfehler rein. Außerdem haben floats auch einen begrenzten Wertebereich.
@martin-tanler: Einen Algorithmus zu parallelisieren hilft doch nur wirklich was, wenn man mehrere Prozessoren/kerne hat. Aber es ist eh eine Java Anwendung, d. h. ich komm an diese Lowlevelebenen gar nicht ran.
Also die Anwendung soll die konvexe Hülle von Punkten zu finden, und das möglichst schnell.
Dazu brauche ich einen Algorithmus, der herausfindet, ob drei Punkte eine Links- oder eine Rechtskurve bilden.
Hier mal ein Teil der zugehörigen Klasse:
Point{
public int x;
public int y;
public int isLeft(Point a, Point b){
/*die Funktion gibt 1 zurück, wenn sich der Punkt links von der Geraden, die durch a und b geht, befindet. 0 für auf der Geraden und -1 für rechts von der Geraden.*/
long a11, a12, a21, a22;
a11 = (long) b.x - a.x; /*man muss long nehmen, da das Ergebnis möglicherweise nicht in den Wertebereich von int passt*/
a12 = (long) x - a.x;
a21 = (long) b.y - a.y;
a22 = (long) y - a.y;
return signOfDet(a11, a12, a21, a22); /*berechnet das Vorzeichen der Determinante*/
}
private int signOfDet(long a11, long a12, long a21, long a22){
//hier gibt es dann potentiell Überläufe.
}
}
Achja, noch eine zweite Frage:
Wie kann man von zwei Zahlen a und b
a/b und a%b
in einem Rechenschritt ausrechnen? Also, dass ich den Rest der Division praktisch auch noch gleich mitbekomme?
Wenn der Prozessor a/b berechnet hat, muss er ja schließlich auch den Rest wissen. Nur weiß ich nicht, wie ich da rankomme.
Beitrag geaendert: 4.2.2007 15:10:27 von cga -
Hi,
du hast natürlich recht, daß parallelisieren mit einem prozessor keine Sinn macht. Du könntest aber ein kleines c Programm von deinem java progamm aus starten (Runtime.exec(...) soweit ich mich erinner), das die berechnungen für dich übernimmt. Ob dies dann wirklich schneller ist, weiß ich allerdings auch nicht. Ich hab versucht die Berechnung des Determinanten Vorzeichens zu umgehen, hab aber nur noch mehr rundungsfehler dadurch erhalten.
Du kannst nich modulo und divide zugleich ausfürhen (auch wenn intern natürlich der rest klar ist). Aber du kanns tine funktion specialDivide() programmiren die natürlich die Division durch subtraktion berechnet und dir zum schluss ein Objekt Result zurückgibt weleches die funktionen getResult() und getRemaineder(), beihnaltet.
Sorry, daß ich dir bei der long sache nicht weiterhelfen kann. Dies sind immer problematische Ding in der Informatik.
Grüße
Martin
Beitrag geaendert: 4.2.2007 17:52:21 von martin-tanler -
@martin-tanler
Java ist leider so langsam, dass eine while-Schleife mit schrittweisem Abziehen langsamer ist als wenn man a/b und a%b hinternander berechnet.
Die schnellste Lösung, die ich gefunden habe ist:
long q, r;
q = a/b;
r = a - q*b // schneller als r = a%b;
falls es dich interessiert (du scheinst mir ja ein erfahrener Programmierer zu sein), es gibt tatsächlich ein Verfahren, das Vorzeichen einer Determinante einer 2x2 Matrix mit n-bit Integern unter Verwendung von n-bit Arithmetik auszurechnen!!!
Stichwort Gausssche Umformungen.
Addition eines Vielfachen einer Zeile zu einer anderen ändert das Vorzeichen nicht!
Multiplikation einer Zeile mit einer negativen Zahl ändert das Vorzeichen, mit einer positiven Zahl ändert das Vorzeichen nicht.
So kann man die Zahlen in der Matrix so klein kriegen, dass sie keinen Überlauf mehr erzeugen. Während der Gaussschen Umformungen kann natürlich auch ein Überlauf auftreten, das ist aber nicht schlimm, solange man es erkennt (das Vorzeichen ergibt sich in so einem Fall sofort).
Aber wie gesagt, um Überläufe in Java zu erkennen, muss eine Division gemacht werden!!!
In C schaut man sich einfach das overflow flag an.
In C kriegt man ja auch den Rest bei einer Division mitgeliefert!!
Auf dieser Überlegung basiert dann auch ein Verfahren, das für eine 2x2 Matrix aus Gleitkommazahlen das Vorzeichen der Determinante vollkommen ohne Rundungsfehler berechnet.
Im Gegensatz zu dem simplen Vorgehen a_11 * a_22 - a_12 * a_21.
Also mir reichts jetzt langsam mit Java, ab jetzt schreib ich das in C++ weiter!
Beitrag geaendert: 5.2.2007 19:09:04 von cga -
Hi cga,
das ist wohl die beste entscheidung. Wie gesagt wenn man einmal eine java oberfläche drauf aufbauen möchte, kann man das ja immer nocht tun (über prozessaufruf). Zeitkritische Sachen würde ich auch immer in C/C++ programmieren. Java gebe ich den vorzug, wenn es um standardmäßige anwendungen geht (mit einer schönen oberfläche halt, ohne irgendwas zeitkritisches) oder webservices oder sowas geht.
Es lohnt sich halt je nach Umständen die passende Programmiersparche zu wählen.
Also, viel Erfolg noch beim coden (und bug fixen :-)).
Beitrag geaendert: 6.2.2007 3:08:08 von martin-tanler
Beitrag geaendert: 6.2.2007 3:12:37 von martin-tanler -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
