Author 
Message 
Prime_Count@hotmail.com science forum beginner
Joined: 20 Feb 2006
Posts: 2

Posted: Mon Feb 20, 2006 9:42 pm Post subject:
Prime Counting: O(.8+e) time, O(e) space. Can this be improved?



So, over the course of the last year or so, I've been working on a
prime counting algorithm. The fastest I've been able to get it, as my
subject line says, is O( n^4/5 + epsilon ) execution and O( epsilon )
memory  and that execution time is really only empirical.
Can anyone think of any ways to improve the speed of this, aside from
swapping it out with completely dissimilar algorithms, of course?
I've included both the description of the math below, as well as C++
code implementing the algorithm (it's only about 400 lines long).
I'm really interested in knowing if this can be improved.
Nathan McKenzie
*******************************
Section 1: Prime Power Function

For any positive constant integer N, where n1, n2, ... nx are natural
number variables greater than or equal to 2,
#{ n1 = N : nx >= 2 }
 1/2 * #{ n1 * n2 = N : nx >= 2 }
+ 1/3 * #{ n1 * n2 * n3 = N : nx >= 2 }
 1/4 * #{ n1 * n2 * n3 * n4 = N : nx >= 2 }
+ 1/5 * #{ n1 * n2 * n3 * n4 * n5 = N : nx >= 2 }
 ...
which is to say, the count of ways that N can be expressed as an
integer greater than 1, minus half the count of ways that N can be
expressed as two integers multiplied together, each greater than 1,
plus a third of the count of ways N can be expressed as three integers
each greater than 1 multiplied together, and so on is equal to the
following:
0 if N is composite
1 if N is prime
1 / power if N is a prime power
So, for example,
245

+ 1 / 1 * #{ (245) } = +1
 1 / 2 * #{ (5*49), (7*35), (35*7), (49*5) } = 2
+ 1 / 3 * #{ (5*7*7), (7*5*7), (7*7*5) } = +1

0
Thus, 245 is composite.
81

+ 1 / 1 * #{ (81) } = +1
 1 / 2 * #{ (3*27), (9*9), (27*3) } = 3/2
+ 1 / 3 * #{ (3*3*9), (3*9*3), (9*3*3) } = +1
 1 / 4 * #{ (3*3*3*3) } = 1/4

1/4
Thus, 81 factors to a prime to the 4th power.
Section 2: Prime Powers Counting Function

The identity from Section 1 requires, generally, factoring N before we
can find the number of solutions for each count. If, however, we sum
this identity for all values from 2 to N, we find that
#{ n1 <= N : nx >= 2 }
 1/2 * #{ n1 * n2 <= N : nx >= 2 }
+ 1/3 * #{ n1 * n2 * n3 <= N : nx >= 2 }
 1/4 * #{ n1 * n2 * n3 * n4 <= N : nx >= 2 }
+ 1/5 * #{ n1 * n2 * n3 * n4 * n5 <= N : nx >= 2 }
 ...
is equal to the count of primes <= N plus one half the count of primes
less than or equal to N^(1/2) plus one third the count of primes less
than or equal to N^(1/3) and so on, or, in other words,
#{ n1 <= N : n1 prime }
+ 1/2 * #{ n1 <= N^(1/2): n1 prime }
+ 1/3 * #{ n1 <= N^(1/3): n1 prime }
+ 1/4 * #{ n1 <= N^(1/4): n1 prime }
+ 1/5 * #{ n1 <= N^(1/5): n1 prime }
+ ...
Counting these lattice volumes is not trivial, but it can be done
without resorting to factoring.
Section 3: Prime Counting Function

The prime powers coutning function from Section 2 yields precisely the
same values as Riemann's similar function. Thus, we can use the same
techniques, employing a mobius inversion to yield the exact count of
primes less than or equal to N.
Section 4: Lattice Counting

For an expression like
#{ n1 * n2 * ... nx <= N: n1, n2, ... nx >= 2 }
any given set of numbers will show up at most x! times. Additionally,
the smallest value in the set will be at most floor( N^( 1 / x ) ). If
we count the number of values in the lattice from smallest value to
largest, our process can look, very roughly, something like this:
for( a_1 = 2 to N^(1/x) )
for( a_2 = a_1 to ( N^(1/(x1) )/a_1 )
for( a_3 = a_2 to ( N^(1/(x2))/(a_1*a_2) )
...
for( a_(x1) = a_(x2) to ( N^(1/2)/( a_1*a_2*...*a_(x2) ) )
total += b1 + ( N / ( a_1*a_2*...*a_(x1) )  1 ) * b2
where b2 is calculated based on how many times values in the set( a_1,
a_2, ..., a_(x1) ) are equal to each other. This technique can be
vastly sped up by using a wheel.
With my current implementation of lattice counting, which is an area of
research I don't know much about, this yields a prime counting
algorithm that works, at least empirically, in O( N ^ 4/5 + epsilon )
time and O( epsilon ) space.
Section 5: Continuous Volumes Bounding Lattices

As before, with n1, n2, ... nx integers >= 2 and N a constant value,
#{ n1 * n2 <= N } is bounded by the continuous (realvariable) curve
x1*x2 = N, x1 >= 1, x2 >= 1. All valid integer pair solutions to the
first equation are contained entirely by this volume, and only integer
pair solutions from this first equation are contained entirely by this
volume. The integral for this volume is N log N  N + 1.
#{ n1 * n2 * n3 <= N } is bounded by the continuous curve x1*x2*x3 = N,
where, x1, x2, and x3 are all >= 1. The integral for this volume is
N/2 * ( log N )^2  N log N + N  1. It has similar properties to the
first equation in terms of the specific lattice points it bounds.
#{ n1 * n2 * n3 * n4 <= N } is bounded by a volume that is, when
integrated, equal to N/6 * ( log N )^3  N/2 * ( log N )^2 + N log N 
N + 1.
And so on. All of these volumes have similar properties regarding the
lattice points that they bound.
Section 6: Relationship to the Prime Number Theory

If we replace the prime power counting function from section 2,
#{ n1 <= N : nx >= 2 }
 1/2 * #{ n1 * n2 <= N : nx >= 2 }
+ 1/3 * #{ n1 * n2 * n3 <= N : nx >= 2 }
 1/4 * #{ n1 * n2 * n3 * n4 <= N : nx >= 2 }
+ 1/5 * #{ n1 * n2 * n3 * n4 * n5 <= N : nx >= 2 }
+ ...
with the continuous variable volumes bounding each of these lattices as
approximations, we arrive at the following equation:
(  1 + N )
 1/2 * ( 1  N + N log N )
+ 1/3 * (  1 + N  N log N + N/2 ( log N )^2 )
 1/4 * ( 1  N + N log N  N/2 ( log N )^2 + N/6 ( log N )^3 )
+ 1/5 * (  1 + N  N log N + N/2 ( log N )^2  N/6 ( log N )^3 + N/24(
log N )^4 )
...
This value is equal the Logarithmic Integral, Li( N ).
It might be possible one could construct an elementary proof of the
prime number theory based off of these relationships, assuming that all
the steps to this point were proven.
Section 7: Relationship to the Zeroes of the Riemann Zeta Function

The equation from Section 2,
#{ n1 <= N : nx >= 2 }
 1/2 * #{ n1 * n2 <= N : nx >= 2 }
+ 1/3 * #{ n1 * n2 * n3 <= N : nx >= 2 }
 1/4 * #{ n1 * n2 * n3 * n4 <= N : nx >= 2 }
+ 1/5 * #{ n1 * n2 * n3 * n4 * n5 <= N : nx >= 2 }
 ...
is precisely equal to
#{ n1 <= N : n1 prime }
+ 1/2 * #{ n1 <= N^(1/2): n1 prime }
+ 1/3 * #{ n1 <= N^(1/3): n1 prime }
+ 1/4 * #{ n1 <= N^(1/4): n1 prime }
+ 1/5 * #{ n1 <= N^(1/5): n1 prime }
+ ...
which, by Riemann's work, is equal to
Li( N )  Li( N^( each nontrivial zeta zero ) )  ln 2 + tiny integral
Given that the formula involving the bounding continuous volumes from
the preceding section equals Li( N ), we can see that
(  1 + N
 #{ n1 <= N : nx >= 2 } )
 1/2 * ( 1  N + N log N
 #{ n1 * n2 <= N : nx >= 2 } )
+ 1/3 * (  1 + N  N log N + N/2 ( log N )^2
 #{ n1 * n2 * n3 <= N : nx >= 2 } )
 1/4 * ( 1  N + N log N  N/2 ( log N )^2 + N/6 ( log N )^3
 #{ n1 * n2 * n3 * n4 <= N : nx >= 2 } )
+ 1/5 * (  1 + N  N log N + N/2 ( log N )^2  N/6 ( log N )^3 + N/24(
log N )^4
 #{ n1 * n2 * n3 * n4 * n5 <= N : nx >= 2 })
 ...
which represents volumes of the various bounding curves that aren't
contained by lattice squares/cubes/etc underneath them (and which, when
totaled, is the amount that Li( N ) deviates from pi( N ) + 1/2pi(
N^1/2) + 1/3pi( N^1/3) + ... ) is thus equal to
 Li( N^( each nontrivial zeta zero ) )  ln 2 + tiny integral
What repurcussions, if any, this has is unclear to me.
Section 8: Mu Function

For any positive constant integer N, where n1, n2, ... nx are natural
number variables greater than or equal to 2, and where the syntax #{ a
* b <= c } denotes the count of solutions to a * b <= constant c, the
sum
 #{ n1 = N : nx >= 2 }
+ #{ n1 * n2 = N : nx >= 2 }
 #{ n1 * n2 * n3 = N : nx >= 2 }
+ #{ n1 * n2 * n3 * n4 = N : nx >= 2 }
 #{ n1 * n2 * n3 * n4 * n5 = N : nx >= 2 }
+ ...
(which is to say, the negative value of the count of ways that N can be
expressed as 1 integer greater than 1, plus the count of ways that N
can be expressed as 2 integers multiplied together, each greater than
1, minus the count of ways N can be expressed as three integers each
greater than 1 multiplied together, and so on)
is equal to the mobius mu function, where
mu( N ) = 0 if N is not squarefree
1 if N is squarefree and has an even number of factors
1 if N is squarefree and has an odd number of factors
Section 9: Mertens Function

The identity for mu above requires, generally, factoring N to find the
number of solutions for each equation. If, however, we sum this
identity for all values from 2 to N, we find the following:
 #{ n1 <= N : nx >= 2 }
+ #{ n1 * n2 <= N : nx >= 2 }
 #{ n1 * n2 * n3 <= N : nx >= 2 }
+ #{ n1 * n2 * n3 * n4 <= N : nx >= 2 }
 #{ n1 * n2 * n3 * n4 * n5 <= N : nx >= 2 }
+ ...
Calculating the number of solutions for each of these values, while not
simple, can be done without resorting to any factoring. These values
are essentially the number of integer lattice values under various
regular rectangular hyperbola volumes.
This identity is a way of expressing the Mertens Function, the sum of
the mobius mu.
Section 10: d_k

The count of ways a number N can be represented by k integers >= 1
multiplied together, if N in its canonical prime decomposition is
represented by p1^a1 * p2^a2 * ... * px^ax, is equal to
( a1 + k  1 )! / ( a1! * ( k  1 )! )
* ( a2 + k  1 )! / ( a2! * ( k  1 )! )
* ( ... )
* ( ax + k  1 )! / ( ax! * ( k  1 )! )
Section 11: d_k_2

The count of ways a number N can be represented by k integers >= 2
multiplied together, if N in its canonical prime decomposition is
represented by p1^a1 * p2^a2 * ... * px^ax, is equal to
binomial( k, 0 ) * d_k ( N )
 binomial( k, 1 ) * d_(k1)( N )
+ binomial( k, 2 ) * d_(k2)( N )
 ...
and so on until the series terminates.
Section 12: Using d_k_x to calculate Mertens and Pi*

Using the family of d_k_x functions, we can rewrite the previous
results as
Mu( N ) =  d_1_2( N ) + d_2_2( N )  d_3_2( N )
+ d_4_2( N )  ...
Prime Power( N ) = d_1_2( N )  1/2 * d_2_2( N ) + 1/3 * d_3_2( N )
 1/4 * d_4_2( N ) + ...
Thus
Mertens( N ) =
 d_1_2( 1 ) + d_2_2( 1 )  d_3_2( 1 ) + d_4_2( 1 ) 
....
 d_1_2( 2 ) + d_2_2( 2 )  d_3_2( 2 ) + d_4_2( 2 ) 
....
 d_1_2( 3 ) + d_2_2( 3 )  d_3_2( 3 ) + d_4_2( 3 ) 
....
 ...
 d_1_2( N ) + d_2_2( N )  d_3_2( N ) + d_4_2( N ) 
....
and
pi*( N ) =
d_1_2( 1 )  1/2 * d_2_2( 1 ) + 1/3 * d_3_2( 1 )  1/4 * d_4_2( 1 ) +
....
+ d_1_2( 2 )  1/2 * d_2_2( 2 ) + 1/3 * d_3_2( 2 )  1/4 * d_4_2( 2 ) +
....
+ d_1_2( 3 )  1/2 * d_2_2( 3 ) + 1/3 * d_3_2( 3 )  1/4 * d_4_2( 3 ) +
....
....
+ d_1_2( N )  1/2 * d_2_2( N ) + 1/3 * d_3_2( N )  1/4 * d_4_2( N ) +
....
In general, though, while this appears to be true, it is an extremely
slow way to evaluate these functions.
Section 13: The Glaring Omission of Proofs

Clearly, this document contains a lot of conjectures and hypothesises
about an assortment of number theory identities.
And now, the code:
****************************************************
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "conio.h"
#include "time.h"
const double EPSILON = .00000000001;
typedef long long BigInt;
/* A wheel including 19 has 9.6 million entries. */
const int g_wheelLargestPrime = 19;
/* Used for the construction of the wheel  include more primes as
needed,
but this is already enough primes to consume over 75 gigs of RAM */
const int g_primes[] ={ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29
};
int g_wheelCycleEntries;
int g_wheelCyclePeriod;
int g_wheelFirstPrime;
int g_wheelBasePrimes;
int* g_wheelTranslation = 0;
int* g_wheelOffsets = 0;
BigInt g_latticepoints;
BigInt g_minVarValue;
BigInt g_boundary;
BigInt g_scale;
BigInt g_divisor;
BigInt g_lastMax;
int g_variablesLeft;
BigInt g_lastScaleDivisor;
BigInt g_scaleVal;
int g_moo[] = {
0, 1, 1, 1, 0, 1, 1, 1, 0, 0,
1, 1, 0, 1, 1, 1, 0, 1, 0, 1,
0, 1, 1, 1, 0, 0, 1, 0, 0, 1,
1, 1, 0, 1, 1, 1, 0, 1, 1, 1,
0, 1, 1, 1, 0, 0, 1, 1, 0, 0,
0, 1, 0, 1, 0, 1, 0, 1, 1, 1,
0, 1, 1, 0, 0, 1, 1, 1, 0, 1,
1, 1, 0, 1, 1, 0, 0, 1, 1, 1,
0, 0, 1, 1, 0, 1, 1, 1, 0, 1,
0, 1, 0, 1, 1, 1, 0, 1, 0, 0,
0, 1, 1, 1, 0, 1, 1, 1, 0, 1,
1, 1, 0, 1, 1, 1, 0, 0, 1, 1,
0, 0, 1, 1, 0, 0, 0, 1, 0, 1,
1, 1, 0, 1, 1, 0, 0, 1, 1, 1,
0, 1, 1, 1, 0, 1, 1, 0, 0, 1,
0, 1, 0, 0, 1, 1, 0, 1, 1, 1,
0, 1, 0, 1, 0, 1, 1, 1, 0, 0,
1, 0, 0, 1, 1, 0, 0, 1, 1, 1,
0, 1, 1, 1, 0, 1, 1, 1, 0, 0,
1, 1, 0, 1, 1, 1, 0, 1, 0, 1,
0, 1, 1, 1, 0, 1, 1, 0, 0, 1,
1, 1, 0, 1, 1, 1, 0, 1, 1, 1,
0, 1, 1, 1, 0, 0, 1, 1, 0, 1,
1, 1, 0, 1, 0, 1, 0, 1, 1, 1,
0, 1, 0, 0, 0, 0, 1, 1, 0, 1,
0, 1, 0, 1, 1, 1, 0,
};
/* Note that with 64 bit ints, we can't go above factorial( 20 )
anyway. */
BigInt g_factorial[] = {
0, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800,
479001600,
6227020800, 87178291200, 1307674368000, 20922789888000,
355687428096000,
6402373705728000, 121645100408832000, 2432902008176640000
};
inline BigInt InversePower( BigInt x, BigInt y ){
return ( (BigInt)( pow( (double)x + EPSILON, ( 1.0 / (double)y ) ) +
EPSILON ) );
}
inline int GetwheelCyclePeriod( int cap ){
int val = 1;
int i = 0;
while( g_primes[ i ] <= cap ){
val *= g_primes[ i ];
i++;
}
return val;
}
inline int GetFirstIncludedPrime( int cap ){
int i = 0;
while( g_primes[ i ] <= cap ){
i++;
}
return g_primes[ i ];
}
inline int GetBasePrimes( int cap ){
int i = 0;
while( g_primes[ i ] <= cap ){
i++;
}
return i;
}
inline void IncrementWheel( int &offset ){
offset++;
if( offset >= g_wheelCycleEntries ){
offset = 0;
}
}
void MakeWheel( int cap ){
g_wheelBasePrimes = GetBasePrimes( cap );
g_wheelCyclePeriod = GetwheelCyclePeriod( cap );
g_wheelCycleEntries = 0;
int cur = 0;
int offset = 1;
int* wheelBase = 0;
wheelBase = ( int* )malloc( g_wheelCyclePeriod * sizeof( int ) );
g_wheelTranslation = ( int* )malloc( ( g_wheelCyclePeriod + 1 ) *
sizeof( int ) );
g_wheelOffsets = ( int * )malloc( g_wheelCyclePeriod * sizeof( int )
);
g_wheelFirstPrime = GetFirstIncludedPrime( cap );
for( int i = 0; i < g_wheelCyclePeriod; i++ ){
wheelBase[ i ] = 1;
for( int j = 2; j <= cap; j++ ){
if( !( ( i + 1 ) % j ) ){
wheelBase[ i ] = 0;
break;
}
}
}
while( cur < g_wheelCyclePeriod ){
if( wheelBase[ cur ] && cur != 0 ){
g_wheelOffsets[ g_wheelCycleEntries ] = offset + 1;
offset = 0;
g_wheelCycleEntries++;
}else{
offset++;
}
cur++;
}
g_wheelOffsets[ g_wheelCycleEntries ] = 2;
g_wheelCycleEntries++;
int total = 0;
g_wheelTranslation[ 0 ] = 0;
for( i = 0; i < g_wheelCyclePeriod; i++ ){
if( i && wheelBase[ i  1 ] ){
total++;
}
g_wheelTranslation [ i + 1 ] = total;
}
free( wheelBase );
}
/* This function calculates how many entries the wheel leaves
in the range from (rangeStart, rangeStop].*/
inline BigInt CountWheelEntries( BigInt rangeStart, BigInt rangeEnd ){
rangeEnd++;
int a = rangeStart % g_wheelCyclePeriod;
int b = rangeEnd % g_wheelCyclePeriod;
return ( rangeEnd  b  rangeStart + a ) / g_wheelCyclePeriod *
g_wheelCycleEntries + g_wheelTranslation[ b ]  g_wheelTranslation[ a
] ;
}
void CountHyperbolaLattice_2_Variables( void ){
BigInt finalBoundary = g_boundary / g_minVarValue;
BigInt boundaryRoot = (BigInt)( sqrt( (double)finalBoundary ) +
EPSILON );
/* For if the final two digits happen to be the same. */
g_latticepoints += g_scale / ( g_divisor * ( g_divisor + 1 ) );
/* Leading digit is same, final digit is not. */
g_latticepoints +=
( CountWheelEntries( g_minVarValue, finalBoundary / g_minVarValue ) 
1 )
* ( g_scale / g_divisor );
/* For if the final two digits happen to be the same,
but both differ from the previous. */
g_latticepoints +=
( CountWheelEntries( g_minVarValue, boundaryRoot )  1 ) * ( g_scale
/ 2 );
/* Both digits differ from all other digits  This is the hellish evil
loop of portentious doom. */
int curWheelOffset = g_wheelTranslation[ g_minVarValue %
g_wheelCyclePeriod ];
BigInt curLeadingVar = g_minVarValue + g_wheelOffsets[ curWheelOffset
];
BigInt subTotal = 0;
IncrementWheel( curWheelOffset );
while( curLeadingVar <= boundaryRoot ){
subTotal += CountWheelEntries( curLeadingVar, finalBoundary /
curLeadingVar )  1;
curLeadingVar += g_wheelOffsets[ curWheelOffset ];
IncrementWheel( curWheelOffset );
}
g_latticepoints += subTotal * g_scale;
}
void CountHyperbolaLattice_3_Variables( BigInt hyperbolaBoundary,
BigInt minVarValue ){
BigInt maxVarValue = InversePower( hyperbolaBoundary, 3 );
int curWheelOffset = g_wheelTranslation[ minVarValue %
g_wheelCyclePeriod ];
g_boundary = hyperbolaBoundary;
g_minVarValue = minVarValue;
g_scale = g_scaleVal / g_lastScaleDivisor;
g_divisor = g_lastScaleDivisor + 1;
CountHyperbolaLattice_2_Variables();
g_minVarValue += g_wheelOffsets[ curWheelOffset ];
IncrementWheel( curWheelOffset );
g_scale = g_scaleVal;
g_divisor = 2;
while( g_minVarValue <= maxVarValue ){
CountHyperbolaLattice_2_Variables();
g_minVarValue += g_wheelOffsets[ curWheelOffset ];
IncrementWheel( curWheelOffset );
}
}
void CountHyperbolaLattice_X_Variables( BigInt hyperbolaBoundary,
BigInt minVarValue ){
BigInt maxVarValue = InversePower( hyperbolaBoundary,
g_variablesLeft );
/* Save global variables that will be restored at end of function */
BigInt scaleVal = g_scaleVal;
BigInt lastScaleDivisor = g_lastScaleDivisor;
int curWheelOffset = g_wheelTranslation[ minVarValue %
g_wheelCyclePeriod ];
g_variablesLeft;
g_lastScaleDivisor = lastScaleDivisor + 1;
g_scaleVal = scaleVal / lastScaleDivisor;
if( g_variablesLeft == 3 ){
CountHyperbolaLattice_3_Variables( hyperbolaBoundary / minVarValue,
minVarValue );
}else{
CountHyperbolaLattice_X_Variables( hyperbolaBoundary / minVarValue,
minVarValue );
}
g_lastScaleDivisor = 2;
g_scaleVal = scaleVal;
minVarValue += g_wheelOffsets[ curWheelOffset ];
IncrementWheel( curWheelOffset );
while( minVarValue <= maxVarValue ){
if( g_variablesLeft == 3 ){
CountHyperbolaLattice_3_Variables( hyperbolaBoundary / minVarValue,
minVarValue );
}else{
CountHyperbolaLattice_X_Variables( hyperbolaBoundary / minVarValue,
minVarValue );
}
minVarValue += g_wheelOffsets[ curWheelOffset ];
IncrementWheel( curWheelOffset );
}
/* Restore global variables */
g_lastScaleDivisor = lastScaleDivisor;
g_variablesLeft++;
}
BigInt CountHyperbolaLattice( BigInt hyperbolaBoundary, int
hyperbolaVariables ){
g_latticepoints = 0;
g_variablesLeft = hyperbolaVariables;
g_lastScaleDivisor = 1;
g_scaleVal = g_factorial[ hyperbolaVariables ];
if( hyperbolaBoundary < (BigInt)pow( (double)g_wheelFirstPrime,
(double)hyperbolaVariables ) ){
return 0;
}
switch( hyperbolaVariables ){
case 1:
g_latticepoints = CountWheelEntries( g_wheelFirstPrime,
hyperbolaBoundary );
break;
case 2:
/* CountHyperbolaLattice_2_Variables expects a number of global
variables
to be initialized when it is called, which generally happens in
CountHyperbolaLattice_3_Variables. We have to do it manually
here. */
g_minVarValue = g_wheelFirstPrime;
g_boundary = g_wheelFirstPrime * hyperbolaBoundary;
g_scale = 2;
g_divisor = 1;
CountHyperbolaLattice_2_Variables();
break;
case 3:
CountHyperbolaLattice_3_Variables( hyperbolaBoundary,
g_wheelFirstPrime );
break;
default:
CountHyperbolaLattice_X_Variables( hyperbolaBoundary,
g_wheelFirstPrime );
break;
}
return g_latticepoints;
}
BigInt CountPrimes( BigInt numLimit ){
int maxPower = ( int )( log( ( double )numLimit + EPSILON ) / log (
( double )g_wheelFirstPrime + EPSILON ) + EPSILON ) + 1;
double total = 0.0;
int oldClock = (int)clock();
int totalTime = 0;
for( int curPower = 1; curPower < maxPower; curPower++ ){
if( !g_moo[ curPower ] ){
continue;
}
BigInt curMax = InversePower( numLimit, curPower );
double subTotal = 0.0;
BigInt hyperbolaEntries = 1;
double sign = 1;
while( 1 ){
double temp = sign / hyperbolaEntries;
sign *= 1;
double v2 = (double)CountHyperbolaLattice( curMax, hyperbolaEntries
);
temp *= v2;
if( temp == 0.0 ){
break;
}
subTotal += temp;
hyperbolaEntries++;
int newClock = (int)clock();
totalTime += newClock  oldClock;
oldClock = newClock;
}
subTotal /= curPower * g_moo[ curPower ];
total += subTotal;
}
total += g_wheelBasePrimes;
/* the .5 is to prevent truncation errors  but it's clearly sloppy */
return (BigInt)( total + 0.5 );
}
BigInt main(int argc, char* argv){
MakeWheel( g_wheelLargestPrime );
int oldClock = (int)clock();
int lastDif = 0;
for( BigInt i = 10; i <= 100000000000000; i *= 10 ){
printf( "%20I64d(%4.1f): ", i, log( (double)i ) );
BigInt total = CountPrimes( i );
int newClock = (int)clock();
printf( " %20I64d %8d : %4d: %f\n",
total, newClock  oldClock, ( newClock  oldClock ) / CLK_TCK,
( lastDif ) ? (double)( newClock  oldClock ) / (double)lastDif :
0.0 );
lastDif = newClock  oldClock;
oldClock = newClock;
}
getch();
return 0;
} 

Back to top 


Pubkeybreaker science forum Guru
Joined: 24 Mar 2005
Posts: 333

Posted: Mon Feb 20, 2006 10:14 pm Post subject:
Re: Prime Counting: O(.8+e) time, O(e) space. Can this be improved?



<snip>
Look up the "MeisselLehmer" method. This method is elementary. I
believe (but am unsure) that this method achieves O(N^3/5) time.
There are other methods (non elementary!) that achieve O(n^1/2) time
and space. 

Back to top 


***** science forum beginner
Joined: 11 Feb 2006
Posts: 5

Posted: Mon Feb 20, 2006 11:02 pm Post subject:
Re: Prime Counting: O(.8+e) time, O(e) space. Can this be improved?



Quote:  snip
Look up the "MeisselLehmer" method. This method is
elementary. I
believe (but am unsure) that this method achieves
O(N^3/5) time.
There are other methods (non elementary!) that
achieve O(n^1/2) time
and space.

not that im going to do it, but i think the OP was looking for methods to speed up HIS algorithm, which he said he put a year of work into... and specifically wrote
"aside from
swapping it out with completely dissimilar algorithms, of course?"
i dont know what [if any] they are in this case, but there can be good reasons for working on things even if more efficient ways are well known. 

Back to top 


Prime_Count@hotmail.com science forum beginner
Joined: 20 Feb 2006
Posts: 2

Posted: Tue Feb 21, 2006 10:02 pm Post subject:
Re: Prime Counting: O(.8+e) time, O(e) space. Can this be improved?



<snip>
Quote:  i dont know what [if any] they are in this case, but there can be good reasons for working on things even if more efficient ways are well known.

Thanks  that's exactly right.
In this particular case, my prime counting algorithm relies
substanitally on lattice point counting, and it's an area I'm by no
means an expert at. So while I know that using methods I happen to
understand can make this algorithm execute in O(.8+e) time, I want to
know if anyone else might know of techniques that would make it execute
faster.
Nathan McKenzie 

Back to top 


Pubkeybreaker science forum Guru
Joined: 24 Mar 2005
Posts: 333

Posted: Wed Feb 22, 2006 11:56 am Post subject:
Re: Prime Counting: O(.8+e) time, O(e) space. Can this be improved?



"So while I know that using methods I happen to
understand can make this algorithm execute in O(.8+e) time, I want to
know if anyone else might know of techniques that would make it execute
faster. "
No flame intended, but trying to reinvent a square wheel is usually
counterproductive. 

Back to top 


Google


Back to top 



The time now is Fri Apr 26, 2019 2:26 pm  All times are GMT

