Goldbach Vermutung

for(unsigned int a=2; a<i; a++)

Hier gibts noch nen Faktor 2 zu holen, weil es reicht bis einschließlich i/2 zu testen.

volkard schrieb:

for (unsigned int i=2; i*i<=number; i++)
500000 time: 1422 ms

Obacht mit dem Wertebereich. 500000^2 passt schon nicht mehr in eine 32 Bit Variable!

Mr X

i*i<=number ist eine intelligente Idee, die Fließkommaoperation sqrt() loszuwerden, schöner Hinweis (wenn man die 32-bit-Grenze dabei nicht vergisst. Problem ist halt, dass die Zahlen explodieren...).

Mr X schrieb:

i*i<=number ist eine intelligente Idee, die Fließkommaoperation sqrt() loszuwerden, schöner Hinweis

Vermutlich will man eher eine effiziente Version davon: https://en.wikipedia.org/wiki/Integer_square_root

volkard

sebi707 schrieb:

volkard schrieb:
for (unsigned int i=2; i*i<=number; i++)
500000 time: 1422 ms
Obacht mit dem Wertebereich. 500000^2 passt schon nicht mehr in eine 32 Bit Variable!

Richtig. Man muss aufpassen wie ein Luchs.

Aber kann i denn in die Gegend von number kommen? Nöö, gell? Hab den Luchs erschossen! *freu* *hüpf*

Bengo

Für Zahlen kleiner als 341550071728321 ist sicher, dass es reicht zu prüfen ob die starke Pseudoprimzahlen sind zur Basis 2,3,6,7,9,11,13,17. Ich denke das geht recht schnell und kann dein Programm enorm beschleunigen.

Nachtrag: Für kleiner als 25326001, reichen 2,3,5.

volkard schrieb:

Aber kann i denn in die Gegend von number kommen? Nöö, gell? Hab den Luchs erschossen! *freu* *hüpf*

Ich merks gerade. Hätte mir auch eher auffallen können...

Erhard Henkes

#include <iostream>
#include <limits>
#include <ctime>
#include <cstdint>

using namespace std;

void wait()
{
    cin.clear();
    cin.ignore(numeric_limits<streamsize>::max(), '\n');
    cin.get();
}

bool IsPrime(uint64_t number)
{
    if(number<2)    return false;
    if(number==2)   return true;
    if(number%2==0) return false;

    for(uint64_t i=3; i*i<=number; i+=2)
    {
        if(number%i == 0) return false;
    }
    return true;
}

bool ZweiPrimzahlenGefunden(uint64_t i)
{
    for(uint64_t a=2; a<i; a++)
    {
        if(IsPrime(a) && IsPrime(i-a))
            return true;
    }
    return false;
}

int main()
{
    clock_t zeit1 , zeit2;
    zeit1 = clock();

    for(uint64_t i=6; i<=5000000; i+=2)
    {
        if(!ZweiPrimzahlenGefunden(i))
            cout << "Gegenbeweis gefunden für folgende Zahl: " << i << endl;

        if (i%100000 == 0)
        {
                zeit2 = clock();
                cout << i << "\ttime: " << 1000 * (zeit2-zeit1) / CLOCKS_PER_SEC << " ms" << endl;
        }
    }

    wait();
 }

mit -O3 und 64 bit: 5000000 time: 18652 ms

Bengo

Ich denke du kannst noch richtig Speed raushohlen, wenn du dir die Primzahlen vorher erstellst.

Das hier könnte ein Construtor für eine Klasse Primes werden, die einen public std::vector mit den Primzahlen hält, über den kannst du dann immer iterieren.

Primes::Primes(int up_to) {
    this->primes.push_back(2);
    bool abbruch = false;
    for(int i = 3; i <= up_to; ++i) {
        for ( auto &p : this->primes ) {
            if (i%p == 0) {
                abbruch = true;
                break;
            }
        }
        if (abbruch == true) {
            abbruch = false;
        } else {
            this->primes.push_back(i);
        }
    }
}

Erhard Henkes

ja, das müsste man aber dann schon bis 18.446.744.073.709.551.616 machen für uint64_t. Gewaltiges Array.

Mr X

Erhard Henkes schrieb:

ja, das müsste man aber dann schon bis 18.446.744.073.709.551.616 machen für uint64_t. Gewaltiges Array.

Naja, zum Glück sind nur eine Minderheit der Zahlen bis dahin Primzahlen, sodass der Speicherbedarf doch ein erhebliches Stück geringer ist.

Bengo

Mr X schrieb:

Erhard Henkes schrieb:

ja, das müsste man aber dann schon bis 18.446.744.073.709.551.616 machen für uint64_t. Gewaltiges Array.

Naja, zum Glück sind nur eine Minderheit der Zahlen bis dahin Primzahlen, sodass der Speicherbedarf doch ein erhebliches Stück geringer ist.

mmh, ich würde sagen immernoch mehr als mein Computer verkraftet.
Es sind etwa 18.446.744.073.709.551.616/log(18.446.744.073.709.551.616)
(Ich meine den natürlichen log)
Und das sind immernoch verdammt viele.

Ok also bei so großen Zahlen würd ich trotzdem den Test mit den Pseudoprimzahlen machen, der ist einfach und schnell. Wird glaube auch bei vielen RSA implementierungen verwendet.

Und du kannst in der Schleife von ZweiPrimzahlenGefunden, wenigstens mit a = a + 2 interieren

Bengo

Die Idee hinter den Pseudoprimzahlen ist folgende:

Es gilt a^{p-1} \equiv 1 \mod p (kleiner Fermat) ggT(a,p)=1;(Beweis: betrachte die Gruppe der Restklassen modulo p ohne 0 mit der Multiplikation als verknüpfung, diese Gruppe hat die Ordung p-1, daher gilt für jedes a: a^(p-1)=1)

Umgekehrt kann man aber auch schließen, wenn für diese Kongruenz für eine Zahl n erfüllt ist, ist sie auch prim. Das stimmt leider nicht ganz, aber wenn es für die Zahlen a=2,3,5,7,11,13,17 gilt dann ist sie sehr wahrscheinnlich prim, und wenn kleiner als die Grenze die ich schon mal angegeben habe auch zu 100%. Kann man beweisen wenn man einfach mal überprüft, welche Zahlen bei 2 Pseudoprimzahlen sind, dann bei 3 und so weiter. Die kleinste gemeinsame Zahl ist dann schon verdammt groß.
Da sich $a^{p-1}$ eher nicht ausrechnen lässt, muss man das iterativ machen und immer mal wieder mod p rechnen.

volkard

Bengo schrieb:

Ich denke du kannst noch richtig Speed raushohlen, wenn du dir die Primzahlen vorher erstellst.

Das hier könnte ein Construtor für eine Klasse Primes werden, die einen public std::vector mit den Primzahlen hält, über den kannst du dann immer iterieren.
Primes::Primes(int up_to) {
    this->primes.push_back(2);
    bool abbruch = false;
    for(int i = 3; i <= up_to; ++i) {
        for ( auto &p : this->primes ) {
            if (i%p == 0) {
                abbruch = true;
                break;
            }
        }
        if (abbruch == true) {
            abbruch = false;
        } else {
            this->primes.push_back(i);
        }
    }
}

abbruch ist eine "künstliche variable", die nur dazu da ist, das exit-pfeilchen aus dem struktogramnm wegzumachen. was hatte onkel volkard vorhin darüber geschrieben?

volkard

Mr X schrieb:

Erhard Henkes schrieb:

ja, das müsste man aber dann schon bis 18.446.744.073.709.551.616 machen für uint64_t. Gewaltiges Array.

Naja, zum Glück sind nur eine Minderheit der Zahlen bis dahin Primzahlen, sodass der Speicherbedarf doch ein erhebliches Stück geringer ist.

Ein Trugschluss!

Sagen wir mal, man will eine Primzahlenliste bis 2^n speichern und hat als Alternativen
A einen vector<n-bittiger-int>(wo man nur die primzahlen speichert) oder
B einen vector<bool>(wo man 2^n bits drin hat und nur die primzahlen sind 1).

Was ist teuerer? Und vor allem, wie verhält es sich, wenn n immer größer wird?

Primzahlensatz: Zwischen 0 und x gibt es ungefähr x/ln(x) Primzahlen.

B braucht 2^n Bits.
A braucht n*(2^n)/ln(2n) = n*(2^n)/(ln(2)*n) = 2^n/ln(2) Bits.
B braucht 69% von A.

Überraschung, der Verbrauch von B wird nie "erhebliches Stück geringer" sein.

volkard

Bengo schrieb:

Für Zahlen kleiner als 341550071728321 ist sicher, dass es reicht zu prüfen ob die starke Pseudoprimzahlen sind zur Basis 2,3,6,7,9,11,13,17. Ich denke das geht recht schnell und kann dein Programm enorm beschleunigen.

Nachtrag: Für kleiner als 25326001, reichen 2,3,5.

evtl haste Spaß daran: https://www.c-plusplus.net/forum/67513-full
Das führt aber zu weit für die Zielgruppe von Ehrhard fürchte ich.

Erhard Henkes

du kannst in der Schleife von ZweiPrimzahlenGefunden, wenigstens mit a = a + 2 iterieren

bool ZweiPrimzahlenGefunden(uint64_t i)
{
    uint64_t a=2;

    if(IsPrime(a) && IsPrime(i-a))
        return true;

    for(a=3; a<i; a+=2)
    {
        if(IsPrime(a) && IsPrime(i-a))
            return true;
    }
    return false;
}

Gemessene Zeitersparnis (6 bis 5.000.000): 1,93% DANKE!

Wie wichtig Reihenfolgen sind, sieht man daran, wenn man die Anordnung

IsPrime(i-a) && IsPrime(a)

ausprobiert. Dann braucht es etwa 65% mehr Zeit.

Mr X

Den Test mit a=2 kann man auch sein lassen; 2 + irgendeine andere Primzahl ergibt eine ungerade Zahl, aber die Goldbachsche Vermutung betrifft nur gerade Zahlen. Für 4 ergäbe es zwar dann einen angeblichen Gegenbeweis, allerdings startet dein Test ja eh erst bei 6.

Erhard Henkes

bool ZweiPrimzahlenGefunden(uint64_t i)
{
    for(uint64_t a=3; a<i; a+=2)
    {
        if(IsPrime(a) && IsPrime(i-a))
            return true;
    }
    return false;
}

Gute Idee. Das bringt 7% Zeitersparnis.

Interessant wird es aber erst bei hohen Zahlen (mit -O3):
Intel i5-2520M 2,5 GHz, 8 GB RAM, 64 bit

1000000000000000000 time: 4836 ms
1000000000000000100 time: 249455 ms
1000000000000000200 time: 560991 ms

Zur Sicherheit der aktuelle Code:

#include <iostream>
#include <limits>
#include <ctime>
#include <cstdint>

using namespace std;

void wait()
{
    cin.clear();
    cin.ignore(numeric_limits<streamsize>::max(), '\n');
    cin.get();
}

bool IsPrime(uint64_t number)
{
    if(number<2)    return false;
    if(number==2)   return true;
    if(number%2==0) return false;

    for(uint64_t i=3; i*i<=number; i+=2)
    {
        if(number%i == 0) return false;
    }
    return true;
}

bool ZweiPrimzahlenGefunden(uint64_t i)
{
    for(uint64_t a=3; a<i; a+=2)
    {
        if(IsPrime(a) && IsPrime(i-a))
            return true;
    }
    return false;
}

int main()
{
    clock_t zeit1 , zeit2;
    zeit1 = clock();

    for(uint64_t i=1000000000000000000; i<=2000000000000000000; i+=2)
    {
        if(!ZweiPrimzahlenGefunden(i))
            cout << "Gegenbeweis gefunden für folgende Zahl: " << i << endl;

        if (i%100 == 0)
        {
                zeit2 = clock();
                cout << i << "\ttime: " << 1000 * (zeit2-zeit1) / CLOCKS_PER_SEC << " ms" << endl;
        }
    }

    wait();
}

oder:

18400000000000000000 time: 27753 ms
18400000000000000010 time: 168974 ms
18400000000000000020 time: 308288 ms
18400000000000000030 time: 446579 ms
18400000000000000040 time: 587249 ms
18400000000000000050 time: 741313 ms

int main()
{
    clock_t zeit1 , zeit2;
    zeit1 = clock();

    for(uint64_t i=18400000000000000000; i<=18446744073709551615; i+=2)
    {
        if(!ZweiPrimzahlenGefunden(i))
            cout << "Gegenbeweis gefunden für folgende Zahl: " << i << endl;

        if (i%10 == 0)
        {
                zeit2 = clock();
                cout << i << "\ttime: " << 1000 * (zeit2-zeit1) / CLOCKS_PER_SEC << " ms" << endl;
        }
    }

    wait();
}

Welche Bibliothek sollte man für Zahlen größer 2^64 - 1 einsetzen?

Erhard Henkes

Ein erweitertes Thema: Zahl der Goldbach-Zerlegungen:

99999000 Anzahl Primzahlenpaare: 599905
99999000 time: 111418 ms
99999002 Anzahl Primzahlenpaare: 219708
99999004 Anzahl Primzahlenpaare: 261948
99999006 Anzahl Primzahlenpaare: 437521
99999008 Anzahl Primzahlenpaare: 222566
99999010 Anzahl Primzahlenpaare: 291523
99999010 time: 591165 ms

Ab einer Milliarde wird es sehr zeitaufwändig (ca. 1h pro Zahl):

999999000 Anzahl Primzahlenpaare: 6797548
999999000 time: 3201129 ms

https://upload.wikimedia.org/wikipedia/commons/thumb/7/79/Goldbach200000.png/1024px-Goldbach200000.png <== Interessantes Muster.
Da wird es ab 100 Millionen am PC hakelig und Beschleunigung ist gefragt.

Kann man die AKS- oder Bernstein-Methodik hier vernünftig einsetzen? http://yves.gallot.pagesperso-orange.fr/src/aks.html