Double factorial and primorial

Torbjorn Granlund tg at
Tue Dec 20 17:05:27 CET 2011

Joerg Arndt <arndt at> writes:

  * Niels Möller <nisse at> [Dec 20. 2011 16:05]:
  > Torbjorn Granlund <tg at> 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
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.


More information about the gmp-devel mailing list