Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Prime number test performance on negative integers
(Folsk Pratima)
2. Re: Prime number test performance on negative integers
(Francesco Ariis)
3. Re: Prime number test performance on negative integers
(Folsk Pratima)
4. Re: Prime number test performance on negative integers
(Francesco Ariis)
5. Re: Prime number test performance on negative integers
(Folsk Pratima)
6. Re: Prime number test performance on negative integers
(Francesco Ariis)
----------------------------------------------------------------------
Message: 1
Date: Mon, 11 Dec 2023 19:24:17 +0200
From: Folsk Pratima <[email protected]>
To: [email protected]
Subject: [Haskell-beginners] Prime number test performance on negative
integers
Message-ID: <[email protected]>
Content-Type: text/plain; charset=US-ASCII
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.
import System.Environment
isPrime :: Int -> (Bool, String)
isPrime n =
let ll n = k + 1 : k + 5 : ll (n + 1)
where
k = 6 * n + 1
l = 2 : 3 : 5 : ll 1
q (i:is)
| i * i > n = (True, "it is")
| (n `rem` i) == 0 = (False, "divisible by " ++ show i)
| otherwise = q is
in q l
main =
getArgs >>= \argv ->
let f True = "primal"
f False = "not primal"
m0 = map (\x -> read x :: Int) argv
m1 = m0
--m1 =
-- map
-- (\x ->
-- if x < 0
-- then -x
-- else x)
-- m0
m2 = map isPrime m1
msg (x, (y0, y1)) = x ++ " is " ++ f y0 ++ " because " ++ y1
in mapM_ putStrLn $ map msg (zip argv m2)
------------------------------
Message: 2
Date: Mon, 11 Dec 2023 18:55:21 +0100
From: Francesco Ariis <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] Prime number test performance on
negative integers
Message-ID: <[email protected]>
Content-Type: text/plain; charset=utf-8
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@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
------------------------------
Message: 3
Date: Mon, 11 Dec 2023 20:24:13 +0200
From: Folsk Pratima <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] Prime number test performance on
negative integers
Message-ID: <[email protected]>
Content-Type: text/plain; charset=UTF-8
>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
------------------------------
Message: 4
Date: Mon, 11 Dec 2023 19:48:07 +0100
From: Francesco Ariis <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Prime number test performance on
negative integers
Message-ID: <[email protected]>
Content-Type: text/plain; charset=utf-8
Il 11 dicembre 2023 alle 20:24 Folsk Pratima ha scritto:
> 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));
> }
Let’s implement the algorithm in Haskell, shall we?
import System.Environment
isPrimeWiki :: Integer -> Bool
isPrimeWiki 2 = True
isPrimeWiki 3 = True
isPrimeWiki n
| n <= 1 ||
rem n 2 == 0 ||
rem n 3 == 0 = False
isPrimeWiki n =
let f i
| i^2 > n = True
| rem n i == 0 ||
rem n (i+2) == 0 = False
| otherwise = True
in f 5
main :: IO ()
main = do
[n] <- getArgs
print $ isPrimeWiki (read n)
then
f@x270:/tmp/prova$ time ./prime 1506491439391566589
True
real 0m0.014s
user 0m0.001s
sys 0m0.005s
------------------------------
Message: 5
Date: Mon, 11 Dec 2023 21:41:00 +0200
From: Folsk Pratima <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] Prime number test performance on
negative integers
Message-ID: <[email protected]>
Content-Type: text/plain; charset=UTF-8
>Il 11 dicembre 2023 alle 20:24 Folsk Pratima ha scritto:
>> 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)); }
>
>Let’s implement the algorithm in Haskell, shall we?
>
> import System.Environment
>
> isPrimeWiki :: Integer -> Bool
> isPrimeWiki 2 = True
> isPrimeWiki 3 = True
> isPrimeWiki n
> | n <= 1 ||
> rem n 2 == 0 ||
> rem n 3 == 0 = False
> isPrimeWiki n =
> let f i
> | i^2 > n = True
> | rem n i == 0 ||
> rem n (i+2) == 0 = False
> | otherwise = True
> in f 5
>
> main :: IO ()
> main = do
> [n] <- getArgs
> print $ isPrimeWiki (read n)
>
>then
>
> f at x270:/tmp/prova$ time ./prime 1506491439391566589
> True
>
> real 0m0.014s
> user 0m0.001s
> sys 0m0.005s
Ahem,
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
int IsPrime(int64_t n, char **msg)
{
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) {
sprintf (*msg, "divisible by %d", i);
return 0;
}
if (n % (i + 2) == 0) {
sprintf (*msg, "divisible by %d", i + 2);
return 0;
}
}
return 1;
}
int main () {
char *msg[1];
msg[0] = malloc (sizeof (char) * 128);
sprintf (msg[0], "success");
int res;
int64_t num;
char numstr[] = "1506491439391566589";
num = 1506491439391566589;
res = IsPrime (num, msg);
printf ("%s: %d: %s\n", numstr, res, msg[0]);
}
tells me the number is divisible by 13 and is *not* primal. The
qalculate tells me pretty much the same!
------------------------------
Message: 6
Date: Mon, 11 Dec 2023 21:25:33 +0100
From: Francesco Ariis <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] Prime number test performance on
negative integers
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
Il 11 dicembre 2023 alle 21:41 Folsk Pratima ha scritto:
> Ahem,
Woops, I messed up that `otherwise`.
import System.Environment
isPrimeWiki :: Integer -> Bool
isPrimeWiki 2 = True
isPrimeWiki 3 = True
isPrimeWiki n
| n <= 1 ||
rem n 2 == 0 ||
rem n 3 == 0 = False
isPrimeWiki n =
let f i
| i^2 > n = True
| rem n i == 0 ||
rem n (i+2) == 0 = False
| otherwise = f (i+1)
in f 5
main :: IO ()
main = do
[n] <- getArgs
print $ isPrimeWiki (read n)
Still, no sweat computing that:
f@x270:/tmp/prova$ time ./prime 1506491439391566589
False
real 0m0.014s
user 0m0.000s
sys 0m0.005s
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 172, Issue 1
*****************************************
