FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math
Prime Counting: O(.8+e) time, O(e) space. Can this be improved?
Post new topic   Reply to topic Page 1 of 1 [5 Posts] View previous topic :: View next topic
Author Message
Prime_Count@hotmail.com
science forum beginner


Joined: 20 Feb 2006
Posts: 2

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

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/(x-1) )/a_1 )
for( a_3 = a_2 to ( N^(1/(x-2))/(a_1*a_2) )
...
for( a_(x-1) = a_(x-2) to ( N^(1/2)/( a_1*a_2*...*a_(x-2) ) )
total += b1 + ( N / ( a_1*a_2*...*a_(x-1) ) - 1 ) * b2

where b2 is calculated based on how many times values in the set( a_1,
a_2, ..., a_(x-1) ) 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 (real-variable) 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 non-trivial 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 non-trivial 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_(k-1)( N )
+ binomial( k, 2 ) * d_(k-2)( 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

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

<snip>

Look up the "Meissel-Lehmer" 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

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

Quote:
snip

Look up the "Meissel-Lehmer" 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

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

<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

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

"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
counter-productive.
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [5 Posts] View previous topic :: View next topic
The time now is Thu Nov 15, 2018 11:24 pm | All times are GMT
Forum index » Science and Technology » Math
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts SRT , GRT and Minkowski space . socratus Relativity 1 Sun Jan 06, 2008 9:49 pm
No new posts Undestanding SR - examination time. Nicolaas Vroom Relativity 14 Thu Jul 20, 2006 4:00 pm
No new posts equilateral triangles in space, and cyclohexane David Madore Math 0 Thu Jul 20, 2006 1:05 pm
No new posts Homology of a certain space question James1118 Math 2 Wed Jul 19, 2006 9:22 pm
No new posts Space-time and time dilation Henry Haapalainen Relativity 40 Sun Jul 16, 2006 9:58 pm

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0209s ][ Queries: 16 (0.0032s) ][ GZIP on - Debug on ]