3. Programmoptimierung

Programmoptimierung

  • S

    Hi Leutz

    ich mache derzeitig die aufgaben von projecteuler.net aber ich hab ne aufgabe die dauert etwas lange...

    wie kann ich folgenden code optimieren?

    void Problem()
{
	BigInteger a(28433);
	BigInteger x(2); 
	BigInteger y(7830457);
	BigInteger result;
	BigInteger eins(1);
	result = a*pow(x, y)+eins;

	cout << result << endl;
}

BigInteger pow(BigInteger const& x, BigInteger const& y)
{
	BigInteger res = 1;
	for(BigInteger i = 0; i < y; ++i)
	{
		res *= x;
	}
	return res;
}

    (die stylistischens achen könnt ihr mal aussen vor lassen...)

    BigInteger ist eine Bilbliothek die mit grossen integern bzw unsigneds rechenn kann...
    hab ich mir irgendwo ausem netz gesaugt

    aber kann ich das hier etwas vershcnellern?
    (hauptproblem ist pow)

    zum verständnis:
    die zahl 28433 * 2^7830457 ist eine primzahl
    sie soll eifnach nur errechnet werden

    eigener ansatz:
    ich hab mir gedacht man könnte (mindestens einen teil der pow funktion) in einer formel zusammen fassen...
    so anch dem prinzip der geometrischen (oder halt adneren) reihen...

    0
  • J

    aber kann ich das hier etwas vershcnellern?
    (hauptproblem ist pow)

    Ja, Stichwort "square & multiply"

    zum verständnis:
    die zahl 28433 * 2^7830457 ist eine primzahl
    sie soll eifnach nur errechnet werden

    Das hilft mir nicht beim Verständnis... 28433* 2^7830457 ist also eine Primzahl mit den Teilern 28433, 2, 4, 8, ...?

    Da kommt doch bestimmt noch irgendwo ein modulo ins spiel, oder? 😉

    0
  • S

    Jester schrieb:

    Ja, Stichwort "square & multiply"

    das heist?

    Jester schrieb:

    Das hilft mir nicht beim Verständnis... 28433* 2^7830457 ist also eine Primzahl mit den Teilern 28433, 2, 4, 8, ...?

    Da kommt doch bestimmt noch irgendwo ein modulo ins spiel, oder? 😉

    nein, es ist bewiesen dass das eine primzahl ist
    gib die zahl mal bei onkel goggle ein 😉

    ich möchte sie nur ausgerechnet haben, aber mein pc (quadcore 2.5 ghz, 2gb ram) hat einige studnen dran rumgerechent (7 oder 8 stunden) bis ich dann abgebrochen hab weil ichd as gefühl hatte dass er hängt

    problem bei der bigint library ist dass man sich nicht den aktuellen wert im debug modus angeben lassen kann wie bei den standart datentypen, sosnt wüsst ich ja was sache wäre...

    0
  • J

    Skym0sh0 schrieb:

    Jester schrieb:

    Ja, Stichwort "square & multiply"

    das heist?

    Das heißt, dass du "square & multiply" mit der maus markieren sollst, Strg+C drücken, in deinem Browser www.google.de in die adresszeile eingeben sollst und mit enter bestätigen, anschließend per klick in die sucheingabe den fokus dorthin geben sollst und schließlich mit strg+V nebst Bestätigung durch Enter nachlesen solltest wie man das schneller macht.

    Jester schrieb:

    nein, es ist bewiesen dass das eine primzahl ist
    gib die zahl mal bei onkel goggle ein 😉

    Das was Du da angegeben hast ist definitiv keine Primzahl, wie ich soeben durch die Angabe einiger nichttrivialer Teiler bewiesen habe. Allerdings steht im Code ja noch ein +1 dabei, das hast du im text unterschlagen.

    0
  • S

    xD jop hab ich auch grad gemerkt
    aber war zu faul noch zu editen

    ok ich gucke mal nach quadrieren und multiplizieren

    0
  • J

    Btw hast Du einen sehr relevanten Teil der Aufgabenstellung unterschlagen/übersehen... ich befürchte selbst mit dem Trick wird das noch sehr sehr lange brauchen.

    0
  • S

    ok 😃

    ich brauche die letzten 10 stellen der zahl...

    mehr nicht

    0
  • J

    Dann geht's nämlich auch ohne BigInteger. 🙂

    0
  • N

    Dann brauchst du auch nicht mit BigIntegers herumfuhrwerken.
    Da du ohnehin nur die letzten Stellen brauchst, ist es nicht nötig, die ganzen Stellen davor zu berechnen. Damit könnte das ganze in einem Wimpernschlag erledigt werden. Wobei das auch zutreffen würde, wenn du alle Stellen z.B. mit GMP ausrechnest.

    0
  • S

    also ich lasse den jetzt mal rechnen...

    aber ne idee wie ich das mit c++ standart mitteln schaffen könnte - kA

    0
  • F

    Die beste Primzahl ist eh folgende:

    4856507896573978293098418946942861377074420873513579240196520736 6869851340104723744696879743992611751097377770102744752804905883 1384037549709987909653955227011712157025974666993240226834596619 6060348517424977358468518855674570257125474999648219418465571008 4119086259716947970799152004866709975923596061320725973797993618 8606316914473588300245336972781813914797955513399949394882899846 9178361001825978901031601961835034344895687053845208538045842415 6548248893338047475871128339598968522325446084089711197712769412 0795862440547161321005006459820176961771809478113622002723448272 2493232595472346880029277764979061481298404283457201463489685471 6908235473783566197218622496943162271666393905543024156473292485 5248991225739466548627140482117138124388217717602984125524464744 5055834628144883356319027253195904392838737640739168912579240550 1562088978716337599910788708490815909754801928576845198859630532 3823490558092032999603234471140776019847163531161713078576084862 2363702835701049612595681846785965333100770179916146744725492728 3348691600064758591746278121269007351830924153010630289329566584 3662000800476778967984382090797619859493646309380586336721469695 9750279687712057249966669805614533820741203159337703099491527469 1835659376210222006812679827344576093802030447912277498091795593 8387121000588766689258448700470772552497060444652127130404321182 610103591186476662963858495087448497373476861420880529443

    Denn damit kannst DVDs entschlüsseln. 😉

    Achja:

    #include <iostream>

using namespace std;

int main(int argc, char *argv[]){
    long long a = 7830457;

    for (int i = 0; i < 28433; i++){
	a = (a * 2) % 10000000000LL;
    }
    ++a;

    cout << a << endl;   
}
    0
  • S

    nö ist falsch

    hab auch noch 1 am ende dazu addiert
    und die schleife auch mal einen schritt weiterlaufen lassen

    aber hat beides nix gebracht

    0
  • F

    Hast du die Primzahl denn irgendwo? Google weigert sich. 😉

    0
  • S

    -.-'

    die suche ich ja, bei google hab ich auch schon gesucht aber da steht nru überall dass sie als neue primzahl entdeckt wurde, aber ausgeschrieben gabs sie nirgens

    bin sie grad am errechnen(mit dem square&multiply), dauert aber lange -.-

    0
  • F

    Woher weißt du dann, das meine Lösung falsch ist?

    0
  • C
    Mod

    square&multiply geht nicht so ganz direkt, weil wir hier (bei 10stelligem gefordertem Ergebnis mit 20stelligen Zwischenergebnissen zu tun haben, und die passen nicht in ein 64bit-Integer).
    Schnell dahergeschrieben ohne Anspruch auf höchste Optimierung

    #include <iostream>
#include <utility>

using namespace std;

typedef unsigned long long u32;
typedef unsigned long long u64;
typedef pair<u32,u32> x_pair;

x_pair mul(const x_pair& lhs, const x_pair& rhs)
{
    u64 x1 = u64(lhs.second) * rhs.second;
    u64 x2 = u64(lhs.first) * rhs.second + u64(lhs.second) * rhs.first;
    return x_pair( ( x2 + x1 / 100000 ) % 100000, x1 % 100000 );
}

u64 pow2(unsigned exp)
{
    x_pair result( 0, exp % 2 + 1 );
    for ( x_pair x( 0, 2 ); exp /= 2; )
    {
        x = mul( x, x );
        if ( exp % 2 )
            result = mul( result, x );
    }
    return result.first * 100000ull + result.second;
}

int main()
{
    cout << ( 28433 * pow2( 7830457 ) + 1 ) % 10000000000;
}

    Keine Ahnung, ob das Ergebnis stimmt.

    0
  • F

    Dein Ergebnis stimmt. Bei meiner Rechnung weiter oben habe ich nur die beiden Zahlen vertauscht. 😃

    0
Anmelden zum Antworten