John said:
Yes; the fact that he was accusing me of being bad at math.
I wasn't accusing you, I was analysing your arguments.
Well, to start with, he basically accused Wikipedia of having the
integral of ln(x) wrong.
- You said: "integral of log x is log x - x"
- Wikipedia correctly says
(
http://en.wikipedia.org/wiki/List_of_integrals_of_logarithmic_functions)
"int ln(cx) dx = x * ln (cx) - x"
For our case c=1, this is the same as I said ("Furthermore, the integral of log
x is not lox x - x, but rather x * log x - x. )
He also correctly stated that an average of a set exceeds 1/4 the size
of the set, but thereby was trying to imply that the optimization sucked
I didn't say that anything sucked. What optimisation? Starting with the square?
We all know that this does not suck. It is standard.
because something was therefore O(N) in the total number range instead
of O(log N).
I was saying "something was O(N)"? What is something? Do you mean Omega(N)?
The set was of primes, and the size of that is O(log N), so
1/4 of that is O(log N).
The average over any set of positive integers of cardinality k is at least
Omega(k). You said: "The average prime from this set will be O(1)". This is
obviously wrong unless the set contains only O(1) elements.
He actually ends up proving the weak result
that the size of the average prime less than N is *at least* O(log N)
(not ruling out O(N) or whatever);
That wasn't a weaker result, it was a counter argument to your bogus claim.
Furthermore, something cannot be *at least* O(log N). It can only be *at least*
Omega(log N). You should really learn the terms.
I had gotten the stronger result that
the size of the average prime *was* only O(log N).
You are saying the average prime below N is O(log N)?
There are O(log N) primes below N. At least one of these primes is at least N/2.
Even if we ignore the contribution of all other elements in this set, this
single prime alone implies an average of at least Omega(n/log n).
I have the impression that you are trying to look at the set {1,...,N} and take
the average only over the primes in this set, whatever that means. If that is
what you are trying to do, you really should write that down more precisely.
Still, it would be unclear what this would contribute to your reasoning.
The reasoning in a nutshell:
Algorithm to build sieve up to N as I stated it has three parts. Loop
until sqrt(N) (O(sqrt(N)). For each p reached that's not gotten marked
composite earlier, loop from p^2 until N step p. The number of these
loops is O(P), P the number of primes up to sqrt(N). The length of a
given one is O(N/p). Turns out P is O(log(sqrt(N)) = O(1/2 log(N)) =
O(log(N)), so this loop is O(log(N)*X) where the average length of a
loop is O(X). What is the average length of a loop?
It's O(N/p) of course, for the average choice of p.
Note: You cannot just argue over averages and then multiply with the number of
iterations. In general, such arguments fail.
Primes are
logarithmically distributed (P is O(log(N)) above) so the average p is
going to be small fairly independently of the range. It's hard to be
sure it's O(1) though. The average is the sum divided by the total
number. The sum of the primes, the way they are logarithmically
distributed, could be approximated by the integral of the logarithm. (It
might actually be better now I think of it to integrate N/p -- N*(1/2 +
1/3 + 1/5...) looks like N times an exponential decay function, whose
integral is itself and which is clearly O(1))
Clearly?
1/2 + 1/3 + 1/5 + 1/7 + 1/11 ...
is O(1)? You should read:
http://mathworld.wolfram.com/HarmonicSeriesofPrimes.html
It approaches ln ln N.
I concluded that the average length of the loop is bounded by O(N),
You need this long argument to conclude that the average length of a loop that
starts above 1, has a step size of more than 1 and ends at N is bounded by O(N)?
Wow.
and
the whole algorithm by O(N log N). If it's actually N log log N or can
be made such, so much the better.
It's a bit hard to understand why you need so much reasoning for this simple
bound for which already two independent arguments (each of which fit into two
lines) have been given.
BTW: Now that we know that the harmonic series of primes grows as O(ln ln N),
this proves that the total time is O(N * log log N).
Cheers,
Simon