Der Offizielle Developer Thread - Topic

Member

Posts: 11,288

Joined: Jan 20 2007

Gold: 20.69

Apr 9 2017 06:05am

Quote (xXxSebixXx @ 9 Apr 2017 11:09)

Gibt so Projekte bei denen man sich anmelden kann und Speichersharing betreibt. Da kann man recht große und oder genaue Zahlen mit rausfinden. Lokal wirds schwierig, es sei den du hast ein haufen RAM zur Verfügung ;)
Die Theorie dahinter ist, dass du beim berechnen deiner Zahl Speicher anforderst. Dann ist der einzige limitierende Faktor wie genau/groß die Zahl sein kann halt die größe des Speichers der deinem Programm zur Verfügung gestellt werden kann.

mit 16GB ram kannst du 2^17179869184 unetschiedliche zahlen darstellen. locker mehr als die anzahl der atome im universum. dass eine zahl so groß wird, dass eine einzige Zahl an RAM Grenzen stößt, ist praktisch immer ausgeschlossen. Selbst mit fucking 4MB Speicher kannst du 2^(4 * 1024 * 1024) = 2^(4194304) Zahlen darstellen. So viele, dass ich im Kopf keine sinnvolle AUssage über die größe machen kann. Schätze die zahl würde nicht auf ein DIN A4 Blatt in Schriftgröße 10 passen...

EDIT:
Eine große Zahl braucht nie "viel" RAM.
Stell's dir so vor:
DU hast 20Kästchen Karopapier und schreibst 20 Ziffer rein.
Das könnne 20 Zahlen von 0-9 sein - nicht gerade viel.
Es könnte aber auch eine Zahl zwischen 0 und 99999999999999999999 sein -> schon echt keine kleine Zahl.

Im 4MB RAM Beispiel hast du über 4 millionen Kästchen (in die du zwar nur 0-1 schreiben kannst), aber der Effekt ist der gleiche und die maximale Zahl ist arschgroß

This post was edited by Kasiir on Apr 9 2017 06:13am

BizepsBodo

Member

Posts: 4,018

Joined: Aug 30 2014

Gold: 23,680.50

#142

Apr 9 2017 06:16am

Quote (Kasiir @ Apr 9 2017 11:04am)

Gibt in vielen sprachen libs für solche zahlen. Kannst einfach benutzen und hast nicht die Möglichkeit da weitere Fehler einzubauen. Kannst einfach googlen "<Programmiersprache> + arbitrary large numers". Oder "<Sprache> arbitrary precision library". Für C (mit C++ wrapper) z.B. https://gmplib.org/

Nicht empfohlen, trifft wohl her nicht auf deine Situation zu:
wenn es kritisch bezüglich speicherbedarf und/oder laufzeit ist, wäre es wohl besser über das genaue Problem nachzudenken.
Es wäre theoretisch denkbar einfach alle Zahlen in einem byte array aneinander zu hängen.
Zusätzlich man man eine weitere liste mit byte-offsets die immer den start jeder zahl markieren. Eine zahl geht dann einfach von ihrem start bis zum des Nachfolgers.
Wenn man vor allem iterieren will und space sehr kritisch ist, (und es sich lohnt, weil es auch kleine Zahlen zwishcen den sehr großen gibt) könnte man prefix-free codes nutzen (https://en.wikipedia.org/wiki/Prefix_code). Gibt noch 100e Möglichkeiten, aber hängt sehr davon ab, was für Zahlen man hat und was die Anforderungen sind.
Wahrscheinlicher ist auf jeden Fall, dass du mit einer einfachen library am besten bedient bist.

mir geht es akut darum eine zahlenfolge innerhalb von 60 sekunden / 1min zu generieren die jedoch bereits nach ~3-4sekunden laufzeit über die größe aller normalen datentypen hinaus geht.

eine fertige lib finde ich eher solala

selber dachte ich halt spontan an die lösung mit einem array pro zahl, welches dann die zahl beispielsweise in kleine 10^8 große stücke aufteilt.
eine bessere idee kam mir bisher nicht, allerdings denke ich, dass es doch etwas einfacher gehen muss? :unsure:

Kasiir

Member

Posts: 11,288

Joined: Jan 20 2007

Gold: 20.69

#143

Apr 9 2017 06:25am

Quote (BizepsBodo @ 9 Apr 2017 13:16)

was jetzt?
eine zahlenfolge? dann ofc ein array und einfach überhaupt niemals als große zahl interpretieren... sondern eben als folge.

sonst weiß ich nicht, was du mit "zerhacken" meinst aber mit einem einfach array, wäre es doch echt easy. einfach wenn eine zahl nicht in num passt, dann in num nur neuezahl - max und num[i+1] += 1

BizepsBodo

Member

Posts: 4,018

Joined: Aug 30 2014

Gold: 23,680.50

#144

Apr 9 2017 06:27am

Quote (Kasiir @ Apr 9 2017 02:25pm)

was jetzt?
eine zahlenfolge? dann ofc ein array und einfach überhaupt niemals als große zahl interpretieren... sondern eben als folge.

sonst weiß ich nicht, was du mit "zerhacken" meinst aber mit einem einfach array, wäre es doch echt easy. einfach wenn eine zahl nicht in numpasst, dann in numnur neuezahl - max und num[i+1] += 1

meinte mit zahlen folge zb 2^x, also sowas hier:

1, 2, 4, 8, 16, 32 ....

die zahlen sind dann alle eigenständig, aber kannst dir natürlich denken wie schnell die zahl in 60 sekunden bei normalen rechenspeed eskaliert