Hello all,
Trying to learn Haskell here... In a Haskell tutorial I found a function deciding if a number is prime: --//-- prime n = not (factors 2 n) factors m n | m == n = False | m < n = divides m n || factors (m+1) n divides a b = (mod a b == 0) --//-- Reference: http://www.cs.chalmers.se/Cs/Grundutb/Kurser/d1pt/d1pta/Function%20Definition%20by%20Cases%20and%20Recursion/sld038.htm This function seems to produce a wrong result on the number 38466629 (warning, slow computation). This number is prime but the function says that it's not. How do I know that 38466629 is prime? Beause: * http://www.rsok.com/~jrm/printprimes.html says that it is. * I wrote another prime function that says that it is. This is my function: --//-- prime 1 = False prime 2 = True prime n = filter (divides n) primes == [] where numbers = [x | x <- [2..n-1], x*x <= n] primes = filter prime numbers divides a b = (mod a b == 0) --//-- I can't figure out what's wrong with the first one. Can anyone spot the problem? (I'm just curious - trying to learn Haskell). Cheers, Daniel. -- /\/`) http://oooauthors.org /\/_/ http://opendocumentfellowship.org /\/_/ \/_/ I am not over-weight, I am under-tall. / _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Hi Daniel!
> How do I know that 38466629 is prime? What about this: 38466629 = 31 x 1240859 Regards, Jens _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Daniel Carrera-2
John Peterson wrote:
> Add a type signature: > > prime :: Integer -> Bool > > It's defaulting to Int and you're getting overflows Thanks. Hmm... it's still not working. Btw, I mis-reported the problem. The offending number is 38466629, which is /not/ prime but the sample program reports as prime. 38466629 = 31 * 1240859 The offending program is: --//-- prime :: Integer -> Bool prime n = not (factors 2 n) factors :: Integer -> Integer -> Bool factors m n | m == n = False | m < n = divides m n || factors (m+1) n divides :: Integer -> Integer -> Bool divides a b = (mod a b == 0) --//-- The math behind the program seems correct... :( Cheers, Daniel. -- /\/`) http://oooauthors.org /\/_/ http://opendocumentfellowship.org /\/_/ \/_/ I am not over-weight, I am under-tall. / _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Jens Fisseler
Jens Fisseler wrote:
> What about this: 38466629 = 31 x 1240859 Yes, I wrote backwards. The offending program says that it's prime but it's not. Cheers, Daniel. -- /\/`) http://oooauthors.org /\/_/ http://opendocumentfellowship.org /\/_/ \/_/ I am not over-weight, I am under-tall. / _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Daniel Carrera-2
Hi Daniel!
You just have to change the arguments of the 'mod'-function: old: divides a b = (mod a b == 0) new: divides a b = (mod b a == 0) Regards, Jens _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Daniel Carrera-2
Daniel,
Could it be that the arguments to either divides or mod should be reversed? Currently it seems to be testing whether the candidate prime (n) divides the possible factor (m). Or am I to tired to read the code straight? Regards, Maarten On 12/20/05, Daniel Carrera <[hidden email]> wrote: > John Peterson wrote: > > Add a type signature: > > > > prime :: Integer -> Bool > > > > It's defaulting to Int and you're getting overflows > > Thanks. Hmm... it's still not working. > > Btw, I mis-reported the problem. The offending number is 38466629, which > is /not/ prime but the sample program reports as prime. > > 38466629 = 31 * 1240859 > > The offending program is: > --//-- > prime :: Integer -> Bool > prime n = not (factors 2 n) > > factors :: Integer -> Integer -> Bool > factors m n | m == n = False > | m < n = divides m n || factors (m+1) n > > divides :: Integer -> Integer -> Bool > divides a b = (mod a b == 0) > --//-- > > The math behind the program seems correct... :( > > Cheers, > Daniel. > > > > -- > /\/`) http://oooauthors.org > /\/_/ http://opendocumentfellowship.org > /\/_/ > \/_/ I am not over-weight, I am under-tall. > / > _______________________________________________ > Haskell-Cafe mailing list > [hidden email] > http://www.haskell.org/mailman/listinfo/haskell-cafe > Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Daniel Carrera-2
-divides a b = (mod a b == 0) +divides a b = (mod b a == 0) On Dec 20, 2005, at 11:09 AM, Daniel Carrera wrote: > John Peterson wrote: >> Add a type signature: >> prime :: Integer -> Bool >> It's defaulting to Int and you're getting overflows > > Thanks. Hmm... it's still not working. > > Btw, I mis-reported the problem. The offending number is 38466629, > which is /not/ prime but the sample program reports as prime. > > 38466629 = 31 * 1240859 > > The offending program is: > --//-- > prime :: Integer -> Bool > prime n = not (factors 2 n) > > factors :: Integer -> Integer -> Bool > factors m n | m == n = False > | m < n = divides m n || factors (m+1) n > > divides :: Integer -> Integer -> Bool > divides a b = (mod a b == 0) > --//-- > > The math behind the program seems correct... :( > > Cheers, > Daniel. > > > > -- > /\/`) http://oooauthors.org > /\/_/ http://opendocumentfellowship.org > /\/_/ > \/_/ I am not over-weight, I am under-tall. > / > _______________________________________________ > Haskell-Cafe mailing list > [hidden email] > http://www.haskell.org/mailman/listinfo/haskell-cafe _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Daniel Carrera-2
Daniel Carrera <[hidden email]> writes:
> This function seems to produce a wrong result on the number 38466629 > (warning, slow computation). Here is an easier-to-find problem: it tells me the number 4 is prime. Regards, Malcolm _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Bugzilla from robdockins@fastmail.fm
Robert Dockins wrote:
> -divides a b = (mod a b == 0) > +divides a b = (mod b a == 0) Oh, thanks. My program assumed one way to define 'divides' and the example assumed the other. When I wrote it I was thinking of (divides a) being a function that tells me if the input divides 'a'. Thanks! Cheers, Daniel. -- /\/`) http://oooauthors.org /\/_/ http://opendocumentfellowship.org /\/_/ \/_/ I am not over-weight, I am under-tall. / _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Daniel Carrera-2
Henning Thielemann wrote:
>>factors :: Integer -> Integer -> Bool >>factors m n | m == n = False >> | m < n = divides m n || factors (m+1) n > > > Btw. I find the recursion harder to understand than the explicit > definition: > > factors n = any (divides n) [2..(n-1)] For what it's worth, I also found this function un-intuitive. What I'd expect a function called "factors" to do is exactly what yours does, and not what the one in the example does. Cheers, Daniel. -- /\/`) http://oooauthors.org /\/_/ http://opendocumentfellowship.org /\/_/ \/_/ I am not over-weight, I am under-tall. / _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
On Tue, 2005-12-20 at 16:53 +0000, Daniel Carrera wrote:
> Henning Thielemann wrote: > >>factors :: Integer -> Integer -> Bool > >>factors m n | m == n = False > >> | m < n = divides m n || factors (m+1) n > > > > > > Btw. I find the recursion harder to understand than the explicit > > definition: > > > > factors n = any (divides n) [2..(n-1)] > > For what it's worth, I also found this function un-intuitive. What I'd > expect a function called "factors" to do is exactly what yours does, and > not what the one in the example does. It helped me to read "factors m n" as "there is an integer between m and n-1 inclusive that divides n". Then the recursion made sense. Thielemann's "factors n" would read "there is an integer between 2 and n-1 inclusive that divides n". -- Bill Wood _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Free forum by Nabble | Edit this page |