PrimeBenchmark

PrimeBenchmark.c

#include <stdio.h>
#include "xtime_l.h"
#include "platform.h"
#include "xil_printf.h"
#include "xparameters.h"

#define MAX 10000000
#define CACHE_MAX 1000

/* Compute the sqrt(n) using Newton's approximation method.
** It is only accurate for n >= 5 because it relies solely
** on integer arithmetic */
int msqrt(int n)
{
	int prev, cur = n, diff;

	do
	{
		prev = cur;
		cur = (prev + n/prev)/2;

		diff = prev - cur;
		if(diff < 0) diff = -diff;
	} while(diff > 1);
	return cur;
}

/* Check if n is prime, first using cache as a source of possible divisors.
** Cache is an ordered table of primes.  If we reach the end without exceeding
** sqrt(n), we manually try remaining possible divisors <= sqrt(n) */
int isprime(int n, int cache[], int *end)
{
	int max = msqrt(n), tmp = 1;
	while(cache < end)
	{
		tmp = *cache;
		if(tmp > max) return 1;
		if(n % tmp == 0) return 0;
        cache++;
	}
	for(tmp += 2; tmp <= max; tmp += 2)
	{
        if(n % tmp == 0) return 0;
	}
	return 1;
}

/* Iterate from 2 to max, checking if i is a prime, and keeping track
** of the number of primes we find.  The first CACHE_MAX primes we find
** are saved in cache. */
int checkprimes(int max, int cache[], int *len)
{
	int i = 1, count = 1, *pos = cache, *end = cache + CACHE_MAX;

	*pos = 2;
    pos++;

	for(i += 2; i < max; i+=2)
	{
		if(isprime(i, cache, pos))
		{
			if(pos<end)
			{
				*pos = i;
				pos++;
			}
			count++;
		}
	}
	*len = pos - cache;
	return count;
}


int main()
{
    init_platform();

    printf("Starting computation\n");

    XTime start, end;
    int size, cache[CACHE_MAX], max = MAX;

    XTime_GetTime(&start);
    int count = checkprimes(max, cache, &size);
    XTime_GetTime(&end);

    printf("Output took %llu clock cycles.\n", 2*(end - start));
    printf("Output took %.2f us.\n",
               1.0 * (end - start) / (COUNTS_PER_SECOND/1000000));

    cleanup_platform();
    return 0;
}