fib: n > 46 not handled, and fib_verify_value() returns incorrect result for n >= FIB_RESULTS_PRE

[weeks@…]

1. Integer overflow occurs in the Fibonacci number calculated by both serial and omp-tasks versions of the fib kernel for "-n 47" or greater (assuming a conventional 32-bit "int"). Users are likely to be affected by this, because the "medium" input size for the fib kernel uses "-n 50".

2. fib_verify_value(n) returns incorrect results when n >= FIB_RESULTS_PRE (currently defined as 41) due to an error in the while loop that calculates Fibonacci numbers that are not in the precalculated fib_results[] array.

The following patch addresses issue (1) by using "long long" instead of "int" for variables that store Fibonacci numbers, and (2) by fixing the loop in fib_verify_value(n), which obviates the need for the fib_results array.

Note that this patch incorporates the fib_verify() fix described in: http://nanos.ac.upc.edu/projects/bots/ticket/129 which is needed to correctly flag any differences in the parallel and serial results.

--- serial/fib/fib.h.orig	2011-01-14 09:17:48.000000000 -0600
+++ serial/fib/fib.h	2011-06-07 21:15:06.000000000 -0500
@@ -19,7 +19,7 @@
 /**********************************************************************************************/
 #ifndef FIB_H
 #define FIB_H
-int fib (int n);
+long long fib (int n);
 void fib0 (int n);
 #endif
 
--- serial/fib/fib.c.orig	2011-01-14 09:17:48.000000000 -0600
+++ serial/fib/fib.c	2011-06-07 21:15:06.000000000 -0500
@@ -21,11 +21,11 @@
 #include "bots.h"
 #include "fib.h"
 
-static int res;
+static long long int res;
 
-int fib (int n)
+long long fib (int n)
 {
-	int x, y;
+	long long x, y;
 	if (n < 2) return n;
 
 	x = fib(n - 1);
@@ -37,6 +37,6 @@
 void fib0 (int n)
 {
 	res = fib(n);
-	bots_message("Fibonacci result for %d is %d\n",n,res);
+	bots_message("Fibonacci result for %d is %lld\n",n,res);
 }
 
--- omp-tasks/fib/fib.h.orig	2011-01-14 09:17:48.000000000 -0600
+++ omp-tasks/fib/fib.h	2011-06-08 06:43:38.000000000 -0500
@@ -20,21 +20,21 @@
 #ifndef FIB_H
 #define FIB_H
 #if defined(IF_CUTOFF)
-int fib (int n,int d);
+long long fib (int n,int d);
 #elif defined(FINAL_CUTOFF)
-int fib (int n,int d);
+long long fib (int n,int d);
 #elif defined(MANUAL_CUTOFF)
-int fib (int n,int d);
+long long fib (int n,int d);
 #else
-int fib (int n);
+long long fib (int n);
 #endif
 
-int fib_seq (int n);
+long long fib_seq (int n);
 
 void fib0 (int n);
 void fib0_seq (int n);
 
 int fib_verify (int n);
-int fib_verify_value(int n);
+long long fib_verify_value(int n);
 #endif
 
--- omp-tasks/fib/fib.c.orig	2011-02-11 10:20:00.000000000 -0600
+++ omp-tasks/fib/fib.c	2011-06-08 19:51:06.000000000 -0500
@@ -21,12 +21,9 @@
 #include "bots.h"
 #include "fib.h"
 
-#define FIB_RESULTS_PRE 41
-int fib_results[FIB_RESULTS_PRE] = {0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155};
-
-int fib_seq (int n)
+long long fib_seq (int n)
 {
-	int x, y;
+	long long x, y;
 	if (n < 2) return n;
 
 	x = fib_seq(n - 1);
@@ -37,9 +34,9 @@
 
 #if defined(IF_CUTOFF)
 
-int fib (int n,int d)
+long long fib (int n,int d)
 {
-	int x, y;
+	long long x, y;
 	if (n < 2) return n;
 
 	#pragma omp task untied shared(x) firstprivate(n) if(d < bots_cutoff_value)
@@ -54,9 +51,9 @@
 
 #elif defined(FINAL_CUTOFF)
 
-int fib (int n,int d)
+long long fib (int n,int d)
 {
-	int x, y;
+	long long x, y;
 	if (n < 2) return n;
 
 	#pragma omp task untied shared(x) firstprivate(n) final(d+1 >= bots_cutoff_value) mergeable
@@ -71,9 +68,9 @@
 
 #elif defined(MANUAL_CUTOFF)
 
-int fib (int n, int d)
+long long fib (int n, int d)
 {
-	int x, y;
+	long long x, y;
 	if (n < 2) return n;
 
 	if ( d < bots_cutoff_value ) {
@@ -94,9 +91,9 @@
 
 #else
 
-int fib (int n)
+long long fib (int n)
 {
-	int x, y;
+	long long x, y;
 	if (n < 2) return n;
 
 	#pragma omp task untied shared(x) firstprivate(n)
@@ -110,7 +107,7 @@
 
 #endif
 
-static int par_res, seq_res;
+static long long par_res, seq_res;
 
 void fib0 (int n)
 {
@@ -121,26 +118,29 @@
 #else
 	par_res = fib(n);
 #endif
-	bots_message("Fibonacci result for %d is %d\n",n,par_res);
+	bots_message("Fibonacci result for %d is %lld\n",n,par_res);
 }
 
 void fib0_seq (int n)
 {
 	seq_res = fib_seq(n);
-	bots_message("Fibonacci result for %d is %d\n",n,seq_res);
+	bots_message("Fibonacci result for %d is %lld\n",n,seq_res);
 }
 
-int fib_verify_value(int n)
+long long fib_verify_value(int N)
 {
-	int result = 1;
-	if (n < FIB_RESULTS_PRE) return fib_results[n];
+    int n;
+	long long Fn = 1, Fn_minus_one = 0, Fn_prev;
+
+    if (N == 0) return 0;
 
-	while ( n > 1 ) {
-		result += n-1 + n-2;
-		n--;
+	for(n = 2; n <= N; n++) {
+       Fn_prev = Fn;
+       Fn += Fn_minus_one;
+       Fn_minus_one = Fn_prev;
 	}
 		
-	return result;
+	return Fn;
 }
 
 int fib_verify (int n)
@@ -150,13 +150,13 @@
 	if (bots_sequential_flag)
 	{
 		if (par_res == seq_res) result = BOTS_RESULT_SUCCESSFUL;
-		else result = BOTS_RESULT_SUCCESSFUL;
+		else result = BOTS_RESULT_UNSUCCESSFUL;
 	}
 	else
 	{
 		seq_res = fib_verify_value(n);
 		if (par_res == seq_res) result = BOTS_RESULT_SUCCESSFUL;
-		else result = BOTS_RESULT_SUCCESSFUL;
+		else result = BOTS_RESULT_UNSUCCESSFUL;
 	}
 
 	return result;

[xteruel]

Ticked fixed in [26c942f71e598c527249edcaf07768ac4b39fd95]