Another improvement? would be: use a balanced tree, this is similar to the
already posted my binary_splitting routine, that solves it in a recursive
way to compute the product of lots of numbers, but since here we need the
whole tree (to get the remainders) we can't follow exactly this recursive
solution. Use a direct way: when the x point is a product of c numbers then
the two childs of x are product of exactly floor(c/2) and ceil(c/2) numbers.
(since floor(c/2)+ceil(c/2)=c it is possible). I think this is better way,
it is a general observation that gmp likes if the operand size's are nearly
equal.
For example for 12 numbers the current solution follows in reversed:
tree[11]=p6
tree[10]=p5
tree[9]=p4
tree[8]=p3
tree[7]=p2
tree[6]=p1
tree[5]=p5*p6
tree[4]=p3*p4
tree[3]=p1*p2
tree[2]=p3*p4*p5*p6
tree[1]=p1*p2*p3*p4*p5*p6 (too bad we computed it as (p1*p2)*(p3*p4*p5*p6))
The balanced version in reversed:
tree[15]=1
tree[14]=p6
tree[13]=p5
tree[12]=p4
tree[11]=1
tree[10]=p3
tree[9]=p2
tree[8]=p1
tree[7]=p6
tree[6]=p4*p5
tree[5]=p3
tree[4]=p1*p2
tree[3]=p4*p5*p6
tree[2]=p1*p2*p3
tree[1]=p1*p2*p3*p4*p5*p6
So in this solution the tree will be a complete binary tree, we need to give
only the offset of the leafs: pi or 1. Then the remaining part of the
routine is almost the same, there is pow2 instead of count, where pow2 is
the number of leafs (pow2=8 for the above case)
for(i=pow2-1;i>0;i--) mpz_mul(tree[i],tree[2*i],tree[2*i+1]);
// compute the remainders in the tree
mpz_mod(tree[1],u,tree[1]);
for(i=2;i<2*pow2;i++)
mpz_mod(tree[i],tree[i>>1],tree[i]);
Obviously not every pi are equal so floor(c/2) and ceil(c/2) choice is still
suboptimal, but close to the optimal.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"mpir-devel" group.
To post to this group, send email to mpir-devel@googlegroups.com
To unsubscribe from this group, send email to
mpir-devel+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/mpir-devel?hl=en
-~----------~----~----~----~------~----~------~--~---
