[Haskell-cafe] More Efficient Recursion

David Feuer david.feuer at gmail.com
Sun Feb 21 00:45:17 UTC 2021


You can solve the (potential) strictness problem like this:

  | (iterator < exponent) = result `seq` modLoop (iterator + 1) exponent
(mod (result * base) modulus)

but you'd be better off changing your function to use exponentiation by
squaring, which will dramatically reduce the number of multiplications.

On Sat, Feb 20, 2021, 7:36 PM A. Mc. <47dragonfyre at gmail.com> wrote:

> Hello,
>
> I'm just starting off, but I'm wondering if anyone has any suggestions.
> I've made a recursive function that's goal is to handle a base raised to a
> very large power.
> modLoop :: Integer -> Integer -> Integer -> Integer -> Integer -> Integer
> modLoop iterator exponent result base modulus
>   | (iterator == exponent) = result
>    | (iterator < exponent) = modLoop (iterator + 1) (exponent) (mod
> (result * base) modulus) base modulus
>    | (iterator > exponent) = (-1)
>
> However, it flat breaks or takes a long time when using large numbers.
>
> I need to get better at using strict functions, however, I compiled with
> ghc -o (as it tends to implement the strict version - ?) and I still have
> the same problem.  What's a better way?
>
> Thanks in advance and thank you for your time.
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20210220/a927667e/attachment.html>


More information about the Haskell-Cafe mailing list