Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
PrimeBenchmark
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.