<p>The actual time to calculate p2num and montgKeys are both O(log P). What I&#39;m looking is a constant time lookup.</p>
<div class="gmail_quote">On Nov 7, 2011 1:51 PM, &quot;Yucheng Zhang&quot; &lt;<a href="mailto:yczhang89@gmail.com">yczhang89@gmail.com</a>&gt; wrote:<br type="attribution"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
On Mon, Nov 7, 2011 at 9:29 AM, Bin Jin &lt;<a href="mailto:bjin1990@gmail.com">bjin1990@gmail.com</a>&gt; wrote:<br>
&gt; Hi<br>
&gt; This method is what I&#39;m looking for. it&#39;s a nice general solution, but it<br>
&gt; doesn&#39;t solve my problem here.<br>
&gt; I&#39;m using ghc 7.0.3, I tried to cache p2num and montgKeys in the way you<br>
&gt; showed. It seems that ghc doesn&#39;t memorize p2num and reject to compile new<br>
&gt; montgKeys.<br>
&gt; I think caching values with dynamic types is complicated in ghc&#39;s runtime<br>
&gt; environment. Anyone knows the details?<br>
<br>
Adding memorization directly to &#39;montgKeys&#39; or &#39;p2num&#39; should be possible,<br>
if you write your own version of MemoTrie dealing with dynamic types.<br>
<br>
However, this memorization requires an O(log P) lookup in the trie.<br>
This lookup process will require the whole type structure of P to be<br>
examined, which is of size O(log P).<br>
<br>
<br>
<br>
Yucheng Zhang<br>
</blockquote></div>