jsturges@td2cad.intel.com (jay sturges) (06/28/89)
I have found that when dealing with whole number results
it is a far better to create trivial routines to approximate
at a lower level of accuracy. By doing so one can experience
multitudes of performance increase as well as still achieving
the same level of accuracy.
The following source code contains a power series for a
square root function. I have found that using this function
you can actually increase performance if accuracy to a real
value is not required. As below with calculating a prime
number only 3 iterations of the power series is required.
the reflected increase in performance was measured at 4X
over standard C library sqrt( ). This was measured on a
Sun386i system with 80387 coproc
Enjoy the tid-bit
-Jay sun!sacto!pldote!jsturges
+--+--+--+--+--+ C U T +--+--+--+--+--+
#include <stdio.h>
/*
* Prime( )
*
* simple routine to generate the smallest prime number
* larger than a given number. makes use of a very trivial
* C implementation of a power series square root function.
* the need for this function is to eliminate the need for
* the standard math library. accuracy is not a issue as
* the end result is a whole number.
*
* Author: Jay Sturges sun!sacto!pldote!jsturges
* Date : June 23, 1989
*
* Copyright: NONE .... Just enjoy
*/
main( argc, argv )
int argc;
char **argv;
{
argv++; argc--;
while ( argc-- > 0) {
printf("Smallest Prime larger --> %d\n",calc_prime(atoi(*argv++)));
}
}
/*
* calc_prime( )
* calculate the smallest prime larger than a given value
*/
int calc_prime( n )
int n; /* whole number as start */
{
int x;
int prime;
x = n + 1;
prime = 0;
while ( prime <= n ) {
if ( pchk( x ) && ( x > n ) ) {
prime = x; /* is prime */
}
else {
x++; /* try again */
}
}
return( prime );
}
/*
* pchk( )
* checks if value is prime
*/
int pchk( n )
int n;
{
int max;
int i;
max = trivial_sqrt( n ) + 1;
for (i = 2; i < max; i++) {
if ( !(n % i) ) {
return( 0 );
}
}
return( 1 ); /* prime */
}
#define M 3 /* minimum iterations for whole numbers */
/*
* trivial_sqrt( )
* return the integer sqrt of the value
*/
int trivial_sqrt( n )
int n;
{
int i;
float x;
float y;
float a;
y = ( float ) n;
x = y;
/*
* square root
*
* 2
* X = X - X - A
* i+1 i i
* ---------
* 2X
* i
* Where:
* A = n
* X = n
* 1
*/
for ( i = 0; i < M; i++ )
x = x - ( ( ( x*x ) - y ) / ( 2 * x ) );
return( (int) x );
}