Re: Partial difference equation, primes

From: David Kastrup (dak_at_gnu.org)
Date: 08/23/04 

Date: 24 Aug 2004 01:33:13 +0200

jstevh@msn.com (James Harris) writes:

> If you implement the pure math function itself--that is use no
> speed-ups--it's rather slow.
>
> But if you do the same thing with the Fourier Transform--it's slow.
>
> You sci.math'ers wish to throw out the baby with the bathwater by
> creating dumb criteria.
>
> Like suddenly, if there are fast algorithms the base mathematics is
> junk!!!
>
> Oh wait, even you probably aren't socially stupid enough to try and
> toss out the Fourier Transform, so you sci.math'ers are *picky* about
> where you apply your rules.
>
> If I discover something, you make up one rule, but you dare not
> challenge Fourier!!!

The problem is that the Fourier transform has a lot of uses, and the
DFT is a discretionary form of it with similar uses, and the FFT is a
fast implementation of it.

Now pi(n) also has a lot of uses, and your function throws out nothing
but pi(n) as well as intermediate results from a rather slow
implementation of pi(n). One that's a few hundred years old.

So there is no additional theoretical value of your work (since pi(n)
existed before), and no practical value (since it is not faster than
even rather mediocre implementations).

Since there is no new value neither in theory nor in practice, your
work is uninteresting except as finger exercises to yourself. A nice
area for finger exercises, but that's it.

> dS(N,3) = floor((N-4)/6) with N even.
>
> It is the least computationally complex formula for calculating the
> count of odd composites with 3 as a factor up to and including N.
>
> That technology is state of the art, as mathematicians cannot do
> better.

But that's a single trivial case. The least computationally complex
way of sorting a list of two numbers by comparison is insertion
sorting: first sorting a sublist with one element taking out, then
putting that element in its proper place in the sorted list by
comparing until you find the place. Implement that, and for 2 numbers
you compare the numbers and swap them if they are in the wrong order.
But that does not imply that sorting 10 numbers is done fastest by
insertion sort. In fact, almost every sorting algorithm, when given
only a list of two numbers, will end up comparing the numbers once
and swapping them if they are not in the right order.

And most efficient algorithms still are indistinguishable from the
worst imaginable algorithms when you are comparing 3 elements. With 4
elements, the best algorithms and the worst tend to be slightly
different, and with 5 elements, the best (merge insertion) tends to be
slightly better than the rest. But the numbers really fall apart noly
when you get into the hundreds, thousands, millions. That's where the
good and the bad algorithms can be _properly_ sorted out, not with the
trivial cases.

> They also cannot do better--or even math without my research--the
> the other dS values I can give, like
>
> dS(N,5) = floor((N-16)/10) - floor((N-16)/30), with even N>6,

You need to use 15 to have this hold properly for even and odd N.

> Since I can give the most compact, most efficient formulas for each
> dS count, I can define the most efficient prime counting possible.

No, you can't. Because the trivial cases don't generalize to the
complicated ones.

> Like I said, on every point I'm way ahead of mathematicians and the
> technology I have is state of the art.

Its asymptotics are Legendre's, and quite more efficient algorithms
exist. The papers have been pointed out to you. 

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Relevant Pages

  • Re: Partial difference equation, primes
    ... sorting: first sorting a sublist with one element taking out, ... comparing until you find the place. ... And most efficient algorithms still are indistinguishable from the ... and quite more efficient algorithms ...
    (sci.math)
  • Re: Fastest sorting algorithm
    ... It also depends on whether or not you need the sort to be stable - that can make a big difference to the sort speed. ... It also depends on what you are comparing and how complex the compares are. ... Some algorithms keep the number of comparisns as low as possible, and are thus faster when the comparison is complex Other algorithms rely on more comparisons but use a faster sort process, so will be better when the comparison is simple, such as integers. ... so the sorting would be by IDs only. ...
    (microsoft.public.dotnet.languages.vb)
  • Re: Sorting algorithm when comparison is heavy
    ... optimal way of sorting such elements (in other words, ... I have no idea about algorithms at all. ... want to completely sort the players by their strength (we can assume ... My guess is that log2rounds are needed for a full sorting. ...
    (comp.programming)
  • Re: Selection-Sort in C
    ... solving that problem is the cost of the best algorithms. ... making is to assume that all sorting algorithms are comparison sorts. ... Thetawhere n is the number of bits in the data set. ...
    (comp.lang.c)
  • Re: Sorting algorithm when comparison is heavy
    ... optimal way of sorting such elements (in other words, ... There are many sort algorithms as ... you may be able to get by coding. ...
    (comp.programming)
Quantcast