On Thu, Jul 8, 2010 at 5:24 PM, Jason Moxham <[email protected]>wrote:
> > maybe , I would have to look it up , basically mulhi goes like this > > calculate mul_short (either basecase or divide and conquer) > mul_short is like mul_high but with 2 extra digits calculated , these 2 > extra > digits give enough info that the mul_high product is almost always right > except in easy to tell situations . If the product is not an exact mul_high > then just do a full mull.The probability of having to do a full mul is > something like n/2^64 (for n limbs), how far the mul_short differs from > mul_high would be easy to calculate but I dont know what it is (perhaps n?) > I think the sourcecode has all the info , or you can read the relevant > paper > which is referenced somewhere. > > Jason > Yes, I know MPFR uses something like this. The probability of having to fall back to the full product is negligible because the bits are pretty much random in my use case, so only the overhead should matter. As long as the error can be bounded (say, by n units in the last place), either way should be fine. If the overhead is only 10%, say, it probably doesn't matter. Fredrik -- You received this message because you are subscribed to the Google Groups "mpir-devel" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/mpir-devel?hl=en.
