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!

Rechnung braucht unwahrscheinlich lange und Frage zu den Algorithmen von math.h

Werbeanzeige

Rexona for men

Treue Seele

  • »Rexona for men« ist der Autor dieses Themas

Beiträge: 121

  • Private Nachricht senden

1

31.08.2011, 12:42

Rechnung braucht unwahrscheinlich lange und Frage zu den Algorithmen von math.h

So, ich wollte einfach mal ausprobieren, wie lange die Berechnung einer beliebige Anzahl von Potenzen dauert.

Hier einfach mal der (Pseudo-)Code:

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

#include <iostream>
#include <math.h>
#include <ctime>
#include <string>

using namespace std;

int main ()
{
    double b = 0.4;

    for ( int i = 10000; i < 4294967295; i++)
    {
        pow (i, b);
    }

    //pow (1000000000000000000000.0, b);

    cout << "Ende 1" << endl;
    double t1 = clock () / CLOCKS_PER_SEC;
    cout << t1 << endl;

    for ( int i = 0; i < 4294967296; i++)
    {
        pow (i, b);
    }

    cout << "Ende 2" << endl;
    double t2 = clock () / CLOCKS_PER_SEC;
    cout << t2 << endl;

}


Nun wundert mich allerdings, dass die erste for-Schleife genau 0 Sekunden benötigt, die zweite aber einfach nicht fertig werden möchte (bei mir jedenfalls), obwohl nur eine zusätzliche Rechnung ausgeführt werden muss.
Weiß jemand den Grund :D

Außerdem würde mich gerne interressieren, wie denn die Algorithmen der Standardbibliothek zur Berechnung von beliebigen Potenzen aussehen.
Einfach, weil ich Mathematik so mag :)
MSDN kennt nur die Header (genauso wie mein VS), Google will nichts brauchbares ausspucken (oder ich suche nicht mit den richtigen Begriffen).
Gibts hierfür ne Quelle?


Allgemein bin ich immer an solchen Algorithmen (auch für Logarithmen, Sinus etc. ..) interressiert, gibt es allgemein eine Quelle für sowas?
Die rein mathematischen würden mir schon reichen, am Code schreibe ich auch gerne selber rum.

BlueCobold

Community-Fossil

Beiträge: 10 738

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

2

31.08.2011, 12:47

Ich würde sagen da fehlt Dir scheinbar das Wissen über Deine Datentypen. Schau einfach mal nach welche Zahl in diesen int passt (denn ich gehe mal von 32 Bit aus), dann wird ganz schnell klar wie oft die Schleifen eigentlich laufen.
Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

dot

Supermoderator

Beiträge: 9 757

Wohnort: Graz

  • Private Nachricht senden

3

31.08.2011, 12:54

Zitat von »Rexona for men«

Außerdem würde mich gerne interressieren, wie denn die Algorithmen der Standardbibliothek zur Berechnung von beliebigen Potenzen aussehen.

z.B. so

C-/C++-Quelltext

 
1
2
3
4

float pow(float base, float exponent)
{
  return exp(log(base) * exponent);
}


Wobei die meisten Compiler die math Funktionen wohl als Intrinsics kennen. D.h. wenn du sqrt() verwendest, wird (zumindest im Release Build) nicht wirklich ein Aufruf der sqrt() Funktion draus, sondern direkt der entsprechende Maschinenbefehl.


Zitat von »Rexona for men«

Allgemein bin ich immer an solchen Algorithmen (auch für Logarithmen, Sinus etc. ..) interressiert, gibt es allgemein eine Quelle für sowas?
Die rein mathematischen würden mir schon reichen, am Code schreibe ich auch gerne selber rum.

Schau dir mal das an: http://de.wikipedia.org/wiki/Taylorreihe. Oder schau einfach mal nur hier oder hier, um zu sehen wie man z.B. die Exponentialfunktion bzw. den Logarithmus berechnen kann. Die Kernaussage ist, dass man beliebige Funktionen durch eine unendliche Reihe darstellen und damit beliebig genau berechnen kann. Auch wenn man es dann nicht unbedingt wirklich so macht...
m4studios

Dieser Beitrag wurde bereits 4 mal editiert, zuletzt von »dot« (31.08.2011, 13:07)

Rexona for men

Treue Seele

  • »Rexona for men« ist der Autor dieses Themas

Beiträge: 121

  • Private Nachricht senden

4

31.08.2011, 13:23

Zitat

Ich würde sagen da fehlt Dir scheinbar das Wissen über Deine Datentypen. Schau einfach mal nach welche Zahl in diesen int passt (denn ich gehe mal von 32 Bit aus), dann wird ganz schnell klar wie oft die Schleifen eigentlich laufen.
Arg, hab ich ganz vergessen.
256^4 = 4294967296, würd dann passen, schade dass ein long bei mir genauso groß ist :(


Zitat

Schau dir mal das an: http://de.wikipedia.org/wiki/Taylorreihe. Bzw. schau einfach mal nur hier, um zu sehen wie man z.B. die Exponentialfunktion berechnen kann. Die Kernaussage ist, dass man beliebige Funktionen durch eine unendliche Reihe darstellen und damit beliebig genau berechnen kann. Auch wenn man es dann nicht unbedingt wirklich so macht...
Ok, danke :)
Grad ausprobiert, funktioniert gut.
Aber was heißt "nicht unbedingt wirklich so macht" ?

Und achja, wie kriegt der Rechner es hin das so schnell zu berechnen 8|
Ich hab die selbe Schleife 10 mal laufen lassen, die benötigte Zeit ist immer noch 0 Sekunden.

Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »Rexona for men« (31.08.2011, 13:43)

Fuxii

Frischling

Beiträge: 88

  • Private Nachricht senden

5

31.08.2011, 14:28

Zitat von »Rexona for men«

256^4 = 4294967296, würd dann passen, schade dass ein long bei mir genauso groß ist :(


256^4 (= 2^32) ist zwar die Anzahl aller möglichen Kombinationen bzw die Anzahl aller verschiedenen Zahlen die dargestellt werden können, aber es ist nicht das Maximum:

ein int stellt Zahlen im positiven und im negativen dar, daher braucht es die hälfte der Zahlen im negertiven (2^32/2=2^31) und die 0 ist auch eine Zahl, daher ist das Maximum 2^31-1.

du kannst aber auch selbst überprüfen, ob er bei dir überhaupt rechnet, oder nichts tut:

C-/C++-Quelltext

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

#include <iostream>

using namespace std;

int main ()
{
    int Maxa=4294967295;
    int Maxb=4294967296;

    cout << Maxa << endl;
    cout << Maxb << endl << endl;

    cout << ((0<Maxa)   ? "True" : "False" ) << endl;
    cout << ((1000<Maxb)? "True" : "False" ) << endl << endl;

    cout << ((0<4294967295)   ? "True" : "False" ) << endl;
    cout << ((1000<4294967296)? "True" : "False" ) << endl << endl;

    system("Pause");
}

Zitat

Basically, there are only 10 types of people in the world. Those who know binary, and those who don't.

foreach

Frischling

Beiträge: 87

Beruf: Student

  • Private Nachricht senden

6

31.08.2011, 14:31

Der Rechner braucht vermutlich 0 Sekunden weil der Compiler die Schleife wegoptimiert hat.
Wenn du verhindern willst, dass der Compiler die Optimierungen vornimmt musst du entweder die Compiler-Optionen ändern, das Ergebnis von "pow" verwenden, oder eine deiner Variablen als "volatile" deklarieren.
Mit "nicht unbedingt wirklich so macht" meint dot, dass die Algorithmen zwar mathematisch korrekt sind, aber für die meisten Programme zu langsam wären, wenn sie so auf der FPU oder in einer Bibliothek umgesetzt wären.
Wenn du dir einmal eine Implementierung ansehen möchtest, dann kannst du dir die C-Bibliothek fdlibm anshen, welche jedem Java-Programmierer, der das Schlüßelwort "strictfp" und die Klasse "StrictMath" kennt, ein Begriff sein sollte.

Zitat

rg, hab ich ganz vergessen.
256^4 = 4294967296, würd dann passen, schade dass ein long bei mir genauso groß ist :(
Aber "long long" bzw. "__int64" haben einen größeren Wertebereich.

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »foreach« (31.08.2011, 15:26)

Rexona for men

Treue Seele

  • »Rexona for men« ist der Autor dieses Themas

Beiträge: 121

  • Private Nachricht senden

7

31.08.2011, 15:05

Zitat

256^4 (= 2^32) ist zwar die Anzahl aller möglichen Kombinationen bzw die Anzahl aller verschiedenen Zahlen die dargestellt werden können, aber es ist nicht das Maximum:

ein int stellt Zahlen im positiven und im negativen dar, daher braucht es die hälfte der Zahlen im negertiven (2^32/2=2^31) und die 0 ist auch eine Zahl, daher ist das Maximum 2^31-1.
Ups, hab ich glatt vergessen :whistling:

Zitat

Aber "long long" bzw. "__int64" haben einen größeren Wertebereich.
Danke, gut dass es sowas auch gibt :D
Mit dann 10 Milliarden Berechnungen hat es immerhin 12 Sekunden gedauert.
Jetzt bin ich wieder beruhigt.

BlueCobold

Community-Fossil

Beiträge: 10 738

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

8

31.08.2011, 15:09

Zitat von »foreach«

Der Rechner braucht vermutlich 0 Sekunden weil der Compiler die Schleife wegoptimiert hat.

Eher nicht. Das liegt wohl eher daran was ich schon oben gesagt habe und was durch Fuxii konkretisiert wurde. Die Zahlen sind zu groß für den Bereich eines ints und somit entweder Null oder sogar negativ.
Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

Werbeanzeige

Ähnliche Themen