Double factorial and primorial

[Joerg Arndt]

* 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
>   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)).

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).


> 
> -- 
> Torbjörn
> _______________________________________________
> gmp-devel mailing list
> gmp-devel at gmplib.org
> https://gmplib.org/mailman/listinfo/gmp-devel