Binär - Dezimal (ANZAHL ZIFFERN)

5 Antworten

Vom Fragesteller als hilfreich ausgezeichnet

Die Zahl kannst du berechnen mit 2 hoch bit. Willst du direkt die Anzahl der Stellen berechnen, musst du davon den Logarithmus berechen und diesen auf die nächst größere Zahl aufrunden. So wirst du z.B. feststellen, dass die 32-bit-Zahl nur 10 Stellen hat.

sehr gute antwort danke. Habs probiert 2 hoch bits und davon den 10-er logarithmus und das aufrunden hat funktioniert.

Muss nun nur noch schauen wie ich das programmiere..

Ich programmiere das mit java. Da benutze ich die Java-Klasse BigInteger.

Mit dem kann ich primzahlen mit bis zu 2000 Ziffern! berechnen.

Nur ob meine rechenleistung ausreicht um von einer 2000 Ziffrigen zahl den logarithmus zu bilden muss ich noch testen. Allerdings bezweifle ich es.

Vielen dank trotzdem für deine antwort

1
@realdee

Hier könnte vielleicht ein Logarithmusgesetz weiterhelfen:

log(2^Bits) = Bits * log(2).

1
@realdee
Nur ob meine rechenleistung ausreicht um von einer 2000 Ziffrigen zahl den logarithmus zu bilden muss ich noch testen.

Unterschätze mal nicht die Geschwindigkeit eines Superskalar Prozessorkerns bei 2.4GHz. ;-)

0
@Melvissimo

ach. das kannte ich, hab aber nicht dran gedacht. Vielen Dank für diesen Tip!

0
@Roderic

Ja die geschwindigkeit hat mich echt überrascht. Dachte das die viiel langsamer sind. Aber das liegt wohl eher dran dass die meisten heutigen Software extrem innefizient programmiert sind und die meisten ressourcen für schnickschnack und design draufgeht.

Den Logarithmus einer solchen zahl, kann man mit JAVA auf jeden fall nicht einfach so ohne weiteres berechnen, da es die logarithmusfunktion nur für Zahlen bis 64-bit gibt.

0

Das müsste berechenbar sein, indem man die Zahl in mehrere (z. B. ) 32-bit Pakete teilt. Bin aber nicht ganz sicher, ob ich Deine Frage richtig verstehe.

Die exakte Formel (die fast jede Sprache versteht) lautet:

MaxAnzahlZiffern = ceil(log(2^Bit)/log(10))

ABER: Bei 64 Bit (unsigned = ohne Vorzeichen) kann man nicht alle 20 Stellen voll (1...9) nutzen, denn die 1. Ziffer kann bei der Obergrenze nur 1 sein. (also eigentlich floor() =Abrunden statt ceil() =Aufrunden.

JAVA kennt zwar BigInteger, wird dann aber noch langsamer als uInt64!!

Besser geeignet sind Sprachen wie c++ oder PureBasic, die die 64Bit CPU und alle Kerne voll nutzen!

Ich möchte behaupten, dass Du nicht mal 19 stellige Primzahlen unter 5 min schaffen wirst. (das soll nicht demotivieren, sondern Ansporn sein)

Es gibt bereits über 4 Online-Rechner, die um die 60 stellige Primzahlen erfolgreich unter 2 min schaffen: hoch optimierter Code oder Zwischenspeicher.

Was viele Anfänger nicht beachten: die Berechnungen sind stark nichtlinear, d.h. die Rechenzeit steigt etwa exponentiell an!

Nicht die Hardware ist entscheidend, sondern Algorithmus und Software!
(da kann man Verbesserungsfaktoren um 100 herausholen, was keine Hardware schafft)

Hier eine Primzahl zum Üben: 9223372036854775783

habe da auch schon dran gedacht das mal mit c/c++ zu machen. Da ich es aber nur "als spass" in der freizeit mache hab ich grad keine zeit dies zu tun.

Ich kann in JAVA 1000-stellige Primzahlen berechnen lassen und das in ca. 1 min. Wobei die berechnungszeit auch vom glück abhängt, wie nahe man an einer primzahl startet.

Ich bin mir auch ziemlich sicher dass die Zahl auch eine Primzahl ist, weiss allerdings nicht genau wie ich das prüfen soll. Hier ist die Funktion die ich nutze die in der standard Java-library bereits vorhanden ist:

    String basisZahl = "15605615406507";
    
    // Startzahl als BigInteger definieren und initialisieren
    BigInteger startzahl = new BigInteger(basisZahl);
    
    // sucht ab der Startzahl die nächste Primzahl
    BigInteger primzahl = startzahl.nextProbablePrime();
    
    System.out.println(primzahl);

Das umrechnen mit bits benötige ich nur, damit man auch eine 1024-bit zahl oder eine 1000 stellige zahl suchen kann ohne vorher eine 1000 stellige Zahl als basiszahl schreiben zu müssen, weil das dauert dann etwas und ist fehleranfällig (nur 999 oder 1001 Ziffern) :-)

Hier ein beispiel für 60-Stellig: (0.057 sekunden)

586801795797689907301737523271843482556542101777625487523881

Oder hier eine 500-stellige: (4.823 sekunden) 48079777495619644027731399215911206980558936238452187641003247712317867846488396482688722335930281579506080005846426750839824530288382728678393373996898847350752453704004579088693406330991622998577285765479998808618183015728232782543349469560044230902274611847773590443579623343066593908718556970888529024542860914312137002747018243199105185615131510523436951235763180354990313554320633374088227377199647952906419532900454601007158090609081927257635841448045866276428362991576323330006730864970252601

Den genauen algorithmus der funktion hab ich aber noch nicht angeschaut. Die beschreibung verrät aber schon mal folgendes:

"Returns the first integer greater than this BigInteger that is probably prime. The probability that the number returned by this method is composite does not exceed 2-100. This method will never skip over a prime when searching..."

Heisst soviel wie: Die Warscheinlichkeit, dass die berechnete Zahl keine Primzahl ist liegt bei ~ 0.000000000000000000000000000079% Es wird beim suchen keine Primzahl übersprungen.

Auch die ersten 100'000 Primzahlen sind schnell gefunden: (12.239 s) Die ersten kleinen zahlen hab ich überprüft und die stimmen alle. Die 100'000-ste Primzahl währe laut dieser Java-Funktion dann die: 1299709

um beim programm eine 1000 stellige primzahl zu suchen, muss ich wissen wie viel bit eine 1000-stellige zahl hat um sie zu initialisieren. Das mach ich mit: " bit = stellen / lg(2) " und und runde das dann.

Die grösste bekannte Primzahl hat übrigens 17,4 Mio. Ziffern!

http://www.spiegel.de/wissenschaft/mensch/17-4-millionen-stellen-computer-entdeckt-rekord-mersenne-primzahl-a-882646.html

1
@realdee

Ich bin beeindruckt. Scheint ein effizienter Algorithmus zu sein.
Beide Zahlen sind wirklich Primzahlen.
ABER "...berechnungszeit auch vom glück abhängt..." und "...Warscheinlichkeit, ..." hört sich nach "Abkürzung" an. Hast Du Dir die Zahl selbst zufällig ausgedacht, oder wurde sie vorgeschlagen?

Oder kann es sein, dass das JAVA Programm Internet benutzt und auf Datenbanktabellen zurück greift? Auch schöne Primzahl: 7272727232323272323232723272327272327232727272327232323272723232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323232323272723232327232727272327232727232723272323232723232327272727

Ja, Umkehrfunktion lautet Bit = ceil(Stellen * log(10)/log(2)) = ceil(Stellen / lg(2))

http://www.gerdlamprecht.de/Primzahlen.htm 4.Große Primzahlen ausrechnen
findet man die 5 größten bekannten Mersenne-Prims auf die Stelle genau.

Unten sind 3 LINKS "Schnelle Prim-Algorithmen für große Zahlen"

1
@hypergerd

super danke. Also der algorithmus rechnet nur, hat also keinen internetzugriff oder eine tabelle. Allerdings versteh ich die rechnung nicht ganz und es hat einige verschiedene szenarien, je nach dem was für ein kriterium die zahl erfüllt.

Der algorithmus, bzw. die fertige funktion verlangt einen eingabewert, also eine zahl. Der rückgabewert ist dann die nächste primzahl die nach der gegebenen zahl kommt. Also prüft die funktion für jede nächste zahl, ob sie eine primzahl ist, wobei einige zahlen schnell ausgeschlossen werden können, da sie logischerweise nie eine primzahl sein kann..

ich habe bei meinem programm nun eine eingabe z.B. 100 stellen. Dann wird eine 100-stellige zufallszahl generiert und von da aus die nächste primzahl gesucht. Mann kann auch direkt prüfen ob eine Zahl eine primzahl ist. Ich möchte mit meinem programm aber einfach primzahlen finden die eine bestimmte grösse haben. Ich hab mal eine 2000- stellige zahl in 15 min. gefunden. eine 3000 und 4000 stellige habe ich selbst nach 1 stunde suchen bis jetzt noch nicht gefunden. Würde ich aber nur eine 4000-stellige zahl prüfen ob sie eine primzahl ist, sollte das in einer stunde schon möglich sein..

Komischerweise steigt die rechenzeit nicht umbedingt quadratisch an, sondern am anfang fast gar nicht und so ab 1000 stellen bei verdopplung der ziffern um einen faktor 10 oder noch mehr. Und ja womöglich benutzt der algorithmus eine abkürzung. Es gibt wie gesagt auch funktionen mit denen man genau bestimmen kann ob eine zahl eine prim ist, und auch funktionen, bei der man die benötigte warscheinlichkeit "beliebig" hoch einstellen kann. ich bin mit 2^(-100) zufrieden. Dafür ist der algorithmus richtig schnell für grosse zahlen.

Hab auch schon einen eigenen algorithmus geschrieben der ziemlich kurz war. Der war aber bei etwas grösseren zahlen (ca. 20-stellig) schon ziemlich am anschlag.

Du kannst mein aktuelles Programm hier downloaden:

http://www.filedropper.com/primzahltest

Datei => exportieren funktioniert noch nicht. Der rest schon. Während das programm eine primzahl sucht, kann man es nichtmehr bedienen. Also nicht übertreiben :-) sonst musst du es abschiessen oder warten ^^

1
@realdee

LINK führt nach Eingabe der Ziffern auf eine Seite mit Viren. Mich interessiert eher die Seite, von wo Du den Code von nextProbablePrime herbekommen hast.

0

Was möchtest Du wissen?