[Haskell-cafe] memorize function with number parameterized types in GHC

Bin Jin bjin1990 at gmail.com
Mon Nov 7 07:39:04 CET 2011

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.miljenovic at gmail.com>

> On 7 November 2011 16:54, Bin Jin <bjin1990 at 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.Miljenovic at gmail.com
> IvanMiljenovic.wordpress.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20111107/331c0d6e/attachment.htm>

More information about the Haskell-Cafe mailing list