[Info]
Aktuelle Zeit: Mo 22. Jan 2018, 05:19

Alle Zeiten sind UTC + 1 Stunde




Ein neues Thema erstellen Auf das Thema antworten  [ 16 Beiträge ]  Gehe zu Seite 1, 2  Nächste
Autor Nachricht
 Betreff des Beitrags: Laufzeit free() C
BeitragVerfasst: So 23. Aug 2015, 23:22 
Offline
Benutzeravatar

Registriert: Sa 11. Mai 2013, 15:31
Beiträge: 528
Wohnort: Bayern

Spezialgebiet: Knoten,"Hallo Wach Kaffee+",C Sockets
Schule/Uni/Arbeit: Gymnasium
Servus Miteinander
Ich bin gerade dabei für meine Facharbeit über die Implementierung von RSA grundlegende Mathematische Funktionen (Plus Minus Mal und Mod) für große Zahlen zu implementieren. Bei dem ersten Testlauf der Laufzeit hab ich eine 32 byte Zahl mit einer 24byte Zahl multipliziert. Erst mal hab ich mich gefreut dass 100 Multiplikationen in 0,5s geschafft wurden. Nach der ersten Freude kam der Schock dass ich mir wohl ein etwas größeres Speicherleck produziert hab. Also ein bisschen gesucht und 3 fehlend free() gefunden. Nachdem ich das geflickt hab hab ich nochmal de Laufzeit getestet. Plötzlich brauchten die 100 Multiplikationen 12s !!!!!!!. Hab das natürlich einige male ausprobiert.
Woher kommt das? Ist es normal dass free() so langsam ist oder kann so etwas von einem Fehler von mir kommen?
mfg ferrum
EDIT: Compiler ist MinGW in Code::Blocks unter linux ubuntu 12.04

_________________
I <3 0402
Real ist alles was warm wird.


Share on FacebookShare on Google+Share on Reddit
Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Laufzeit free() C
BeitragVerfasst: Mo 24. Aug 2015, 00:18 
Offline
Benutzeravatar

Registriert: Fr 28. Nov 2008, 20:55
Beiträge: 1309
Wohnort: Dresden

Spezialgebiet: Mikrocontroller und Co
Schule/Uni/Arbeit: TU Dresden
Das free sollte es nicht sein, das ist für gewöhnlich fast sofort geschehen (da wird ja nicht mehr gemacht als das der Kernel den Speicher wieder anders vergeben darf).

Wenn du deinen Code zeigst könnte man vielleicht genaueres sagen.

_________________
Meine NEUE WEBSEITE: (Programmieren, E-Tech. und Co): http://fthiessen.de
Mein Linux-Projekt: http://ossc.bplaced.de


Share on FacebookShare on Google+Share on Reddit
Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Laufzeit free() C
BeitragVerfasst: Mo 24. Aug 2015, 10:34 
Offline
Benutzeravatar

Registriert: Sa 11. Mai 2013, 15:31
Beiträge: 528
Wohnort: Bayern

Spezialgebiet: Knoten,"Hallo Wach Kaffee+",C Sockets
Schule/Uni/Arbeit: Gymnasium
Klar ist nur etwas mehr
Code:
#define BYTES unsigned char
#define BIGNUMBER struct BIGNUM



struct BIGNUM
{
    BYTES *zahl;
    int length;
};


Code:
BIGNUMBER *Sum( BIGNUMBER *Summand1 , BIGNUMBER *Summand2)
{
   
    BIGNUMBER Remember,*Summandbig,*Summandsmal,*Summe ;
    Summe=malloc(sizeof(BIGNUMBER));
    Remember.zahl=malloc(sizeof(BYTES));
    Remember.length=1;
    if((*Summand1).length<(*Summand2).length)
    {
        Summandbig=Summand2;
        Summandsmal=Summand1;
    }
    else
    {
        Summandbig=Summand1;
        Summandsmal=Summand2;
    }
    (*Summe).zahl= (BYTES*)malloc(((*Summandbig).length+1)*sizeof(BYTES));
    (*Summe).length=(*Summandbig).length+1;
    int i=0,b=0;
    while(i<((*Summandsmal).length))
    {
        b=0;
        while(b<8)
        {
            if(BitTest((*Summandbig).zahl[i],b)==1)
            {
                int n=0,z=0;
                while(n<(Remember.length)&&z==0)
                {
                    int b1=0;
                    while(b1<8)
                    {

                        if(BitTest(Remember.zahl[n],b1)==0)
                        {
                            SetBit(&Remember.zahl[n],b1);
                            z=1;
                            break;
                        }
                        else
                        {
                            DeleteBit(&Remember.zahl[n],b1);
                        }
                        b1++;
                    }
                    n++;
                }
                if(z==0)
                {
                    Remember.zahl=(BYTES*)realloc(Remember.zahl,(Remember.length+1)*sizeof(BYTES));
                    Remember.zahl[Remember.length]=1;
                    Remember.length++;
                }

            }

            if(BitTest((*Summandsmal).zahl[i],b)==1)
            {
                int n=0,z=0;
                while(n<(Remember.length)&&z==0)
                {
                    int b1=0;
                    while(b1<8)
                    {
                        if(BitTest(Remember.zahl[n],b1)==0)
                        {
                            SetBit(&Remember.zahl[n],b1);
                            z=1;
                            break;
                        }
                        else
                        {
                            DeleteBit(&Remember.zahl[n],b1);
                        }
                        b1++;
                    }
                    n++;
                }
                if(z==0)
                {
                    Remember.zahl=(BYTES*)realloc(Remember.zahl,(Remember.length+1)*sizeof(BYTES));
                    Remember.zahl[Remember.length]=1;
                    Remember.length++;
                }
            }
            (*Summe).zahl[i]=(*Summe).zahl[i] | (BitTest(Remember.zahl[0],0)<<b);
            RightShift(&Remember);
            b++;
        }
        i++;
    }
    while(i<((*Summandbig).length))
    {
        b=0;
        while(b<8)
        {
            if(BitTest((*Summandbig).zahl[i],b)==1)
            {
                int n=0,z=0;
                while(n<(Remember.length)&&z==0)
                {
                    int b1=0;
                    while(b1<8)
                    {
                        if(BitTest(Remember.zahl[n],b1)==0)
                        {
                            SetBit(&Remember.zahl[n],b1);
                            z=1;
                            break;
                        }
                        else
                        {
                            DeleteBit(&Remember.zahl[n],b1);
                        }
                        b1++;
                    }
                    n++;
                }
                if(z==0)
                {
                    Remember.zahl=(BYTES*)realloc(&Remember.zahl,(Remember.length+1)*sizeof(BYTES));
                    Remember.zahl[Remember.length]=1;
                    Remember.length++;
                }

            }
            (*Summe).zahl[i]=(*Summe).zahl[i] | (BitTest(Remember.zahl[0],0)<<b);
            RightShift(&Remember);
            b++;
        }
        i++;
    }
    while(i<((*Summe).length))
    {
        b=0;
        while(b<8)
        {
            (*Summe).zahl[i]=(*Summe).zahl[i] | (BitTest(Remember.zahl[0],0)<<b);
            RightShift(&Remember);
            b++;
        }
        i++;
    }

    free(Remember.zahl);//wenn auskommentiert schnellere laufzeit
    CutNumber(Summe);
    return Summe;
}


BIGNUMBER *Product( BIGNUMBER *Faktor1,  BIGNUMBER *Faktor2)
{
    BIGNUMBER Remember, *Product, *Faktorbig, *Faktorsmal;
    Product=malloc(sizeof(BIGNUMBER));
    (*Product).zahl=malloc(((*Faktor1).length+(*Faktor2).length+1)*sizeof(BYTES));
    if((*Faktor1).length<(*Faktor2).length)
    {
        Faktorbig=Faktor2;
        Faktorsmal=Faktor1;
    }
    else
    {
        Faktorbig=Faktor1;
        Faktorsmal=Faktor2;
    }
    Remember.zahl=malloc((*Faktorbig).length*sizeof(BYTES));
    Remember.length=(*Faktorbig).length;
    int i=0 ,b;
    while(i<(*Faktorbig).length)
    {
        Remember.zahl[i]=(*Faktorbig).zahl[i];
        i++;
    }
    i=0;
    while(i<(*Faktorsmal).length)
    {
        b=0;
        while(b<8)
        {
            if(BitTest((*Faktorsmal).zahl[i],b)==1)
            {
                BIGNUMBER *Producttemp;
                Producttemp=Sum(Product,&Remember);
                free((*Product).zahl);
                free(Product);
                Product=Producttemp;
            }
            LeftShift(&Remember);
            b++;
        }
        i++;
    }
    CutNumber(Product);
    free(Remember.zahl);//wenn auskommentiert schnellere laufzeit
    return Product;
}


BYTES BitTest(BYTES byte,unsigned char bit)
{
    BYTES a =(byte<<(7-bit));
    return a>>7;
}
void SetBit(BYTES *byte,unsigned char bit)
{
    BYTES bitpos= 0x01;
    *byte =(*byte|(bitpos<<bit));
}
void DeleteBit(BYTES *byte,unsigned char bit)
{
    BYTES bitpos= 0x01;
    *byte =(*byte & ((~bitpos)<<bit));
}
void LeftShift(BIGNUMBER *num)
{
    int i=0;
    BYTES bit=0;
    while(i<(*num).length)
    {
        BYTES workkopy;
        workkopy=(*num).zahl[i];
        (*num).zahl[i]=(*num).zahl[i]<<1;
        (*num).zahl[i]=(*num).zahl[i] | bit;
        bit=workkopy>>7;
        i++;
    }
    if(bit==1)
    {
        (*num).zahl=realloc((*num).zahl,((*num).length+1)*sizeof(BYTES));
        (*num).zahl[(*num).length]=1;
        (*num).length++;
    }
}
void RightShift(BIGNUMBER *num)
{
    int i=(*num).length-1;
    BYTES bit=0;
    while(i>=0)
    {
        BYTES workkopy;
        workkopy=(*num).zahl[i];
        (*num).zahl[i]=(*num).zahl[i]>>1;
        (*num).zahl[i]=(*num).zahl[i] | bit;
        bit=workkopy<<7;
        i--;
    }
    if(((*num).zahl[(*num).length-1]==0)&&((*num).length>1))
    {
        (*num).zahl=(BYTES*)realloc((*num).zahl,((*num).length-1)*sizeof(BYTES));
        (*num).length--;
    }

}
void CutNumber(BIGNUMBER *num)
{
    int i=(*num).length-1;
    while(i>0)
    {
        if((*num).zahl[i]==0)
        {
            (*num).zahl=(BYTES*)realloc((*num).zahl,i*sizeof(BYTES));
            (*num).length--;
        }
        else
        {
            break;
        }
        i--;
    }
}

_________________
I <3 0402
Real ist alles was warm wird.


Share on FacebookShare on Google+Share on Reddit
Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Laufzeit free() C
BeitragVerfasst: Sa 29. Aug 2015, 21:27 
Offline
Wiki-Crew
Benutzeravatar

Registriert: Sa 29. Sep 2007, 15:29
Beiträge: 1108

Spezialgebiet: Dinge, Gründe und Sachlagen
Hallo,
darfst du eigentlich libgmpverwenden?

Und was genau machst du mit MinGW? Läuft es unter Wine?

Bonustipp: Stackallocation ist wohl bei vielen Durchläufen nen Tick schneller

_________________
~jwacalex



Zur Lage des Forums: "You're a nut! You're crazy in the coconut! What does that mean? That boy needs therapy"

Der Grund für meine Beiträge hier


Share on FacebookShare on Google+Share on Reddit
Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Laufzeit free() C
BeitragVerfasst: Sa 29. Aug 2015, 21:59 
Offline
Benutzeravatar

Registriert: Sa 11. Mai 2013, 15:31
Beiträge: 528
Wohnort: Bayern

Spezialgebiet: Knoten,"Hallo Wach Kaffee+",C Sockets
Schule/Uni/Arbeit: Gymnasium
Ok Compiler bin ich etwas durcheinander gekommen ich muss das ganze einmal für windoooooof compilen da ist es MinGW und ich arbeite unter Linux mit GNU Gcc
Ein nennenswerter teil meiner Facharbeit ist leider über die Implementierung von Großen Zahlen deswegen ist so was wie libgmp nur die letzte Notlösung wenn wirklich gar nichts geht.
Das Problem mit free() hab ich mittlerweile auf welche Art auch immer in den griff bekommen. Das Problem ist wohl eher dass mein Algorithmus zu ineffizient ist deswegen muss ich die Komplette Multiplikation nochmal mit einem anderen Algorithmus implementieren (40 fach höhere laufzeit). Aber danke für die Hilfe.

_________________
I <3 0402
Real ist alles was warm wird.


Share on FacebookShare on Google+Share on Reddit
Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Laufzeit free() C
BeitragVerfasst: Sa 29. Aug 2015, 22:34 
Offline
Wiki-Crew
Benutzeravatar

Registriert: Sa 29. Sep 2007, 15:29
Beiträge: 1108

Spezialgebiet: Dinge, Gründe und Sachlagen
Eine kleine dumme Idee von Döme und mir (powered by pfeffi): Hast du schon einen Map-Reduce-Ansatz probiert.
Angenommen ich multipliziere 1234568789 mit 123. Dann mache ich drei Workers:
- 1x123456789
- 2x123456789
- 3x123456789

und lege das Egebnis jeweils auf den Threadstorage und shiften um die Zehnerpotenz. Der Hauptthread macht immer wenn ein Ergebnis vorliegt ein Reduce Sum für die Teilergebnisse.

Ich hoffe du versteht was wir meinen

_________________
~jwacalex



Zur Lage des Forums: "You're a nut! You're crazy in the coconut! What does that mean? That boy needs therapy"

Der Grund für meine Beiträge hier


Share on FacebookShare on Google+Share on Reddit
Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Laufzeit free() C
BeitragVerfasst: Mo 31. Aug 2015, 21:12 
Offline

Registriert: Mo 7. Feb 2011, 23:24
Beiträge: 2349
Wohnort: Aachen

Schule/Uni/Arbeit: Student/Elektrotechnik
So wie ich das sehe zerlegst du deine Zahl in einzelne Bytes und gehst dann Byte für Byte und Bit für Bit durch, oder?
Auf den ersten Blick hin kannst du auf jeden Fall noch ein bisschen verbessern.
1. Wenn du mit malloc einen Haufen bytes (oder ein Stuct) reservierst liegen die auch alle hintereinander. Heißt wenn byte 1 die Adresse 0xA2 hat hat byte 2 die Adresse 0xA3...
Anstatt über den Array-Operator kann man also auch direkt mathematisch daran gehen. 7. Zahl in einem int Array wäre z.B. über *(zahl+4*7) zu erreichen.

Aus der Bedingung das alle bytes des Structs hintereinander liegen ergibt sich ein Problem für dich. Ich sehe da realloc. Im Fall das es größer oder kleiner wird, kann es sein das es nicht mehr in den Slot rein passt und dann wo anders hingeschoben werden muss, was einige Schreiboperationen verursacht.

Du kannst dir das realloc sparen wenn du dir vorher die paar Arbeitsvariablen anlegst, die eine ausreichende Größe haben um alle Arbeiten auch im Worst-Case durchzuführen. (Also größtmöglich ohne in einen Overflow zu laufen)
Um dir die Arbeit nicht komplett vorzusagen nur ein kleiner Tipp. Worst-Case für 8bit ist 0xFF*0xFF und das gibt 0xFE01, also 16bit.
Es gibt da aber eine Gesetzmäßigkeit bei ungleich langen Zahlen, viel Spaß ;)

Warum ist das besser als das andere: Speicher ist heutzutage kein Mangel mehr, Und selbst mit einer 64Byte-Zahl (max-Val unsigned: 1,34e154) nimmt der Programm-Host noch mehr Speicher in Anspruch als dein eigener Workspace.
Dafür ist es wichtig das deine Schleifen schnell sind, immerhin hast du bei Binärer Multiplikation O(n²). Und realloc hat halt auch als minimale Geschwindigkeit schon O(n), ich hoffe du verstehst meinen Punkt ;)

@jwacalex: Ich denke nicht das er Multithreaden soll / Kann (Immerhin nur C). Damit holt man sich eine Menge mehr Probleme ins Boot. Außerdem wusste ich noch gar nicht das Computer dezimal rechnen :trollface:


Share on FacebookShare on Google+Share on Reddit
Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Laufzeit free() C
BeitragVerfasst: Mo 31. Aug 2015, 22:25 
Offline
Benutzeravatar

Registriert: Sa 11. Mai 2013, 15:31
Beiträge: 528
Wohnort: Bayern

Spezialgebiet: Knoten,"Hallo Wach Kaffee+",C Sockets
Schule/Uni/Arbeit: Gymnasium
Das mit realloc ist mir bisher nicht so aufgefallen aber da hast du wahrscheinlich recht eine Speicherbereichsabschätzung mach ich z.T. schon allerdings nicht bei allen Variablen. Ich werde das mal Überall implementieren. Trotzdem denke ich dass O(n^2) zu langsam ist ich werde mal Versuchen Toom-3 O(n^1,47) zu implementieren der ist in dem für mich relevanten Bereich deutlich schneller und auch nicht so kompliziert dass er unverständlich wäre. Den Tipp mit dem Array werde ich mal ausprobieren. Das mit dem es gibt doch genug Speicher sehe ich etwas anders obwohl man viel hat verschwenden muss man ihn nicht.

_________________
I <3 0402
Real ist alles was warm wird.


Share on FacebookShare on Google+Share on Reddit
Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Laufzeit free() C
BeitragVerfasst: Do 3. Sep 2015, 15:33 
Offline
Benutzeravatar

Registriert: Sa 11. Mai 2013, 15:31
Beiträge: 528
Wohnort: Bayern

Spezialgebiet: Knoten,"Hallo Wach Kaffee+",C Sockets
Schule/Uni/Arbeit: Gymnasium
So hab jetzt realloc aus der summierfunktion gebannt und noch ein bisschen was verbessert ist jetzt ca. 3 mal schneller aber das ist noch viel zu wenig trotzdem vorerst mal danke für die Hilfe.

_________________
I <3 0402
Real ist alles was warm wird.


Share on FacebookShare on Google+Share on Reddit
Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Laufzeit free() C
BeitragVerfasst: Do 3. Sep 2015, 20:13 
Offline

Registriert: Mo 7. Feb 2011, 23:24
Beiträge: 2349
Wohnort: Aachen

Schule/Uni/Arbeit: Student/Elektrotechnik
Sehr schön das es ein bisschen was gebracht hat. Hast du deine SUM-Funktion denn schon verbessert? Ich denke da kann man auch nochmal ansetzen.
Wenn man die Zahlen vorher einmal analysiert (tatsächliche Länge kann man sich einige Durchläufe sparen)
Außerdem kann man das O(n) der Left- and Right-Shifts durch 1 ersetzen wenn man die Zahlen zumindest für den Prozess der Multiplikation als Queue darstellt und einen Zeiger-Offset einbaut. Dann muss man nur am Ende einmal die Variable auf die richtige Position bringen und ist fertig.
Ansonsten: Assembler an gewissen Stellen macht einiges schneller :P


Share on FacebookShare on Google+Share on Reddit
Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Laufzeit free() C
BeitragVerfasst: Fr 4. Sep 2015, 09:56 
Offline
Benutzeravatar

Registriert: Sa 11. Mai 2013, 15:31
Beiträge: 528
Wohnort: Bayern

Spezialgebiet: Knoten,"Hallo Wach Kaffee+",C Sockets
Schule/Uni/Arbeit: Gymnasium
Ja die Summ Funktion hab ich komplett umgeschrieben ich schreib den größeren Summanden jetzt erst mal in die endgültige summe rein und leg dann den anderen Summanden parallel dazu hin und schau mir den an und überall wo der 1 ist addiere ich an entsprechender stelle 1.

Aus dem Produkt habe ich den left Shift entfernt und die Addition manuell ausgeführt dadurch muss ich nicht lauter Nullen in der summe durchlaufen das hat nochmal 1,9 gebracht. Den toom-3 hab ich jetzt halb implementiert bin gespannt was der dann Laufzeit bringt. Assembler ist wohl eher die letzte alternative.

_________________
I <3 0402
Real ist alles was warm wird.


Share on FacebookShare on Google+Share on Reddit
Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Laufzeit free() C
BeitragVerfasst: Fr 11. Sep 2015, 16:54 
Offline
Benutzeravatar

Registriert: Sa 11. Mai 2013, 15:31
Beiträge: 528
Wohnort: Bayern

Spezialgebiet: Knoten,"Hallo Wach Kaffee+",C Sockets
Schule/Uni/Arbeit: Gymnasium
So mal eine kleine Rückmeldung von mir. Ich hab jetzt Toom-Cook 3 erfolgreich implementiert. Läuft auch ganz gut ist ca. um Faktor 35 Schneller (Für meine Vergleichsoperation 0x1FE^0x407B brauch ich jetzt statt 374s nur 11s). ABER! Das ist deutlich zu wenig für RSA muss eine 3Byte Zahl hoch 0x10001 Gerechnet werden und das in einigermaßen Akzeptabler Zeit. Geschätzt wäre noch etwa Faktor 1,2-1,5 möglich aber das ist immer noch zu wenig. Mit Toom-4 lässt sich das ganze bestenfalls noch um Faktor 1,6 Verbessern. Insgesamt wäre das im besten Falle Faktor 2,4.
Jetzt mal eine Frage an alle : Soll ich mir für eine W-Seminararbet die Mühe machen den sehr aufwändigen Schönhage-Strassen Algorithmus zu implementieren oder soll ich hinnehmen dass das Programm entweder extrem langsam oder Unsicher ist.

_________________
I <3 0402
Real ist alles was warm wird.


Share on FacebookShare on Google+Share on Reddit
Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Laufzeit free() C
BeitragVerfasst: Fr 11. Sep 2015, 20:13 
Offline
Benutzeravatar

Registriert: Di 19. Jun 2012, 23:02
Beiträge: 243
Wohnort: Erlangen

Spezialgebiet: Marxgeneratoren, Capbanks, alte Quacksalbereien
Schule/Uni/Arbeit: Stuß
Ohne jetzt Deinen Code zu kennen: Ich würde an deiner Stelle die jetzige Implementierung nochmal gründlich untersuchen, denn die Zeiten erscheinen schon arg länglich. Denke mal, du wirst etwas in dieser Art:

https://de.wikipedia.org/wiki/Bin%E4re_Exponentiation

anwenden, um die Potenzen auszurechnen.

Rein nach Bauchgefühl sollte sich das weit entfernt von 11 oder noch mehr Sekunden bewegen, weshalb ich vermute, dass noch irgendwo ein dicker Hund begraben liegt :-)

Zu "Schönhage-Strassen" habe ich nur noch im Hinterkopf, dass unser TheoInf-Prof damals meinte, dieser Algo habe so ein dickes "c" vor dem "O", dass er erst bei sehr sehr großen Problemen rentabel würde und daher kaum Praxisrelevanz besitze.

Grüße & viel Spaß noch beim Tüfteln!

EDIT: Das Forum mag keine URL mit "ä". Was ja eigentlich auch richtig ist.

_________________
BildDer Außerirdische mit Tentakelarmen hat es schwer, einen Lötkolben zu halten“ – Harald Lesch


Share on FacebookShare on Google+Share on Reddit
Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Laufzeit free() C
BeitragVerfasst: Sa 12. Sep 2015, 01:11 
Offline
Benutzeravatar

Registriert: Di 19. Jun 2012, 23:02
Beiträge: 243
Wohnort: Erlangen

Spezialgebiet: Marxgeneratoren, Capbanks, alte Quacksalbereien
Schule/Uni/Arbeit: Stuß
Du Seppel! Du hast mir meinen Freitagabend versaut!

Mein Tüftelgen wurde zwangsaktiviert. Aber nicht schuldig ühlen, denn ich bin ein Nerd, der nur jeden drölfzigsten Freitagabend fort geht und die restlichen am PC oder in der Bastelwerkstatt verbringt ;)

Also musste ich mal schnell einen Multiprecision-Multiplizierer in C basteln und deine Beispiele nachrechnen. Ergebnisse wurden mit diversen Onlinetools verifiziert. Da Wolfram ja inzwischen die Frechheit besitzt, für lange Zahlen Geld zu verlangen, half mir diverse Javascript-Dezimalrechner in Kombination mit ebenso langzahlentauglichen Hexkonvertern aus. Jedenfalls stimmte das Ergebnis bis auf die letzte Ziffer.

Methodik:

- Software:
Zum Multiplizieren: Schulmethode, Zahlen in 16-Bit-Stücke zerlegt, Carry nach jeder Ziffer, sonst eher unoptimiert
Zum Potenzieren: Basis wiederholt quadrieren, und die Potenzen entsprechen der 1-Bits im Exponenten zusammenmultiplizieren.

- Hardware:
Ein nicht sehr aktueller, nicht (mehr) übertakteter Core2 E8400 mit 3 GHz. Also ein represäntativer Durchschnitts-PC. Kompiliert wurde auf Win32 / MinGW mit gcc 4.8, Standard-C ohne irgendwelche fancy libraries.

- Ergebnisse:
0x1FE^0x407B: 56 ms bei 29 Mio. 16-Bit-Multiplikationen
0x123456^0x10001: 4,2 sec bei 2,3 Mrd. 16-Bit-Multiplikationen

Die Differenz war zunächst ein *SCHOCK*, doch - siehe #Mul - passen die Werte sehr gut. Leider nur 1 GFlop/s (500 Mul/s, und zu jedem x kommt noch ein +). Meine Matrix-Routinen machen jedenfalls (ohne SSE) 5 GFlop/s pro Core. Weiß der Geier, warum. Cache-Effekte sollten hier ja keine Rolle spielen.

– Fazites:

#1: Meine Schulmalnehmetechnik ist 100 mal schneller als Deine Spezial-Malnehmetechnik; also schau da noch mal drüber: Irgenwas stimmt da nicht (-: Oder du hast das Potenzieren brav iterativ gelöst und nicht nach der Binärmethode, wie in dem oben verlinkten Artikel.

#2: Dass die zweite Aufgabe mit etwas mehr Bits an die 100 mal mehr Rechenoperationen als dein erstes Beispiel benötigt, ist wahr und unüberwindbar. Scheiß Komplexitätstheorie. Aber dagegen sind Mensch und Maschine machtlos.

#3: Was könnte ich an meinem Progrämmchen (nicht: Äppchen!) noch modifizieren? Karatsuba oder Tom-Cook probieren; multithreaden; SSE nutzen, ein paar Schleifenvariablen eliminieren... alles zusammen könnte vll die Zeit für Beispiel 2 unter eine Sekunde drücken.

#4: - und dieser Punkt ist vll am interessaantesten - MODULO!!!

Von Krypto habe ich wenig Ahnung (weil der zuständige Prof zwar gut darin war, durchgeschwitzte weiße Hemden mit seinen siebzigjährigen Nippeln zu verzieren, es mit dem Erklären komplexer Sachverhalte aber nicht so hatte - pfui Deifel, da hab ich mir meine Scheine lieber woanders geholt). Aber ich zumindest, dass die großen Zahlen gerne "kongruent mod p" gerechnet werden: so kannst du den Modulo beim wiederholten Quadrieren auch zwischendrin nach jedem Schritt (oder jedem n., denn Division braucht Zeit) ausführen, um diese Riesenzahlen etwas in die Schranken zu drücken. Das steht auch in dem Wiki-Artikel, den ich in meinem letzten Post verlinkt habe.

Also, ich mach jetzt mal Schluß und geh’ noch einen trinken. Sollte ich morgen dann doch zu faul für die geplante Radtour sein, frickle ich da sicher noch etwas herum. Aber fange du gar nicht erst an mit dem Schönhage-Strassen; es sei denn du verfügst über eine masochistische Ader oder planst, das Thema Deiner Seminararbeit in Richtung Evaluierung diverser Multiplikationsalgorithmen zu ändern :-). Wenn du natürlich Gefallen daran gefunden hast, nur zu!

Grüße

Eddy a.k.a. Claus

P.S. Meinen Code von heute abend kannst du gerne haben; ich würde nur morgen noch ein paar Kommentare reinstreuen, um den Thread nicht zu sehr zu belasten.

EDIT: Smiley eingefügt :twisted:

_________________
BildDer Außerirdische mit Tentakelarmen hat es schwer, einen Lötkolben zu halten“ – Harald Lesch


Share on FacebookShare on Google+Share on Reddit
Nach oben
 Profil  
Mit Zitat antworten  
 Betreff des Beitrags: Re: Laufzeit free() C
BeitragVerfasst: Sa 12. Sep 2015, 17:07 
Offline
Benutzeravatar

Registriert: Sa 11. Mai 2013, 15:31
Beiträge: 528
Wohnort: Bayern

Spezialgebiet: Knoten,"Hallo Wach Kaffee+",C Sockets
Schule/Uni/Arbeit: Gymnasium
OK das hilft weiter ich glaube ich weiß jetzt wo das Problem liegt. Potenzierung hab ich schon Binär gelöst anders ist das ja auch sinnlos. Mein Toom algo ist wahrscheinlich relativ gut implementiert hat gegenüber Schulmethode eine Verbesserung von 35 gebracht (40 wäre Theoretisch möglich). Da Toom ja nichts anderes macht als ein Produkt in kleinere Produkte zu Zerlegen und das dann irgendwann Rekursiv (mit der Schulmethode) Abzubrechen muss es ja wohl an meiner Implementierung der Schulmultiplikation liegen. Das habe ich etwas anders als du gelöst. Dort habe ich mit Russischer Bauernmultiplikation Gearbeitet d.h.wenn ein Bit in einem Faktor gesetzt ist wird der andere Faktor zum endgültigen Produkt addiert. Woran ich dabei natürlich nicht gedacht hab ist dass der Prozessor ja intern schon Routinen hat die das selbe machen. Allerdings aufgrund der Hardware Gegebenheiten weitaus schneller. Wenn man jetzt natürlich wie du de Schulmethode anwendet aber mit den internen Routinen ist das natürlich massiv schneller. Das mit dem modulo wusste ich schon hier http://www.loria.fr/~zimmerma/mca/mca-cup-0.5.9.pdf sind die Anwendungsbereiche vieler Algorithmen schön beschrieben hab das da schon Raus gezogen. Noch einen Tipp für Große Zahlen bc (unter linux schon Vorinstalliert aber auch für Windows erhältlich) Die ein und Ausgabe kann man auch auf hex umstellen(steht in den Variablen ibase und obase).
EDIT: Schönhage-Strassen Interessiert mich durchaus Großteil von meiner Facharbeit ist mittlerweile Fertig und ich hab noch 2 Monate Zeit mal schauen wenn alles Funktioniert könnte ich mich mal dran wagen. Grundkonzept ist auch nicht so mega-kompliziert was mir mehr Sorgen macht ist die Benötigte FFT. Wenn man das hin bekommt ist es zur "Schnellen" Multiplikaton denk ich nicht mehr weit. Wie gesagt mal schauen.

_________________
I <3 0402
Real ist alles was warm wird.


Share on FacebookShare on Google+Share on Reddit
Nach oben
 Profil  
Mit Zitat antworten  
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Ein neues Thema erstellen Auf das Thema antworten  [ 16 Beiträge ]  Gehe zu Seite 1, 2  Nächste

Alle Zeiten sind UTC + 1 Stunde


Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 2 Gäste


Du darfst keine neuen Themen in diesem Forum erstellen.
Du darfst keine Antworten zu Themen in diesem Forum erstellen.
Du darfst deine Beiträge in diesem Forum nicht ändern.
Du darfst deine Beiträge in diesem Forum nicht löschen.
Du darfst keine Dateianhänge in diesem Forum erstellen.

Gehe zu:  
cron



Powered by phpBB® Forum Software © phpBB Group
Deutsche Übersetzung durch phpBB.de

moShBox © 2008, 2009, 2010 mosfetkiller-Community