Double factorial and primorial

[Torbjorn Granlund]

Joerg Arndt <arndt at jjj.de> writes:

  * Niels Möller <nisse at lysator.liu.se> [Dec 20. 2011 16:05]:
  > Torbjorn Granlund <tg at gmplib.org> writes:
  > 
  > > then one could sort the indexes using a minheap.
  > 
  > Clever!
  > 
  
  A bit of a warning: I once used a heap to do essentially the same
  thing, it turned that using a simple array was significantly faster
  (factor 20 or so).  The array definitely needs to fit into level-1
  cache.
  
Using an array would not work well for the algorithm I suggested; it
would make operations O(sqrt(N)) which with a heap would be
O(log(sqrt(N))) = O(log(N)).

A heap is of course represented in an array (not using pointers).
Perhaps that's what you mean?

Heap operations have reasonable locality.  Even if the entire heap does
not fit into cache, only elements close to the leafs will typically not
be in cache.

-- 
Torbjörn