[Haskell-beginners] Prime number test performance on negative integers

[Folsk Pratima]

>Hello Pratima,
>
>Il 11 dicembre 2023 alle 19:24 Folsk Pratima ha scritto:
>> Please explain why this fails for negative numbers. By fails I mean
>> it starts eating RAM infinitely until either me or OOM kills it. If
>> you replace `m1` definition with the one commented out, the code will
>> fail for positive integers as well, which is very frustrating.
>
>I have replaced m1 definition with the commented one, and it works on
>my machine.
>
>    f at x270:/tmp/prova$ ./prime -4
>    -4 is not primal because divisible by 2
>
>How are you invoking the program?
>
>A few additional notes (run `hlint` for more)
>
>> main =
>>     getArgs >>= \argv ->
>
>I don’t mind `>>=` but with `do` notation and `traceM/traceShowM` it
>is easier to debug your programs.
>
>>             --m1 =
>>             --    map
>>             --        (\x ->
>>             --             if x < 0
>>             --                 then -x
>>             --                 else x)
>>             --        m0
>
>More compact: `m1 = map abs m0`
>
>>             msg (x, (y0, y1)) = x ++ " is " ++ f y0 ++ " because "
>> ++ y1
>
>Ancillary functions like this one can go in the `where` section.
>Ciao
>—F

I have been just going to remedy and send the actual number I was using
for testing, sorry for this. Assuming the binary is called a.out,
./a.out 4394853075948683624652562564254523466839834983
I have not immediately guessed that it overflows, so after playing a
minute with it I figured another number -- 1506491439391566589 -- that
breaks even while being positive. And it does not matter if
`m1 = m0` or `m1 = map abs m0`.

I have come up with another definition, based on the `primals`
definition on haskell.org main page that I have not noticed until now.

isPrime6 :: Int -> (Bool, String)
isPrime6 n = test (f [2 ..])
  where
    f (x:xs) = x : f [y | y <- xs, (y `rem` x) /= 0]
    test (x:xs)
        | x > n = (False, "it is not")
        | x == n = (True, "it is")
        | otherwise = test xs

Testing it with 1506491439391566589 makes it look like the code is
going to run forever, but at least it does not take all of your RAM. I
dare suspect the problem is somewhere around having a separate variable
for the `l` list, which does not allow haskell to forget used members.
I am not sure about anything however.

Also, the fact that the code runs forever nonetheless is very sad,
because C equivalent taken from wiki[1] calculates the whole things
almost immediately. The C code is ultra simplified:

#include <stdio.h>
#include <stdint.h>
int IsPrime(int64_t n)
{
    if (n == 2 || n == 3)
        return 1;

    if (n <= 1 || n % 2 == 0 || n % 3 == 0)
        return 0;

    for (int i = 5; i * i <= n; i += 6)
    {
        if (n % i == 0 || n % (i + 2) == 0)
            return 0;
    }

    return 1;
}

int main () {
    printf ("1506491439391566589: %d\n", IsPrime (1506491439391566589));
}

I did not even do anything special to compile it, just `gcc`. With
haskell I supplied the `-O2` flag to `ghc`.

1. https://en.wikipedia.org/wiki/Primality_test