Here's one example using sqrt() and the "binary" isqrt():
Code:
/* sqrt-test.c */
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <limits.h>
#include <math.h>
#include "../../src/cycle_counting.h"
static unsigned int isqrt( unsigned int );
int main( int argc, char **argv )
{
counter_T c1, c2;
unsigned long n;
unsigned int a, b;
char *p;
// I'll ignore more than 1 argument!
if ( ! *++argv )
{
fputs( "Usage: prime <number>\n", stderr );
return EXIT_FAILURE;
}
errno = 0;
n = strtoul( *argv, &p, 10 );
// I'll accept only numeric argument in range... (no spaces).
if ( errno == ERANGE || *p != '\0' )
{
error:
fputs( "ERROR: Invalid argument\n", stderr );
return EXIT_FAILURE;
}
// I'll accept only argument in 'unsigned int' range.
if ( n > UINT_MAX )
goto error;
c1 = BEGIN_TSC();
a = sqrt( n );
END_TSC( &c1 );
c2 = BEGIN_TSC();
b = isqrt( n );
END_TSC( &c2 );
printf( " sqrt( %1$lu ) = %2$u (%3$lu cycles)\n"
"isqrt( %1$lu ) = %4$u (%5$lu cycles)\n",
n, a, c1, b, c2 );
return EXIT_SUCCESS;
}
// Interesting binary algorithm to extract integer square root.
// This is, essentially, a binary search algorithm.
// Use this to avoid using floating point sqrt() - (and it is, probably, faster).
// Stolen from wikipedia: https://en.wikipedia.org/wiki/Methods_of_computing_square_roots
unsigned int isqrt( unsigned int num )
{
unsigned int res = 0;
unsigned int bit = 1U << 30;
while ( bit > num )
bit >>= 2;
while ( bit )
{
if ( num >= res + bit )
{
num -= res + bit;
res = ( res >> 1 ) + bit;
}
else
res >>= 1;
bit >>= 2;
}
return res;
}
Compiling (with optimization) and running in an i7-4770:
Code:
$ cc -O2 -o sqrt-test sqrt-test.c
$ ./sqrt-test
$ ./sqrt-test 1000000000
sqrt( 1000000000 ) = 31622 (537 cycles)
isqrt( 1000000000 ) = 31622 (497 cycles)
isqrt() is 7% faster.
Now, add -ffast-math option:
Code:
$ gcc -O2 -ffast-math -o sqrt-test sqrt-test.c
$ ./sqrt-test 1000000000
sqrt( 1000000000 ) = 31622 (109 cycles)
isqrt( 1000000000 ) = 31622 (553 cycles)
So, without the proper optimizations, isqrt() is, indeed, faster.