[m-users.] Source Code for Miller-Rabin

[Matthias Guedemann]

Hi Robert,

thanks, I'll have a look at it.

> When running test_primes/2 using two 40-digit numbers with the second
> number 5000 larger than the first, I encountered a crash on the PPC
> machine: Uncaught Mercury exception: Software error: detected infinite
> recursion in func primality.powm/4. When I test pown/4 as a standalone
> using large numbers, I'm able to get correct results, so it may be
> that a process upstream of powm/4 is a problem. I'm looking into this.

For a first impression: be careful with memozation!

,----
| :- pragma memo(powm/3).
`----

this results in

,----
| ./test_primeFactors 1234567891234567891234567891234567891234567891234567891234567891
|    primeFactors(1234567891234567891234567891234567891234567891234567891234567891) = [509072870829426831235673094322600393065348204522878
| 3163107, 7823, 31].
| 1.86user 0.45system 0:02.31elapsed 100%CPU (0avgtext+0avgdata 2020044maxresident)k
| 0inputs+0outputs (0major+505046minor)pagefaults 0swaps
`----

without the memo pragma

,----
| ./test_primeFactors  1234567891234567891234567891234567891234567891234567891234567891
|    primeFactors(1234567891234567891234567891234567891234567891234567891234567891) = [5090728708294268312356730943226003930653482045228783163107, 7823, 31].
| 1.99user 0.03system 0:02.03elapsed 100%CPU (0avgtext+0avgdata 67548maxresident)k
| 0inputs+0outputs (0major+16922minor)pagefaults 0swaps
`----

i.e. basically same time, but way less RAM usage. The 'powm' function
takes 3 arguments, resulting in a *vast* table when memoized. That may
explain the problem on your PPC, too. Direct calculation is very likely
much better here.

> The naming convention for constant valued big integers is ap.n63, for
> example, for integer(63). The integer(N) feature doesn't work on the
> PPC machine for large values of N. I have been able to use a
> conversion from string to big integer to get around that problem. The
> solution works as well on x86-64 machines.

,----
| n63888049 = integer.integer(63888049).
| n3215031751 = integer.det_from_string("3215031751").
`----

This seems to be caused by passing 32-bit integer limits. In my opinion,
this thread is related to this problem:

http://www.mercurylang.org/list-archives/users/2009-October/005023.html

Best regards,
Matthias