Re: Another twin primes conjecture

From: Christian Bau (christian.bau_at_cbau.freeserve.co.uk)
Date: 06/21/04 

Date: Mon, 21 Jun 2004 07:50:26 +0100

In article <HzMuJF.C62@cwi.nl>, "Dik T. Winter" <Dik.Winter@cwi.nl>
wrote:

> In article <LW%Ac.811048$oR5.456805@pd7tw3no> "Quinn Tyler Jackson"
> <quinn-j@shaw.ca> writes:
> > OK, David -- I've considered your bubble sort analogy. That's where you
> > (and
> > possibly others) are coming from, and I understand and allow for your
> > views.
> > You probably (not sure, but likely) also realize that I've witnessed James
> > in another, entirely different context, where the typical response to
> > "It's
> > not very fast at all" would be "Can I help you make it faster? Here, note
> > that X is a bottleneck. You may be able to speed it up if you ...." and
> > James' response is "Wow! That speeds it up! Thanks! Maybe if I show you
> > some
> > of my attempts at speeding it up, you can improve on those, since you
> > found
> > X."
>
> Possibly true. But what we reminded James of is not only that his
> algorithm could be made faster, but that the time complexity of his
> algorithm was not good enough. So pointing to bottle-necks would
> help bringing down the constants, but not the complexity. His
> algorithm is O(n), which will not be anything but mildly interesting,
> whatever the constants involved. And when he states that his
> algorithm is better when pointers are given to algorithms with
> better time complexity...

Not only pointers. I am quite sure I posted at least once an explanation
of Meissel's algorithm, which calculates exactly the same values as
Legendre's algorithm, which Harris copied, except that it manages to
determine a huge number of values quicker by using a sieve and therefore
manages to reduce the time complexity.

Now Meissel's method is still by far not the fastest, but it is quite
simple, and once you've understood it it becomes quite obvious that his
approach of using sieves when they are helpful could be extended.

Relevant Pages

  • Re: [9fans] `mk` (from Plan9 ports) efficiency related issue
    ... using simple algorithm with much worse time complexity than ... upfront as that would definitely be much faster than walking ... A dependency matrix is usually very sparse ...
    (comp.os.plan9)
  • Re: Maximum value of a function...
    ... I have a cost function which has two parameters as inputs, ... The cost function is actually the time complexity of an algorithm and ... Complexity of the algorithm is: ... So now I'm stuck. ...
    (sci.math)
  • Re: Quicker then QuickSort???
    ... Thank you for the information about the time complexity! ... Kristofer Gafvert - IIS MVP ... i cannot tell you the Ofor this algorithm (because i am ... > are sorting 30 things, an n^2 algorithm may go faster, but when sorting ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: find the largest 1000 values
    ... I have a new idea of using STL nth_element algorithm, and each time I read a number of data which my memory can afford, then I input to nth_element which could save time to sort. ... I am wondering the time complexity of nth_element, ...
    (microsoft.public.vc.language)
  • Re: APL and (very) large arrays
    ... Sort is at best O) depending on the sorting algorithm used, ... As to the OP's question about primes, there are advanced efforts to compute pifor very large values of n, but the only elementary method is to find all primes <= n and count them. ... By representing only the odd values the sieve would require 62.5MB. ...
    (comp.lang.apl)