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!

Kennt jemand einen effektiveren algorhytmus?

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

08.12.2005, 20:03

Kennt jemand einen effektiveren algorhytmus?

Es geht um die bestimmung des ggTs, ich suche eine relativ schnelle Variante mein bisheriger Ansatz ist:

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

int ggT(int a, int b)
{
    if(a>b)
    {
        int tmp = a%b;

        if(tmp)
            return ggT(b,tmp);

        else
            return b;
    }

    else
    {
        int tmp = b%a;

        if(tmp)
            return ggT(a,tmp);

        else
            return a;
    }
}


oder wenn man weiß, dass die erste Zahl größer ist:

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10

int ggT(int a, int b)
{
    int tmp = a%b;

    if(tmp)
        return ggT(b,tmp);

    else
        return b;
}


Zur Not habe ich noch den hier, auch wenn ich nich weiß ob er schneller ist, denn die Ergebnisse waren nicht eindeutig:

C-/C++-Quelltext

 
1
2
3
4
5
6

int ggT(int a, int b)
{
    if(b) return ggT(b, a%b);

    return a;
}


habt ihr noch ideen, einwände oder Vorschläge, wäre sehr dankbar.

CW_Kovok

Anonymous

unregistriert

2

08.12.2005, 20:11

Schnell genug

C-/C++-Quelltext

 
1
2
3
4
5
6

inline long ggT (long a, long b) 
{ 
    if (b) return ggT (b, a%b); 

    return a; 
}

Aber wenn Du es schneller haben willst: Rekursion raus! Rekursion dauert länger als eine Schleife.

Dave

Alter Hase

Beiträge: 757

Wohnort: Berlin

  • Private Nachricht senden

3

08.12.2005, 20:32

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11

int ggt(int a, int b)
{
        int temp;
        while(a>0)
        {
            temp=a;
            a=b%a;
            b=temp;
        }
        return b;
}


keine rekursion. schön schnell.

Anonymous

unregistriert

4

08.12.2005, 20:37

Zum 2. mal: long und inline

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13

inline long ggt (long a, long b) 
{ 
    long temp; 

    while(a>0) 
    { 
        temp=a; 
        a=b%a; 
        b=temp; 
    } 

    return b; 
}
und keine tabulatoren.

Dave

Alter Hase

Beiträge: 757

Wohnort: Berlin

  • Private Nachricht senden

5

08.12.2005, 20:42

;)

Steven77

Alter Hase

Beiträge: 515

Wohnort: Münster - Gievenbeach

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

6

09.12.2005, 11:56

Da Du ja auf Effizienz und Geschwindigkeit Wert legst, zieh Dir das rein:

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

inline long gcd_casm(long a, long b)
{
    __asm
    {
        mov     eax, a
        mov     ebx, b

_gcd_casm_loop:

        or      ebx, ebx
        jz      _gcd_casm_done

        xor     edx, edx
        div     ebx
        mov     eax, ebx
        mov     ebx, edx

        jmp     _gcd_casm_loop

_gcd_casm_done:

        mov     a, eax
    }
    return a;
}


Das bringt allerdings nicht besonders was.
Richtig geil wird's, wenn Du's so machst:

Quellcode

 
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

.386
.model flat, c

.code

gcd_masm proc a: sdword, b: sdword
        
        mov     eax, a
        mov     ebx, b
        
        or      ebx, ebx
        jz      @_gcd_done
        
        align 4
@_gcd_loop:
        
        xor     edx, edx
        div     ebx
        or      edx, edx
        jz      @_gcd_stop
        mov     eax, ebx
        mov     ebx, edx
        
        jmp     @_gcd_loop
        
        align 4
@_gcd_stop:
        mov     eax, ebx
@_gcd_done:
        ret
        
gcd_masm endp

end

C-/C++-Quelltext

 
1
2
3

extern "C" {
    long gcd_masm(long a, long b);
}


edit: Sorry, ich konnte nicht anders... ;)

Anonymous

unregistriert

7

09.12.2005, 14:24

Steven77
Ich verkleif mir mal jetzt SSE Code zu Posten ;)

dot

Supermoderator

Beiträge: 9 757

Wohnort: Graz

  • Private Nachricht senden

8

09.12.2005, 15:59

was bringt da SSE!?

Anonymous

unregistriert

9

09.12.2005, 16:27

dot
Das selbe was hier Assembler gebracht hat: Sogut wie gar nichts, aber zum Rumbonzen reicths doch :D

Steven77

Alter Hase

Beiträge: 515

Wohnort: Münster - Gievenbeach

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

10

09.12.2005, 17:12

Zitat von »"nix da"«

dot
Das selbe was hier Assembler gebracht hat: Sogut wie gar nichts, aber zum Rumbonzen reicths doch :D

Das siehst Du vollkommen falsch!
Der obige Assembler-Code spart über 40% Rechenzeit ein, was jawohl schon nicht schlecht ist.
Durch SSE würdest Du keinen Hauch schneller werden, da Du ja nicht Unmengen von Daten "parallel" umschaufeln oder transformieren willst, sondern nur mit 32-Bit-Registern rechnest. Die Standardregister (eax, edx etc.) haben nunmal die Länge 32.
Befasse Du Dich lieber mit perfektem Design ohne #defines, Tabs und so und lass mir meinen Spaß an Assembler. ;) Nicht bös gemeint.

Werbeanzeige