 |
|
| Science Forum Index » Mathematics Forum » Prime counting, a real test |
|
Page 1 of 1 |
|
| Author |
Message |
| Guest |
 Posted: Thu Mar 03, 2005 9:34 pm |
|
|
|
|
There are people who are spending effort to promote the belief that my
prime counting function is slow. These people have even put up
webpages.
However, the reality is that I like one form of my own discovery, which
is very slow, but that isn't the form to do a fair test, as the sieve
form is more in line with other prime counting methods, like Legendre's
or Meissel's that use sieves.
The sieve form is to use the following dS partial sieve equation
dS(x,p_i) = p(x/p_1, p_i - 1) - (i-1)
and you calculate dS from i=1, as p_1 is just 2, up until i of the
highest prime less than the square root of x, and you sum all the dS
values together to get
S(x,p_i), and then
p(x,p_i) = floor(x) - S(x,p_i) - 1
where p(x,p_i) = pi(x)
as pi(x) is the traditional way mathematicians write the prime counting
function.
That is the simple and faster sieve form.
I suggest those of you who see webpages or posts claiming my discovery
is very slow check to see if they even discuss the sieve form, and if
they do not, you can know that, yes, there are math people deliberately
lying to you.
Why do they lie to you?
Probably at least partly because they think they can get away with it.
James Harris |
|
|
| Back to top |
|
|
|
| karllarc |
| Posted: Thu Mar 03, 2005 11:29 pm |
|
|
|
Guest
|
jstevh@msn.com wrote:
[quote:28c3dd4eaa]There are people who are spending effort to promote the belief that
my
prime counting function is slow. These people have even put up
webpages.
However, the reality is that I like one form of my own discovery,
which
is very slow, but that isn't the form to do a fair test, as the sieve
form is more in line with other prime counting methods, like
Legendre's
or Meissel's that use sieves.
The sieve form is to use the following dS partial sieve equation
dS(x,p_i) = p(x/p_1, p_i - 1) - (i-1)
and you calculate dS from i=1, as p_1 is just 2, up until i of the
highest prime less than the square root of x, and you sum all the dS
values together to get
S(x,p_i), and then
p(x,p_i) = floor(x) - S(x,p_i) - 1
where p(x,p_i) = pi(x)
as pi(x) is the traditional way mathematicians write the prime
counting
function.
That is the simple and faster sieve form.
I suggest those of you who see webpages or posts claiming my
discovery
is very slow check to see if they even discuss the sieve form, and if
they do not, you can know that, yes, there are math people
deliberately
lying to you.
Why do they lie to you?
Probably at least partly because they think they can get away with
it.
James Harris
[/quote:28c3dd4eaa]
Dude, get a clue. I didn't send you to a page that mentioned your
function. I sent you to a page where a guy was demonstating how to
implement an existing well known algorithm to find primes at a very
fast pace. He used some fairly clever programming concepts to make it
quite fast. He also was able to find all these primes without using a
list of primes initialy, just like you said your little function does.
He actually shows that his ideas work, and work pretty well. |
|
|
| Back to top |
|
|
|
| Mark Nudelman |
| Posted: Fri Mar 04, 2005 1:29 pm |
|
|
|
Guest
|
jstevh@msn.com wrote:
[quote:b398ee1220]The sieve form is to use the following dS partial sieve equation
dS(x,p_i) = p(x/p_1, p_i - 1) - (i-1)
and you calculate dS from i=1, as p_1 is just 2, up until i of the
highest prime less than the square root of x, and you sum all the dS
values together to get
S(x,p_i), and then
p(x,p_i) = floor(x) - S(x,p_i) - 1
where p(x,p_i) = pi(x)
as pi(x) is the traditional way mathematicians write the prime
counting function.
[/quote:b398ee1220]
Could you show an example of how this works for some particular number?
Maybe a simple case like x=5. There are many things that I don't understand
about this presentation, among them:
1. It's strange that you write dS as a function of p_i. I would have said
that it's a function of i, since you're using both i and p_i in the
definition.
2. Which value of i is the upper bound of the sum of dS's? Is i the largest
prime < sqrt(x), or is it the i such that p_i is the largest prime <
sqrt(x), or something else? Your statement "the i of the highest prime ..."
isn't very clear.
3. You add up a bunch of dS values, for different i's, and then you get an S
value, but you write S as a function of p_i. How can S be a function of p_i
when you've added up a bunch of different dS(x,p_i) values to get it?
4. How do you finally arrive at pi(x)? You say pi(x) = p(x,p_i), but again
there's that p_i in the equation, and I don't know which p_i you're
referring to.
5. It's also rather confusing that you have a function named p and some
variables named p_i. It would be better to rename one of them.
So I tried to make some assumptions about what you might mean and work
through an example. Say x=5. Then I start with i=1:
dS(x,p_1) = dS(5,2) = p(5/2,1)
Now I want to calculate p(5/2,1), so I go to the definiton of p and find
p(x,p_i) = floor(x) - S(x,p_i) - 1
But the second parameter in my p(5/2,1) is not any p_i value (1 is not a
prime). So now what do I do? Maybe this parameter isn't supposed to read
p_i. So let's try just saying
p(5/2,1) = floor(5/2) - S(5/2,1) - 1
Now I need to calculate S(5/2,1) but to do that I've got to go start adding
up a whole new set of dS values? How does this ever terminate?
If you could show an example, it might make this all clear and allow someone
to implement it.
BTW, why are you asking other people to implement and test this? Aren't you
able to do it yourself? A complete program that implements your function
would be even better than an example.
--Mark |
|
|
| Back to top |
|
|
|
| The Last Danish Pastry |
| Posted: Fri Mar 04, 2005 1:52 pm |
|
|
|
Guest
|
"Mark Nudelman" <markn@greenwoodsoftware.com> wrote in message
news:F8-dnVYjPMluNbXfRVn-rw@comcast.com...
[quote:44dcab5a4f]jstevh@msn.com wrote:
The sieve form is to use the following dS partial sieve equation
dS(x,p_i) = p(x/p_1, p_i - 1) - (i-1)
and you calculate dS from i=1, as p_1 is just 2, up until i of the
highest prime less than the square root of x, and you sum all the dS
values together to get
S(x,p_i), and then
p(x,p_i) = floor(x) - S(x,p_i) - 1
where p(x,p_i) = pi(x)
as pi(x) is the traditional way mathematicians write the prime
counting function.
Could you show an example of how this works for some particular number?
Maybe a simple case like x=5. There are many things that I don't
understand
about this presentation, among them:
1. It's strange that you write dS as a function of p_i. I would have said
that it's a function of i, since you're using both i and p_i in the
definition.
2. Which value of i is the upper bound of the sum of dS's? Is i the
largest
prime < sqrt(x), or is it the i such that p_i is the largest prime
sqrt(x), or something else? Your statement "the i of the highest prime
...."
isn't very clear.
3. You add up a bunch of dS values, for different i's, and then you get an
S
value, but you write S as a function of p_i. How can S be a function of
p_i
when you've added up a bunch of different dS(x,p_i) values to get it?
4. How do you finally arrive at pi(x)? You say pi(x) = p(x,p_i), but
again
there's that p_i in the equation, and I don't know which p_i you're
referring to.
5. It's also rather confusing that you have a function named p and some
variables named p_i. It would be better to rename one of them.
So I tried to make some assumptions about what you might mean and work
through an example. Say x=5. Then I start with i=1:
dS(x,p_1) = dS(5,2) = p(5/2,1)
Now I want to calculate p(5/2,1), so I go to the definiton of p and find
p(x,p_i) = floor(x) - S(x,p_i) - 1
But the second parameter in my p(5/2,1) is not any p_i value (1 is not a
prime). So now what do I do? Maybe this parameter isn't supposed to read
p_i. So let's try just saying
p(5/2,1) = floor(5/2) - S(5/2,1) - 1
Now I need to calculate S(5/2,1) but to do that I've got to go start
adding
up a whole new set of dS values? How does this ever terminate?
If you could show an example, it might make this all clear and allow
someone
to implement it.
BTW, why are you asking other people to implement and test this? Aren't
you
able to do it yourself? A complete program that implements your function
would be even better than an example.
[/quote:44dcab5a4f]
Two and a half years ago I described a version of James's algorithm in:
http://groups-beta.google.com/group/sci.math/msg/b59d5039904873fc
His current version my be somewhat different, but the article may be
helpful.
--
Clive Tooth
http://www.clivetooth.dk |
|
|
| Back to top |
|
|
|
| Randy Poe |
| Posted: Fri Mar 04, 2005 2:09 pm |
|
|
|
Guest
|
jstevh@msn.com wrote:
[quote:67f304bdc6]There are people who are spending effort to promote the belief that
my
prime counting function is slow. These people have even put up
webpages.
However, the reality is that I like one form of my own discovery,
which
is very slow, but that isn't the form to do a fair test, as the sieve
form is more in line with other prime counting methods, like
Legendre's
or Meissel's that use sieves.
[/quote:67f304bdc6]
Isn't the obvious step for you to post some runtime
results to illustrate how fast your "fast" method is?
On the one side, we have people claiming your algorithm
is slow and posting data. On the other, we have you claiming
your algorithm is fast and posting no data. Do you have
data?
Of particular interest is how it scales as a function
of N, compared to other methods.
- Randy |
|
|
| Back to top |
|
|
|
| Christian Bau |
| Posted: Fri Mar 04, 2005 6:14 pm |
|
|
|
Guest
|
In article <1109903661.239048.202160@z14g2000cwz.googlegroups.com>,
jstevh@msn.com wrote:
[quote:c0b81c5fb4]I suggest those of you who see webpages or posts claiming my discovery
is very slow check to see if they even discuss the sieve form, and if
they do not, you can know that, yes, there are math people deliberately
lying to you.
[/quote:c0b81c5fb4]
The fastest version that you posted was one thousand times slower for
large N than the fastest version I published. The time you have to beat
is eight hours for pi (10^19) on a 733 MHz PowerPC. Just post your
times. |
|
|
| Back to top |
|
|
|
| Guest |
| Posted: Fri Mar 04, 2005 6:21 pm |
|
|
|
|
karllarc wrote:
<deleted>
[quote:8da0c63f2e]
Dude, get a clue. I didn't send you to a page that mentioned your
function. I sent you to a page where a guy was demonstating how to
implement an existing well known algorithm to find primes at a very
fast pace. He used some fairly clever programming concepts to make it
quite fast. He also was able to find all these primes without using a
list of primes initialy, just like you said your little function
does.
He actually shows that his ideas work, and work pretty well.
[/quote:8da0c63f2e]
Dude you get a clue. I looked at the page.
I have a program: PrimeCountH.java
Get it, run it, compare it against everything he tried.
Gain some enlightenment.
Oh to get my program just do a Google search on PrimeCountH.java, and
you should find it somewhere.
Yeah, it's like that.
James Harris |
|
|
| Back to top |
|
|
|
| Guest |
| Posted: Fri Mar 04, 2005 6:42 pm |
|
|
|
|
Mark Nudelman wrote:
[quote:ae3dbb6476]jstevh@msn.com wrote:
The sieve form is to use the following dS partial sieve equation
dS(x,p_i) = p(x/p_1, p_i - 1) - (i-1)
and you calculate dS from i=1, as p_1 is just 2, up until i of the
highest prime less than the square root of x, and you sum all the
dS
values together to get
S(x,p_i), and then
p(x,p_i) = floor(x) - S(x,p_i) - 1
where p(x,p_i) = pi(x)
as pi(x) is the traditional way mathematicians write the prime
counting function.
Could you show an example of how this works for some particular
number?
Maybe a simple case like x=5. There are many things that I don't
understand
about this presentation, among them:
[/quote:ae3dbb6476]
Oh yeah, sure. Let's do pi(10), which is the classical way of writing
it, as with my prime counting function it's p(10,3).
p(10,3) = floor(10) - S(10, 3) - 1
S(x,3) is the sum of dS(10,2) and dS(10,3).
dS(10,2) = p(10/2, 1) - (1 - 1) = p(5,1)
and
p(5,1) = floor(5) - S(5,1) - 1
and since 1 is less than 2 there is no recursion so S(5,1) = 0, which
means that
p(5,1) = 5 - 1 = 4, so
dS(10,2) = 4
and what is that actually? Well it's the count of even composites up
to and including 10.
dS(10,3) = p(10/3, 2) - (2 - 1) = p(3 1/3, 2) - 1
p(3 1/3, 2) = floor(3 1/3) - S(3 1/3, 2) - 1
S(3 1/3, 2) = dS(3 1/3, 2)
dS(3 1/3, 2) = p(10/6, 1) - (1 - 1) = 0
so
p(3 1/3, 2) = 3 - 1 = 2, so
dS(10,3) = 2 - 1 = 1, so
S(10,3) = 5, and
p(10,3) = 10 - 5 - 1 = 4
and I did it the long hard way with a lot of the recursion.
Notice that dS(x, p_i) is just the count of composites up to and
including x that have p_i as a factor that do NOT have any primes less
than p_i as a factor, so dS(10, 3) is easy as that is just counting 9.
And dS(10,2) is easy as that's just the count of even composites.
[quote:ae3dbb6476]
1. It's strange that you write dS as a function of p_i. I would have
said
that it's a function of i, since you're using both i and p_i in the
definition.
[/quote:ae3dbb6476]
I'm using the sieve function, whereas the fully mathematicized function
has
dS(x,y)
where y is not necessarily prime, but notice an interesting and
important feature as the dS(x,y) function is a count of composites that
have y as a factor that do NOT have any primes (or any naturals other
than 1) less than y as a factor, so necessarily if y is composite
dS(x,y) is 0.
So, the dS function is a function of x and y, but it has a unique
feature in that if y is not prime, it's equal to 0.
I actually tossed out p_i in one post when I put up the sieve form as I
just screwed up but was thinking like you are that it's actually a
function of i, and that was just wrong.
Even in sieve form, the function needs the actual prime, not the number
of the prime.
[quote:ae3dbb6476]2. Which value of i is the upper bound of the sum of dS's? Is i the
largest
prime < sqrt(x), or is it the i such that p_i is the largest prime
sqrt(x), or something else? Your statement "the i of the highest
prime ..."
isn't very clear.
[/quote:ae3dbb6476]
i is the number of the largest prime
For instance, for 10, i equals 2, as the largest prime less than
sqrt(10) is 3, and it is the second prime.
[quote:ae3dbb6476]3. You add up a bunch of dS values, for different i's, and then you
get an S
value, but you write S as a function of p_i. How can S be a function
of p_i
when you've added up a bunch of different dS(x,p_i) values to get it?
[/quote:ae3dbb6476]
Well if it helps you change the letter, like you can call it j for S.
I'm actually following a typical convention as if you have, using some
calculus,
ds/dx = x^2, so s' is a function of x,
you don't change the letter when talking about the integral.
So you have s = x^3/3.
S(x,y) is the discrete sum of dS(x,y)
and
S(x, p_i) is the discrete sum of dS(x, p_i)
so it works for me. If it doesn't for you, change the letter.
[quote:ae3dbb6476]4. How do you finally arrive at pi(x)? You say pi(x) = p(x,p_i), but
again
there's that p_i in the equation, and I don't know which p_i you're
referring to.
[/quote:ae3dbb6476]
See demonstration.
[quote:ae3dbb6476]5. It's also rather confusing that you have a function named p and
some
variables named p_i. It would be better to rename one of them.
[/quote:ae3dbb6476]
I've called my prime counting function p(x,y) for a while now, so I'd
say change the other.
The p is for "prime".
[quote:ae3dbb6476]So I tried to make some assumptions about what you might mean and
work
through an example. Say x=5. Then I start with i=1:
dS(x,p_1) = dS(5,2) = p(5/2,1)
Now I want to calculate p(5/2,1), so I go to the definiton of p and
find
p(x,p_i) = floor(x) - S(x,p_i) - 1
But the second parameter in my p(5/2,1) is not any p_i value (1 is
not a
prime). So now what do I do? Maybe this parameter isn't supposed to
read
p_i. So let's try just saying
p(5/2,1) = floor(5/2) - S(5/2,1) - 1
Now I need to calculate S(5/2,1) but to do that I've got to go start
adding
up a whole new set of dS values? How does this ever terminate?
[/quote:ae3dbb6476]
Well, look at my example, and you see that if S doesn't have any values
to sum, then it's just 0.
So S(x,1) = 0.
[quote:ae3dbb6476]If you could show an example, it might make this all clear and allow
someone
to implement it.
[/quote:ae3dbb6476]
Cool. Done.
[quote:ae3dbb6476]BTW, why are you asking other people to implement and test this?
Aren't you
able to do it yourself? A complete program that implements your
function
would be even better than an example.
--Mark
[/quote:ae3dbb6476]
I've been there, done that, and I'm just correcting some knuckleheads
who are putting up webpages claiming things that aren't true.
Do a search on "prime counting function" to see what I mean.
And I do have a program that implements an even more advanced sieve
form, and that program is PrimeCountH.java, and you should be able to
find it with a Google search.
James Harris |
|
|
| Back to top |
|
|
|
|
|
All times are GMT - 5 Hours
The time now is Fri Dec 04, 2009 2:20 am
|
|