Java + sehr grosse Zahlen

**MaxP0W3R** · 11.04.2006, 17:58

Es gibt doch die Klasse BigInteger

**jahlives** · 12.04.2006, 06:56

@Max
Die Klasse habe ich schon ausprobiert, aber leider gibt es dort nichts wie ein Array, Set oder Map. Also kann ich keinen Zahlenbereich abbilden. Das Prob bei Vector, BitSet und Array ist, dass sich diese nur mit ints inisialisieren lassen. Und Maps sind so was von echt langsam

und speicherhungrig.
Kennst du irgendein Konstrukt in Java (so wie ein Behälter), dass sich auch mit long initialisieren lässt ? Oder ist es besser den gesamten Zahlenbereich in einzelne BitSets zu zerlegen und dann die einzelnen Vielfachen aus allen BitSet zu streichen ?

Danke und Gruss

tobi

**MaxP0W3R** · 12.04.2006, 07:54

Geht ein Array of BigInteger nicht ?

Initilaisieren lassen die sich über long und Strings, afair

Die Collections sind ja auch allgemein für Objects definiert und da kannste ja dann auch BigInteger reinstecken

**jahlives** · 12.04.2006, 08:17

Hallo Max

ein Array of BigInteger bringt mich leider auch nicht weiter, weil auch dieser als max Anzahl Elemente nur Integer.MaxValue haben kann. Ausserdem ist der Speicherverbrauch in diesem Falle wesentlich höher, weil für jedes Array Element ein BigInt reserviert werden muss. Drumm habe ich das bis anhin mit einem Array of Booleans gemacht. Jede Zahl entsprich dann dem Index des Elements und hat nur den Wert true oder false (false == Vielfache schon gerechnet). Braucht so am wenigsten Speicher...
Das Problem bei allen Methoden die Objekte verwenden ist wiederum der grosse Speicherverbrauch und die lahme Geschwindigkeit. z.B. mit einer HasMap dauert die Berechnung aller Primen bis ca 4 Mio ~3 min (mehr geht nicht, da mir dann der HeapSpeicher um die Ohren fliegt). Mit einem BitSet komme ich in 2 min bis zum maximalen Integer Wert.

Gruss

tobi

**MaxP0W3R** · 12.04.2006, 11:43

Zum Speicherproblem kann ich nur sagen, dass du beim Aufruf dem JavaInterpreter mehr Speicher zuweisen kannst.

Für den Datentyp fällt mir zur Zeit leider auch nichts ein...

**jahlives** · 12.04.2006, 12:16

Zum Speicherproblem kann ich nur sagen, dass du beim Aufruf dem JavaInterpreter mehr Speicher zuweisen kannst.

Kenn ich

Code:

java -Xmx300m Primen

Allein für Primen bis 4'000'000 fliegt mir auch bei grösstem HeapSpeicher bei der Map Methode der Speicher um die Ohren.
Einzige Möglichkeit (bis jetzt): Das Ganze kompilieren, dann kann auch Virtual Mermory verwendet werden (class File in exe)

Gruss

tobi

**closure** · 18.04.2006, 10:29

Hi,

schreib dir dein eigenes bitset. Als basistyp könntest du ein char-array
verwenden. Die entsprechenden operationen dann mittels bitarithmetik im aktuellen bereich des bitstrings.
Die frage ist ob das die optimale lösung ist. Es ist zwar schwierig
primzahlen unter kontrolle zu bringen aber man weiss doch einiges
über sie. So könnte man durch geschickt genutzte techniken, das
verfahren eventuell beschleunigen. So weiss man zum beispiel
das primzahlen weniger werden je weiter "hinten" man sich im
zu untersuchenden intervall befindet. Man könnte nun hingehen
und mit der bitsetmethode mit integern sieben.
Um dann weiter zu gehen und über die restmenge zu iterieren
und auf primialität zu testen.
Hier muss man nur vorsichtig mit carmichael-zahlen sein
wenn man den fermat-test verwendet. Der miller-rabin-test ist
mitunter besser geeignet.
Man kann noch weiter einschränken. Grundsätzliche genügt es ja
in einem intervall von 3 - X die ungeraden zahlen bis sqrt(X) zu unter
suchen. In diesem intervall arbeitest du dich vor. Erst mit dem sieb
und dann mit anderen methoden. Durch unterteilung des
rest-intervalls in entsprechende teilmengen kann man z.B. nach
besonderen primzahlen suchen z.B. N!+1 u. N!-1.
Es gibt noch mehr möglichkeiten. Zum beispiel die suche nach
primzahlzwillingen o.ä. wichtig und schwierig ist bei den verfahren
nur die durchsuchten mengen immer zu extrahieren. Also die
differenzmenge zu bilden und auf der ergebnismenge weiter zu suchen.

greets

Java + sehr grosse Zahlen