It's all on these two functions. Three most frequently used operations of Num (ModP x) are (+) (-) (*)，each of them will at least call p2num once(to get the modulus), in addition multiplication will call montgKeys. usual implementation do both in constant time: p2num is written as number literal with type "Integral a=>a", so a reasonable implementation should handle these two function in constant time(in amortized time, of course). On Nov 7, 2011 2:27 PM, "Ivan Lazar Miljenovic" <ivan.miljeno...@gmail.com> wrote:
> On 7 November 2011 16:54, Bin Jin <bjin1...@gmail.com> wrote: > > The actual time to calculate p2num and montgKeys are both O(log P). What > I'm > > looking is a constant time lookup. > > Are these two functions CPU bottlenecks as revealed by profiling? If > not, then you're probably over-optimising. > > Note that if O(1) lookup is really required, then that implies you use > a static array, which requires you to pre-populate such an array with > all possible values. > > -- > Ivan Lazar Miljenovic > ivan.miljeno...@gmail.com > IvanMiljenovic.wordpress.com >
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
