On Thu, Feb 26, 2009 at 7:04 PM, <ja...@njkfrudils.plus.com> wrote:
> If this is a typical example that you are interested in , then a faster way is > to reduce t mod 2^q+1 which can be done with one subtraction , this gives you > a remainder whichis nearly right , then while(remainder >(2^q+1)/3)subtract > (2^q+1)/2 from the remaninder , you will only need to do this at most twice. > > So we have swapped a mod operation for a few subtractions , this will be > around 3 to 4 times faster (assuming 1 mod=2 to 3 muls) > If q is divisible by a high power of two then we can double the speed yet > again. > > so to reduce t mod 2^q+1 , subtract the upper q bits from the lower q bits , > and add back in any borrow from that subtraction The code I posted is always the same, except the value of q changes. q is always a prime number so it is not divisible by anything except 1 and itself. It is getting late so I'm going to have to think about what you are saying a bit more to fully understand how to implement that. Thanks for the suggestion, Jeff. --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
