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 magical enough to memorize values with the same type(well, it's actually dynamically generated number parameterized type).
I used binary representation to handle all positive numbers in type system. > data One = One > data D0 a = D0 a > data D1 a = D1 a > class PostiveN a where > p2num :: (Num b, Bits b) => a -> b > instance PostiveN One ... > instance PostiveN a => PostiveN (D0 a) ... > instance PostiveN a => PostiveN (D1 a) ... 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 usage. But tracing shows that both `p2num` and `montgKeys` are evaluated every time being called. So my question is, how to force GHC memorizing this kind of functions? [1]: http://en.wikipedia.org/wiki/Montgomery_reduction [2]: https://github.com/bjin/montg-reduce Regards, Bin
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
