Double factorial and primorial
Joerg Arndt
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
> 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
More information about the gmp-devel
mailing list