Double factorial and primorial
arndt at jjj.de
Thu Dec 22 15:39:42 CET 2011
* Torbjorn Granlund <tg at gmplib.org> [Dec 22. 2011 07:21]:
> 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
> 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)).
Then the situation here may just be different.
For what I did see pp.637-638 (section 32.5.3,
"Exhaustive search for sets of candidate arguments")
of the fxtbook (and there it says the factor was 25).
> 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.
I think the data-dependent branches killed it for me
(a simple binary heap was used).
> gmp-devel mailing list
> gmp-devel at gmplib.org
More information about the gmp-devel