From 3f7d52c8d887e98a350ec3ee1fe59ebf73ea2035 Mon Sep 17 00:00:00 2001
From: David Kaufmann <astra@fsinf.at>
Date: Fri, 13 Jan 2012 16:03:46 +0100
Subject: [PATCH] algorithm1 implemented

---
 openmp/prefix/algorithm_1.c | 24 ++++++++++++++++++++++--
 openmp/prefix/algorithm_1.h |  2 +-
 openmp/prefix/prefix.c      | 18 ++++++++++--------
 3 files changed, 33 insertions(+), 11 deletions(-)

diff --git a/openmp/prefix/algorithm_1.c b/openmp/prefix/algorithm_1.c
index 27f3eff..ed0a1be 100644
--- a/openmp/prefix/algorithm_1.c
+++ b/openmp/prefix/algorithm_1.c
@@ -3,6 +3,26 @@
  */
 #include "algorithm_1.h"
 
-int algorithm_1 (numtype y[], int n, int ops[]) {
-	return 0;
+void algorithm_1 (numtype x[], int n, int ops[]) {
+	int i;
+	numtype y[n/2];
+	if (n == 1) {
+		return;
+	}
+
+	for (i=0; i < (n/2); i++) {
+		y[i] = x[2*i] + x[2*i+1];
+	}
+
+	algorithm_1(y, n/2, ops);
+
+	x[1] = y[0];
+
+	for (i = 1; i < (n/2); i++){
+		x[2*i] = y[i-1] + x[2*i];
+		x[2*i+1] = y[i];
+	}
+	if ((n%2)==1) {
+		x[n-1] = y[n/2-1] + x[n-1];
+	}
 }
diff --git a/openmp/prefix/algorithm_1.h b/openmp/prefix/algorithm_1.h
index 1d537aa..c6c9ded 100644
--- a/openmp/prefix/algorithm_1.h
+++ b/openmp/prefix/algorithm_1.h
@@ -4,4 +4,4 @@
 #include <stdio.h>
 #include "prefix.h"
 
-int algorithm_1 (numtype y[], int n, int ops[]);
+void algorithm_1 (numtype y[], int n, int ops[]);
diff --git a/openmp/prefix/prefix.c b/openmp/prefix/prefix.c
index 9297e71..33f67c9 100644
--- a/openmp/prefix/prefix.c
+++ b/openmp/prefix/prefix.c
@@ -5,35 +5,37 @@
 #include "algorithm_2.h"
 #include "algorithm_3.h"
 
+#define NUMBERS 800000
+
 int main (int argc, char* argv[]) {
 	int result = 0;
-	numtype numarray[5];
-	int countarray[5];
+	numtype numarray[NUMBERS];
+	int countarray[NUMBERS];
 	int i;
 	double startTime, endTime;
 
-	for (i = 0; i < 5; i++) {
-		numarray[i] = i;
+	for (i = 0; i < NUMBERS; i++) {
+		numarray[i] = 10;
 		countarray[i] = 0;
 	}
 
 	startTime = omp_get_wtime();
 	printf ("calling algorithm 1:");
-	result = algorithm_1(numarray, 5, countarray);
-	printf ("sum: %i\n", result);
+	algorithm_1(numarray, NUMBERS, countarray);
+	printf ("sum: %i\n", numarray[NUMBERS-1]);
 	endTime = omp_get_wtime();
 	printf("took %f seconds.\n", endTime-startTime);
 	
 	startTime = omp_get_wtime();
 	printf ("calling algorithm 2:");
-	result = algorithm_2(numarray, 5, countarray);
+	result = algorithm_2(numarray, NUMBERS, countarray);
 	printf ("sum: %i\n", result);
 	endTime = omp_get_wtime();
 	printf("took %f seconds.\n", endTime-startTime);
 	
 	startTime = omp_get_wtime();
 	printf ("calling algorithm 3:");
-	result = algorithm_3(numarray, 5, countarray);
+	result = algorithm_3(numarray, NUMBERS, countarray);
 	printf ("sum: %i\n", result);
 	endTime = omp_get_wtime();
 	printf("took %f seconds.\n", endTime-startTime);
-- 
2.43.0