ubuntu--anfaenger
Anmeldungsdatum: 12. Oktober 2013
Beiträge: 1088
Wohnort: Belgien
|
Hallo, c++ Unterstützt keine "sehr sehr grossen Integer" Wie kann ich dieses Programm so umschreiben das es zb Primzahlen in Billiarden ausgeben kann(nicht das ich das brauche aber für einen Anfänger wie mich wäre das sehr Interessant umzusetzen) Geht das überhaupt? Mir ist auch klar das es aufs Betriebssystem irgendwann mal geht..das es stop sagt ☺ aber das wäre mir egal. Sollte ich das mit einem vector<int> versuchen oder besser mit einem array? Für ein paar Beispiele wäre ich sehr dankbar..da meine Programmier Technik noch nicht sehr weit ist.. 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 | #include <bits/stdc++.h>
//#include <iostream>
using namespace std;
void sieb(int n)
{
bool prim[n+1]; // +1 da Array 0
memset(prim, true, sizeof(prim));// memeset setzt das kompl Array auf true(1)
for(int p=2; p*p<=n; p++)// starte mit 2 da 1 keine prim ist, erhöhe p bis n(vielfaches)
{
if(prim[p]==true){ // wenn p true
for(int i=p*2; i<=n; i+=p) // siebe alle vielfache von i
prim[i]=false; //setze alle vielfache von i auf false
}
}
for(int p=2; p<=n; p++) // Durchlaufe p bis <=n
if(prim[p])
cout << p << " "; // gebe p aus
}
int main()
{
cout << "Programm zu berechnen der Primzahlen: ";
int n;
cin>>n;
cout << "Primzahlen bis: " << n << endl;
sieb(n);
cout << endl;
return 0;
}
|
lg,
|
NORACSA
Anmeldungsdatum: 31. Januar 2010
Beiträge: 180
|
unsigned long long ist ideal dafür! Wobei das Sieb des Eratosthenes mit Billiarden "etwas" viel RAM in Anspruch nimmt!
(wenn man nur 1 Byte pro Wahrheitswert nimmt, dann wären es 931 GB, bei einem Bit immerhin noch 116 GB, und das nur für 1 Billiarde. Wenn du mehr willst, dann eben umsomehr... 😀 ) Wenn du minimal Speicher sparen willst, dann würde ich nicht den Index p verwenden sondern p-2.
|
ubuntu--anfaenger
(Themenstarter)
Anmeldungsdatum: 12. Oktober 2013
Beiträge: 1088
Wohnort: Belgien
|
NORACSA schrieb
unsigned long long ist ideal dafür!
Ich hatte unsigned long long auch schon getestet, es macht aber keinen Unterschied ob ich int oder unsigned long long verwende, bei mir ist bei 8300000 schluss Kann es sein das die grenze von bool erreicht ist?
Wobei das Sieb des Eratosthenes mit Billiarden "etwas" viel RAM in Anspruch nimmt!
Ich hab 32gb ram und beobachte den ,bei dem maximal Wert was geht ist der ram sehr entspannt.Vielleicht ist auch Billiarden übertrieben..Aber mehr wie 10000000 müsste doch gehen?
|
NORACSA
Anmeldungsdatum: 31. Januar 2010
Beiträge: 180
|
Du könntest, wenn du das Ganze über eine Bit-Maske verwendest, immerhin auf die 8-fache Zahl kommen. Außerdem wirst du die Größe des Stacks modifizieren müssen, wenn du größere Datenmengen anlegen willst. ubuntu--anfaenger schrieb: Ich hab 32gb ram und beobachte den ,bei dem maximal Wert was geht ist der ram sehr entspannt.Vielleicht ist auch Billiarden übertrieben..Aber mehr wie 10000000 müsste doch gehen?
Siehe Edit oben, wobei ich mich um eine Größenordnung vertan habe. Das wären nur Billionen mit den 932 GB RAM. Mit Billiarden wären es ca. so viele TB. Vorallem würde ich an deiner Stelle mal über die Laufzeit nachdenken. Das nimmt abstruse Ausmaße an!
|
ubuntu--anfaenger
(Themenstarter)
Anmeldungsdatum: 12. Oktober 2013
Beiträge: 1088
Wohnort: Belgien
|
NORACSA schrieb
Du könntest, wenn du das Ganze über eine Bit-Maske verwendest, immerhin auf die 8-fache Zahl kommen.
Das hört sich Interessant an, werde mich darin einlesen.
Außerdem wirst du die Größe des Stacks modifizieren müssen
Vielleicht auch auf dem heap als array?
Das wären nur Billionen mit den 932 GB RAM. Mit Billiarden wären es ca. so viele TB.
lassen wir die Billarden weg..sagen wir bis Grenze 9999999 wäre bis da kein Laufzeitproblem.
Vorallem würde ich an deiner Stelle mal über die Laufzeit nachdenken. Das nimmt abstruse Ausmaße an!
Ich versuch mal zu erklären wie ich auf mein Vorhaben gekommen bin: 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45 | #include <iostream>
//#include <stdio.h>
using namespace std;
int main()
{
int n;
int N;
int i;
int carry;
int size;
int mul;
int res[500000];
cout << "Faktor!: " << endl;
cin >> N;
res[0] = 1;
carry = 0;
size = 1;
for(n = 2; n <= N; n++)
{
for(i = 0; i < size; i++)
{
mul = (res[i] * n) + carry;
res[i] = mul % 10;
carry = mul / 10;
}
while(carry > 0)
{
res[size++] = carry % 10;
carry /= 10;
}
}
cout << "Faktorial = ";
for(i = size-1; i >= 0; i--)
cout << res[i];
return 0;
}
|
Wie gesagt ich bin Anfänger und will lernen wie ich solche Probleme lösen kann.
|
user_unknown
Anmeldungsdatum: 10. August 2005
Beiträge: 17548
Wohnort: Berlin
|
NORACSA schrieb:
Wenn du minimal Speicher sparen willst, dann würde ich nicht den Index p verwenden sondern p-2.
Ich würde p/2, nicht p-2 nehmen, dann kann man doppelt so viele Bits im gleichen Speicher verwalten. Nur die 2 bedarf der Extrabehandlung. Und auch in den Schleifen i=3; i < MAX; i+=2 nehmen, alle geraden Zahlen überspringen, dürfte etwa doppelt so schnell sein, dann. Bzw., da 2 verschachtelte Schleifen, 4x.
|
user_unknown
Anmeldungsdatum: 10. August 2005
Beiträge: 17548
Wohnort: Berlin
|
Mit Scala habe ich vor einiger Zeit mal was geschrieben, damit erreiche ich in gut einer Minute: | time scala -DXmx=4G -nc -howtorun:script primesTo2.scala 4990000
...
85845101
85845127
85845167
86966034 count: 253804396
real 0m52,870s
user 1m1,704s
sys 0m7,210s
|
86966034 count: 253804396 Etwas mehr Ram ließe sich wohl noch rauskitzeln, aber keine Größenordnung. Scala kann man aber nicht gut Zeilenweise in C++ übersetzen. Seit > 20 Jahren habe ich, außer trivialen Supportfällen hier im Forum, kein C++ mehr gemacht. Lambdaausdrücke sind da sicher auch angekommen. Bestimmt gibt es auch etwas, das einem BitSet entspricht. 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 | object NPrimes extends App{
var cnt=0
def c(M:Int)={
val p=collection.mutable.BitSet(M+1)
p(2)=true
(3 to M + 1 by 2).map(p(_)=true)
for (i <-p) {
var jj=i.toLong*i;
var j=math.min(M,jj).toInt
while (j < M) {
cnt+=1
if (p (j))
p(j)=false
j+=i}
}
p
}
val i = args(0).toInt
/*"""
To get the number x with i primes below, it is nearly ln(x)*x. For small numbers
we need a correction factor 1.13, and to avoid a bigger factor for very small
numbers we add 666 as an upper bound.
"""*/
val x = (math.log(i)*i*1.13).toInt+666
println (c(x).take (i).mkString("\n"))
System.err.println (x + "\tcount: " + cnt)
}
|
Mit einer kl. Zahl lässt sich das Programm besser erklären:
| scala -DXmx=4G -nc -howtorun:script primesTo2.scala 6
2
3
5
7
11
13
678 count: 1032
|
Man übergibt dem Programm die Zahl 6, weil man die ersten 6 Primzahlen sucht. Das i ist gleich 6. Mit einer Formel wird dann bestimmt, dass man zur Sicherheit lieber 678 Primzahlen erzeugt; von denen werden dann die ersten 6 ausgegeben sowie die obere Grenze zu prüftender Zahlen, die 678. Woher ich die Formel habe, weiß ich nicht, wahrscheinlich Wikipedia. Groß-M steht für MAX; da das ganze Teil eines Codegolf-Wettbewerbs war, sind die Namen von mir gekürzt worden. Das ist ein Zwischenstand, vor Entfernung von Einrückungen usw. p ist das BitSet von Primes, welches erzeugt werden soll. p(2)=true setzt die 2 explizit auf true, weil danach nur die ungeraden Zahlen vorläufig auf true gesetzt werden. Der Algorithmus nimmt dann immer die kleinste Primzahl, und setzt alle Vielfachen davon auf auf false. Die CPU, auf der das lief, ist ein Core-i7, schon recht betagt. Wenn die Laufzeit keine große Rolle spielt, dann kann man BitSet auf Festplatte (SSD) schreiben und davon lesen, um sehr viel größere Primzahlen zu sammeln, aber die Geschwindigkeit wird dann natürlich einbrechen.
|
ubuntu--anfaenger
(Themenstarter)
Anmeldungsdatum: 12. Oktober 2013
Beiträge: 1088
Wohnort: Belgien
|
Danke für die vielen Tipps, Ich muss leider Morgen wieder arbeiten, das muss ich mir dann alles in Ruhe anschauen..wird dann eher etwas für nächstes Wochenende, das übersteigt schon meinen Wissensstand. 😳 lg,
|
rklm
Projektleitung
Anmeldungsdatum: 16. Oktober 2011
Beiträge: 12801
|
Ich würde mal prüfen, ob eine Bitmaske überhaupt so eine gute Datenstruktur ist. Unter 100 sind sie ja recht häufig, aber ich bin mir nicht sicher, wie sich das unter größeren Zahlen verhält. Sollten sie dann selten werden, wäre eine Bitmaske eine unfassbare Verschwendung von Speicher. Btw. da gibt es bestimmt auch eine Datenstruktur in der Stdlib oder bei boost für BitSets - und die ist garantiert effizienter als ein Array von bool.
|
seahawk1986
Anmeldungsdatum: 27. Oktober 2006
Beiträge: 11176
Wohnort: München
|
ubuntu--anfaenger schrieb: c++ Unterstützt keine "sehr sehr grossen Integer"
Das hängt auch von der Zielarchitektur (eine 64-Bit CPU ist dafür essentiell) um vom Compiler ab - für gcc gibt es ein __int128 sowohl signed als auch unsigned: https://gcc.gnu.org/onlinedocs/gcc/_005f_005fint128.html - mit passenden Bibliotheken (wie https://www.boost.org/doc/libs/1_75_0/libs/multiprecision/doc/html/boost_multiprecision/tut/ints/cpp_int.html) kann man auch darüber hinaus gehen, aber das geht dann zu Lasten der Performance, wenn die CPU das nicht nativ beherrscht.
|
rklm
Projektleitung
Anmeldungsdatum: 16. Oktober 2011
Beiträge: 12801
|
Wie gesagt, da würde ich zu einem Bitset greifen - gibt es sogar in der STL:
|
ubuntu--anfaenger
(Themenstarter)
Anmeldungsdatum: 12. Oktober 2013
Beiträge: 1088
Wohnort: Belgien
|
Das ist jetzt viel Input für mich, wird Zeit in Anspruch nehmen..werde die Threads zu gegebener Zeit abarbeiten. rklm schrieb
Unter 100 sind sie ja recht häufig, aber ich bin mir nicht sicher, wie sich das unter größeren Zahlen verhält.
Ich glaube das ist eines der wichtigsten noch ungelösten Rätsel, wenn Du das Beschreiben kannst, ist glaube ich 1000000$ Preisgeld drauf
Btw. da gibt es bestimmt auch eine Datenstruktur in der Stdlib oder bei boost für BitSets - und die ist garantiert effizienter als ein Array von bool.
Mal eine Anfänger Gegenfrage, denkst Du das das an dem bool Array liegt, da es keinen Unterschied macht ob ich int oder unsigned long long verwende? bei 8300000 gibt der alle Primzahlen aus, bei 8400000 (sowohl bei int wie auch bei unsigned long long)segmentation fault seahawk1986 schrieb
Das hängt auch von der Zielarchitektur (eine 64-Bit CPU ist dafür essentiell) um vom Compiler ab - für gcc gibt es ein int128 sowohl signed als auch unsigned: https://gcc.gnu.org/onlinedocs/gcc/_005f_005fint128.html - mit passenden Bibliotheken (wie https://www.boost.org/doc/libs/1_75_0/libs/multiprecision/doc/html/boost_multiprecision/tut/ints/cpp_int.html) kann man auch darüber hinaus gehen, aber das geht dann zu Lasten der Performance, wenn die CPU das nicht nativ beherrscht.
Ich hatte mir schonmal die boost Bibliotheken runtergeladen..ich brauchte das mal für regexp, ich denke aber das ist zu hoch für mich, solange ich die Grundlagen im Programmieren nicht behersche sollte ich eher denke ich bei einfachen Dingen bleiben. lg,
|
rklm
Projektleitung
Anmeldungsdatum: 16. Oktober 2011
Beiträge: 12801
|
ubuntu--anfaenger schrieb: Das ist jetzt viel Input für mich, wird Zeit in Anspruch nehmen..werde die Threads zu gegebener Zeit abarbeiten.
Gut! Dann haben wir Dich ja beschäftigt. ☺
rklm schrieb
Unter 100 sind sie ja recht häufig, aber ich bin mir nicht sicher, wie sich das unter größeren Zahlen verhält.
Ich glaube das ist eines der wichtigsten noch ungelösten Rätsel, wenn Du das Beschreiben kannst, ist glaube ich 1000000$ Preisgeld drauf
Es gibt da schon Abschätzungen durch den Primzahlsatz. Wenn man mit x / ln(x) rechnet, nimmt die Anzahl pro Intervall ab: | irb(main):022:0> f(2000) - f(1000)
=> 118.36182254681981
irb(main):023:0> f(12000) - f(11000)
=> 95.5156075168361
irb(main):024:0> f(102000) - f(101000)
=> 79.221751328565
irb(main):025:0> f(1002000) - f(1001000)
=> 67.1364846182696
|
Und generell sind das ziemlich wenige Primzahlen in einem 1000er-Intervall, was dafür spricht, dass ein Array eine nicht sehr speichereffiziente Datenstruktur für Primzahlen ist.
Btw. da gibt es bestimmt auch eine Datenstruktur in der Stdlib oder bei boost für BitSets - und die ist garantiert effizienter als ein Array von bool.
Mal eine Anfänger Gegenfrage, denkst Du das das an dem bool Array liegt, da es keinen Unterschied macht ob ich int oder unsigned long long verwende? bei 8300000 gibt der alle Primzahlen aus, bei 8400000 (sowohl bei int wie auch bei unsigned long long)segmentation fault
Ich habe es nicht im Detail studiert und habe auch nicht die alternativen Programmversionen gesehen, aber das ist wahrscheinlich, denn die Integer werden ja nur als Index in das bool-Array benutzt. Du bekommst das aber ziemlich schnell raus, wo der Segfault geschmissen wird: entweder schmeißt Du den Debugger an oder zu fügst einfach eine Ausgabe vor und nach dem Anlegen des Arrays ein.
Ich hatte mir schonmal die boost Bibliotheken runtergeladen..ich brauchte das mal für regexp, ich denke aber das ist zu hoch für mich, solange ich die Grundlagen im Programmieren nicht behersche sollte ich eher denke ich bei einfachen Dingen bleiben.
Naja, ein Bitset ist eigentlich eine recht einfache Datenstruktur. Du kannst das tatsächlich an Stelle Deines bool-Arrays verwenden und musst außer dem memset() nix ändern. Übrigens, so etwas macht man nicht: | if(prim[p]==true){ // wenn p true
|
Einen Bool vergleicht man nicht mit einem Bool. In diesem Fall funktioniert das vielleicht noch unfallfrei, aber spätestens in Sprachen wie C, wo früher zumindest ein int als bool benutzt wurde und es exakt einen Wert für falsch (0 nämlich), aber beliebig viele für true gibt (alles andere). Da geht dann ein Vergleich von irgendeinem Wahr-Wert mit einem anderne Wahr-Wert schief. Es ist einfach überflüssig - die boolsche Logik bietet alles, was man braucht. Du brauchst nur das "==true" zu entfernen.
|
ubuntu--anfaenger
(Themenstarter)
Anmeldungsdatum: 12. Oktober 2013
Beiträge: 1088
Wohnort: Belgien
|
rklm schrieb
Du bekommst das aber ziemlich schnell raus, wo der Segfault geschmissen wird: entweder schmeißt Du den Debugger an
Program received signal SIGSEGV, Segmentation fault.
0x00005555555552be in sieb (n=8400000) at sieb1.cc:8
8 bool prim[n+1]; // +1 da Array 0
Ja sieht so aus, danke.
Übrigens, so etwas macht man nicht:
Ok hab ich verstanden, hab ich raus. Ich schau dann mal ob ich ab hier alleine weiterkomme, es ist immer eine Zeitfrage und Unwahrscheinlich viel zu lesen.
|