Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Zu dumm für alles, oder die neue Umgebung: nix als ärger

Werbeanzeige

CW_Kovok

Alter Hase

  • »CW_Kovok« ist der Autor dieses Themas

Beiträge: 836

Wohnort: nähe Bonn

Beruf: Schüler

  • Private Nachricht senden

1

16.01.2006, 21:56

Zu dumm für alles, oder die neue Umgebung: nix als ärger

Moin,

habe mir gerade in 5 min was zusammengeschustert, weil ich wissen wollte, wie zeitintensiv eine modulorechnung ist, naja lange rede kurzer sinn, prob ist, dass das programm ohne fehler ist, aber nix ausgibt, sondern immer nur weiter mit beliebiger taste angibt, warum?

Hier der Quellcode:

C-/C++-Quelltext

 
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

#include <iostream>
#include <ctime>

int ggte(__int32 a, __int32 b)
{
    if(a>b)
    {
        __int32 c = a-b;
        return ::ggte(c, b);
    }

    else if(a<b)
    {
        __int32 c = b-a;
        return ::ggte(a, c);
    }

    else
        return b;
}

int ggtm(__int32 a, __int32 b)
{
    if(a>b)
    {
        __int32 c = a%b;
        return ::ggtm(c, b);
    }

    else if(a<b)
    {
        __int32 c = b%a;
        return ::ggtm(a, c);
    }

    else
        return b;
}

int main()
{
    long anf, end;

    anf = ::clock();

    for(unsigned __int32 i=0; i<1e6; i++)
        ggte(15, 12);

    end = ::clock();

    std::cout<<(end-anf)/CLOCKS_PER_SEC<<std::endl;

    anf = ::clock();

    for(unsigned __int32 i=0; i<1e6; i++)
        ggtm(15, 12);

    end = ::clock();

    std::cout<<(end-anf)/CLOCKS_PER_SEC<<std::endl;

    return 0;
}
Was es alles gibt, das ich nich brauche - Aristoteles

Anonymous

unregistriert

2

16.01.2006, 22:22

Hi,

versuch mal das hier zu klammern: (end-anf)/CLOCKS_PER_SEC

Ansonsten schön das Du den Euklid-Algo probierst :) Jedoch da Du rekursiv arbeitest, bremst Du Dich selbst aus. Hab was besseres ;)

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

template<typename T> inline void swap (T* left, T* right)
{
    const T temp = (*left);

    (*left)  = (*right);
    (*right) = temp;
}

    // Shift durchführung

template<typename T> inline void shift (T* x, T* y, T z)
{
    (*x) = (*y);
    (*y) = z;
}

inline long ggt (long left, long right)
{
        // 'left' soll größer als 'right' sein

    if (right > left) swap<long> (&left, &right);

    while (right != 0) shift<long> (&left, &right, left%right);

    return (left);
}



Ansonsten guck mal was der Debugger ausspuckt!

CW_Kovok

Alter Hase

  • »CW_Kovok« ist der Autor dieses Themas

Beiträge: 836

Wohnort: nähe Bonn

Beruf: Schüler

  • Private Nachricht senden

3

17.01.2006, 20:59

danke funzt jetzt, aber kann mir mal jemand sagen, wie der rechner eine modulorechnung durchführt, denn diese ist wesentlich schneller als die einfache euklidmethode, daher muss die modulo operation anders aufgebaut sein als ich dachte, hat jemand ne ahnung wie?
Was es alles gibt, das ich nich brauche - Aristoteles

Black-Panther

Alter Hase

Beiträge: 1 443

Wohnort: Innsbruck

  • Private Nachricht senden

4

17.01.2006, 21:03

der Prozessor macht eine einfache Bitoperation... wie die jetzt genau aussieht müsste ich nachschauen ;)

Edit:
Uups, hab mich geirrt ;-) Das war was anderes:
http://de.wikipedia.org/wiki/Modulo_(Rest)
stillalive studios
Drone Swarm (32.000 Dronen gleichzeitig steuern!)
facebook, twitter

koschka

Community-Fossil

Beiträge: 2 862

Wohnort: Dresden

Beruf: Student

  • Private Nachricht senden

5

17.01.2006, 21:11

naja, also ich glaub die Optimierung reicht schon... um den Rest kann sich doch der Compiler kümmern, ... den euklidischen Algo hasste ja... bzw. nix da ^^.

Aus den Daten des Euklisischen Algo kann man auch noch das Inverse zu a mod(b) berechnen. Ich wüsste zwar nicht wozu man das jetzt direkt braucht... aber zumindestens in einer guten Mathe Lib sollte das ned fehlen.

CW_Kovok

Alter Hase

  • »CW_Kovok« ist der Autor dieses Themas

Beiträge: 836

Wohnort: nähe Bonn

Beruf: Schüler

  • Private Nachricht senden

6

17.01.2006, 21:55

also habe das ganze jetzt so:

C-/C++-Quelltext

 
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

#include <iostream>
#include <ctime>

template<typename T> inline void swap (T* left, T* right)
{
    const T temp = (*left);

    (*left)  = (*right);
    (*right) = temp;
}

template<typename T> inline void shift (T* x, T* y, T z)
{
    (*x) = (*y);
    (*y) = z;
}

inline long ggtm (long left, long right)
{
    if (right > left) swap<long> (&left, &right);

    while (right != 0) shift<long> (&left, &right, left%right);

    return (left);
}

inline long ggte (long left, long right)
{
    while (right != 0)
    {
        if (right > left) swap<long> (&left, &right);
        shift<long> (&left, &right, left-right);
    }

    return (left);
}

int main()
{
    long anf, end;

    anf = ::clock();

   for(unsigned __int32 i=0; i<1e7; i++)
        ggte(154, 16);

    end = ::clock();

    std::cout<<float((end-anf))/CLOCKS_PER_SEC<<std::endl;

    anf = ::clock();

    for(unsigned __int32 i=0; i<1e7; i++)
        ggtm(154, 16);

    end = ::clock();

    std::cout<<float((end-anf))/CLOCKS_PER_SEC<<std::endl;

    return 0;
}


als ergebnis habe ich jetzt 8.854 und 3.584, könnt ihr auch mal ausprobieren für vergleichswerte?
Was es alles gibt, das ich nich brauche - Aristoteles

koschka

Community-Fossil

Beiträge: 2 862

Wohnort: Dresden

Beruf: Student

  • Private Nachricht senden

7

17.01.2006, 22:10

naja, ich wüsste nicht was das bringen sollte, den jeder hat ja andere Prozessoren und auch der gewwählten Zahlen.... besser ist da ein Zeitkompleitätsverleich...

C-/C++-Quelltext

 
1

while (right != 0) shift<long> (&left, &right, left%right);


Die Zeitkomplexität hängt hier von right ab, und im ungünstigsten Fall, wenn der GGT 1 ist und rright bzw left immer um 1 decrementiert werden ist der Zeitaufwand "right". Damit spricht man von einer Zeitkomplexität n.

Da das aber wohl kaum der Fall sein wird... ist die im Nomalfall wesenlich kleiner als right...

Bei einer Zeitkomplexität von n^3 oder n² sollte man sich Gedanken machen, aber doch nciht bei so nem kleckerkram... ^^

riCo

Treue Seele

Beiträge: 165

Beruf: Student

  • Private Nachricht senden

8

17.01.2006, 22:12

Tut mir leid für die unqualifizierte Antwort, aber kann mir mal einer kurz und knapp erklären wozu templates gut sind? Bin bis jetzt auch immer gut ohne ausgekommen..

koschka

Community-Fossil

Beiträge: 2 862

Wohnort: Dresden

Beruf: Student

  • Private Nachricht senden

9

17.01.2006, 22:16

Wenn du ein Datenobjekt hast (z.B. eine Liste) die verschiedene Daten verwalten soll. Also du willst nur die Liste entwerfen, die Daten soll der Anwender dann eingeben. Das kannst du dann mit Templates machen. So ist eine Liste

C-/C++-Quelltext

 
1

List<__int32>

eine Liste mit ganzzahligen, 32 Bit Werten, während

C-/C++-Quelltext

 
1

List<std::basic_string<wchar_t> >

eine Liste mit Unicode String's ist.
Das ganze implementierst du nur einmal, indem du einfach sagst:

C-/C++-Quelltext

 
1
2
3
4
5
6
7

template<typename T> class List
{
    private:
        T   data;
    public:
        .....
};


T bezeichnet dabei den Typ den der spätere Anwender braucht. Ich hoffe es ist klar gewurden. In C hhat man es mit void* Zeigern gemacht, in Cpp macht man es mit templates... ist auch schöner.

CW_Kovok

Alter Hase

  • »CW_Kovok« ist der Autor dieses Themas

Beiträge: 836

Wohnort: nähe Bonn

Beruf: Schüler

  • Private Nachricht senden

10

17.01.2006, 23:02

mir geht es um den imensen zeitvorteil der modulorechnung gegenüber euklid, und woher der kommt, werde mir dass ganze wohl oder übel mal mit einm dissassembler angucken
Was es alles gibt, das ich nich brauche - Aristoteles

Werbeanzeige