Berechnung in C parallel laufen lassen?

vip*r

Hey Leute!

Kann man in C Berechnungen parallel laufen lassen? Ich hab z.B. folgendes vor: ich möchte Fibonacci-Zahlen einmal rekursiv und einmal iterativ Berechnen lassen. Dabei ist klar, dass die iterative Lösung hier wesentlich schneller auf das korrekte Ergebnis kommt als die rekursive Lösung. Dies möchte ich zeitgleich starten lassen um Rückschlüsse auf die Geschwindigkeit erzielen zu können.

Geht das?

cooky451

Kurz: Nö.

C kennt keine Threads, du wirst das wohl hintereinander ausführen müssen. Das dürfte aber eh zu viel genaueren Messungen führen.
Für Threads musst du dir Betriebssystemfunktionen angucken, oder libs die das Ganze kapseln.

vip*r

Hier mal kurz der Code für die fib-Zahlen:

#include<iostream>

int fib_rekursiv(int n)
{
	if(n == 0)
	{
		return 0;
	}

	if(n == 1)
	{
		return 1;
	}

	if(n > 1)
	{
		return fib_rekursiv(n-1) + fib_rekursiv(n-2);
	}
}

int fib_iterativ(int n)
{
	if(n == 0)
	{
		return 0;
	}

	if(n == 1)
	{
		return 1;
	}

	if(n > 1)
	{
		int fib1 = 0, fib2 = 1, fib_tmp;

		for(int i=0; i<n-1; i++)
		{
			fib_tmp = fib1 + fib2;
			fib1 = fib2;
			fib2 = fib_tmp;
		}

		return fib2;
	}
}

int main()
{
	int n;

	printf("n = ");
	scanf("%i", &n);

	printf("Fib_iterativ(%i) = %i\n\n", n, fib_iterativ(n));
	printf("Fib_rekursiv(%i) = %i\n\n", n, fib_rekursiv(n));

return 0;
}

Ich hab jetzt nur die Frage, warum ich die for-Schleife n-1 mal laufen lassen muss, damit ich auf das richtige Ergebnis bei z.B. Fib(12) komme. Was is'n da falsch?

So genau werden die Messungen im Zweifel gar nicht sein müssen. Die naive iterative Berechnungsweise skaliert mit O(n), die rekursive mit O(Φⁿ), wobei Φ ≈ 1,6180339887 der goldene Schnitt ist.

Schon für recht kleine n liegt man da um Größenordnungen auseinander - bei n = 40 dürfte das in der Gegend von "Sekunden gegen Jahre" liegen.

Was die Schleife bis n - 1 angeht - was meinst du, falsch? Für mich sieht das richtig aus. Du fängst mit F(0) und F(1) an, im ersten Durchlauf errechnest du dann F(2), und im (n - 1)ten Durchlauf errechnest du F(n).