Hi, Oleg
Thanks for your time and your brilliant code. I think this problem is
solved.
Best wishes to you
Regards
Bin
On Wed, Nov 9, 2011 at 2:05 PM, o...@okmij.org wrote:
p2num :: Dep a b
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
Hi,
Thanks for your reply!
I made some changes according to your suggest. Now I get rid of
argument p. Unfortunately, GHC is not smart enough to memorize
this true polymorphic constant.
Can you give some hints on what kind of specialize pragmas I should
use?
Regards,
Bin Jin
On Tue, Nov 8, 2011
It seems GHC can be pursuaded to do proper specialization and
memoization. We can see that, first, using trace:
class (Ord b, Integral b, Num b, Bits b) = PositiveN a b where
p2num :: Dep a b
instance (Ord b, Integral b, Num b, Bits b) = PositiveN One b where
p2num = trace p2num 1 $
Bin Jin wrote:
Here is a function that will be called everytime by `(*)` in `Num` typeclass
montgKeys :: (PostiveN p, Integral a, Bits a) = p - a
as you can imagine, I always pass (undefined :: p) as parameter to
`montgKeys`, so if it's handled well, it should be memorized for
future
Hi, everyone
I'm recently trying to implement the Montgomery reduction algorithm[1] in
Haskell, the code can be found on
my Github page[2]. After doing some benchmark testing I found that the
library works rather slow. With the
help of `trace` function from Debug.Trace, I found that GHC is not
On Sun, Nov 6, 2011 at 9:10 PM, Bin Jin bjin1...@gmail.com wrote:
Hi, everyone
I'm recently trying to implement the Montgomery reduction algorithm[1] in
Haskell, the code can be found on
my Github page[2]. After doing some benchmark testing I found that the
library works rather slow. With
Hi,
Since I actually didn't use the parameter in calculation, the return value
only depends on the type
of input, not the actually value. If it's impossible to cache the result,
is there another way to
memorize this function ?
On Sun, Nov 6, 2011 at 9:20 PM, Yucheng Zhang yczhan...@gmail.com
On Sun, Nov 6, 2011 at 9:35 PM, Bin Jin bjin1...@gmail.com wrote:
Hi,
Since I actually didn't use the parameter in calculation, the return value
only depends on the type
of input, not the actually value. If it's impossible to cache the result, is
there another way to
memorize this function ?
Hi,
Then how about p2num, how to memorize this function.
Also I think it's okay to memorize this kind of function. The type system
ensure all calling of montgKeys have the same type, e.g., it's a pure
function without parameter, it's safe to memorize it since it didn't occupy
more memory than
On Sun, Nov 6, 2011 at 10:31, Bin Jin bjin1...@gmail.com wrote:
Then how about p2num, how to memorize this function.
Also I think it's okay to memorize this kind of function. The type system
ensure all calling of montgKeys have the same type, e.g., it's a pure
function without parameter,
Yes, but I think it's not a funtion since the function didn't use the
parameter. So maybe there is a way to make memorizing possible.
Also p2num is a general function used in number parameterized types, so I
asked this question here.
On Nov 6, 2011 11:41 PM, Brandon Allbery allber...@gmail.com
What's the purpose of all the type trickery?
Why not just implement the algorithm using Integer?
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
In order to represent Z/nZ, regular way need to store two integers, and a
data constructer. With number parameterized types, newtype+Integer can be
used, it's much more efficient.
For this project, montg reduce require to calculate a key for each modulus,
but the modulus won't be changed within
Bin Jin bjin1990 at gmail.com writes:
In order to represent Z/nZ, regular way need to store two integers,
and a data constructer. With number parameterized types, newtype+Integer
can be used, it's much more efficient. For this project, montg reduce
require to calculate a key for each
On 11/6/11 10:51 AM, Bin Jin wrote:
Yes, but I think it's not a funtion since the function didn't use the
parameter. So maybe there is a way to make memorizing possible.
In general, if the argument is not used then
\x - E
is equal to
let e = E in \x - e
Which we can make strict by
Hi
This method is what I'm looking for. it's a nice general solution, but it
doesn't solve my problem here.
I'm using ghc 7.0.3, I tried to cache p2num and montgKeys in the way you
showed. It seems that ghc doesn't memorize p2num and reject to compile new
montgKeys.
I think caching values with
On Mon, Nov 7, 2011 at 9:29 AM, Bin Jin bjin1...@gmail.com wrote:
Hi
This method is what I'm looking for. it's a nice general solution, but it
doesn't solve my problem here.
I'm using ghc 7.0.3, I tried to cache p2num and montgKeys in the way you
showed. It seems that ghc doesn't memorize
The actual time to calculate p2num and montgKeys are both O(log P). What
I'm looking is a constant time lookup.
On Nov 7, 2011 1:51 PM, Yucheng Zhang yczhan...@gmail.com wrote:
On Mon, Nov 7, 2011 at 9:29 AM, Bin Jin bjin1...@gmail.com wrote:
Hi
This method is what I'm looking for. it's a
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
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
20 matches
Mail list logo