Re: As the Crow flies.

On 2008-10-22, spintronic <spintronic@xxxxxxxxxxx> wrote:
On Oct 22, 1:48 am, Mark VandeWettering <wetter...@xxxxxxxxxxx> wrote:
On 2008-10-21, spintronic <spintro...@xxxxxxxxxxx> wrote:

Tell me, what does "p1*p2*p3..." mean?

It means the product of the first, second and third primes.

That is a feature of Legendre's (rather impractical) technique.  It is a
property that isn't shared by Lehmer's technique.


Of course it is.

a = pi(997 ^ 1/4) = 5 = 3 (primes)
& = 8 (operations)

b = pi(997 ^ 1/2) = 31 = 10 (Primes)
& all its (operations)(Btw, this is a relatively number of operations)

Your notation is actually very confusing, as there are things on either
side of the "=" which are not equal. It would seem that you mean:

a = pi(997^1/4) = pi(5) = 3
b = pi(997^1/2) = pi(31) = 10

In any real implementation, there is signicant overlap between these
two operations. Computing pi(x) and pi(x+1) aren't really two separate
calculations:

Just to but in. But 10 + 8 is 1 more Operation than mine takes.

Then you have
c = pi(997 ^ 1/3) = 7 = 4

I'm curious: just what do you think is an "operation"?

In computer science, we have a standard way of talking about algorithms
to determine their relative efficiency. We use things like O(n)
measures to describe space or time measures. These are represented as
functions of input size. These measure the amount of work done by an
algorithm of varying size, and in particular, how that work grows as
the size of the problem grows. Broadly speaking, most conventional
sieves are very nearly O(n) to find the primes < n, because it must
examine all primes < n, and there are very nearly O(n) primes less than
n (actually, n/logn, but what's a factor of logn between friends). Good
implementations of Lehmer's idea take less, typically O(n^2/3). Still,
if you look at practical implementations, for ranges up to maybe 1E9 or
so, sieving is still a practical algorithm: it runs very fast, since it
is amenable to a lot of optimizations relative to the kinds of machines
that they typically run on. It would be idiocy to go to the trouble of
implementing Lehmer's algorithm for x around 1e3, heck, it's hardly even
worth implementing a sieve for such values: you could just build a table
and "compute" such values in constant time.

You've made a bunch of claims about how fast your algorithm is. You've
neither presented an implementation that works for comparison, nor
presented anything like an analysis of it's asymptotic run time. You've
given no reason for us to believe that "your algorithm" is faster either
abstractly in the limit or practically measured by clocktime than any
reasonable implementation of standard techniques.

Mark

.

Relevant Pages

  • Re: As the Crow flies.
    ... Which is how many my algorithm took. ... be silly indeed to use Lehmer's algorithm to count primes up to 997. ... that's a meaningless endorsement of your technique. ...
    (talk.origins)
  • Re: As the Crow flies.
    ... Which is how many my algorithm took. ... be silly indeed to use Lehmer's algorithm to count primes up to 997. ... that's a meaningless endorsement of your technique. ...
    (talk.origins)
  • Re: Math errors in book Secret Life of Numbers
    ... his students have proven that primes can be found in polynomial time. ... For practical purposes the algorithm is, admittedly, still too ... that in practice, it always was solved in polynomial time using the ... the simplex method is not a polynomial-time algorithm. ...
    (sci.math.research)
  • Re: I was right, surrogate factoring proof
    ... primes divide n -- at most I'll have to look through sqrt/ ... But don't forget that's included in the cost of the algorithm! ... if surrogate factoring ever becomes ... two values are congruent modulo p, and hopefully not congruent modulo n/p. ...
    (sci.math)
  • Re: I was right, surrogate factoring proof
    ... primes divide n -- at most I'll have to look through sqrt/ ... But don't forget that's included in the cost of the algorithm! ... if surrogate factoring ever becomes ... two values are congruent modulo p, and hopefully not congruent modulo n/p. ...
    (sci.crypt)