How to repair this code

Learn
#1

Hello! This get from “250 problems in elementary number theory, (Modern analytic and computational methods in science and mathematics)” But have one question: How repair this code for complete work. (may be lazyness trick?)

isInteger :: RealFrac a => a -> Bool
isInteger x = fromIntegral (truncate x) == x

prf :: Int -> [Bool]
prf n = take n [x | j <- [0..], let x = isInteger ((j * j + 1) / (j + 1)), x == True ]

main = do
   putStrLn "Search  Integer result from sequences:" 
   print (prf 1000)
1 Like
#2

This code “works”, in the sense that it compiles and runs. It’s just working very hard!

Compiling with profiling:

ghc Main.hs -prof -fprof-auto
./Main +RTS -p

I get

	Wed Mar 15 08:07 2023 Time and Allocation Profiling Report  (Final)

	   Main +RTS -p -RTS

	total time  =       33.85 secs   (33853 ticks @ 1000 us, 1 processor)
	total alloc = 66,183,779,816 bytes  (excludes profiling overheads)

COST CENTRE MODULE    SRC              %time %alloc

isInteger   Main      Main.hs:2:1-44    62.8   54.7
prf.x       Main      Main.hs:5:37-73   31.8   36.0
prf         Main      Main.hs:5:1-78     5.4    9.3
                                                                             individual      inherited
COST CENTRE    MODULE                SRC                  no.     entries  %time %alloc   %time %alloc

MAIN           MAIN                  <built-in>           128           0    0.0    0.0   100.0  100.0
 CAF           Main                  <entire-module>      255           0    0.0    0.0   100.0  100.0
  main         Main                  Main.hs:(7,1)-(9,19) 256           1    0.0    0.0   100.0  100.0
   prf         Main                  Main.hs:5:1-78       258           1    5.4    9.3   100.0  100.0
    prf.x      Main                  Main.hs:5:37-73      259    85145795   31.8   36.0    94.6   90.7
     isInteger Main                  Main.hs:2:1-44       260    85145795   62.8   54.7    62.8   54.7
 CAF           GHC.Conc.Signal       <entire-module>      250           0    0.0    0.0     0.0    0.0
 CAF           GHC.IO.Encoding       <entire-module>      237           0    0.0    0.0     0.0    0.0
 CAF           GHC.IO.Encoding.Iconv <entire-module>      235           0    0.0    0.0     0.0    0.0
 CAF           GHC.IO.Exception      <entire-module>      229           0    0.0    0.0     0.0    0.0
 CAF           GHC.IO.Handle.FD      <entire-module>      227           0    0.0    0.0     0.0    0.0
 CAF           GHC.TopHandler        <entire-module>      205           0    0.0    0.0     0.0    0.0
 main          Main                  Main.hs:(7,1)-(9,19) 257           0    0.0    0.0     0.0    0.0

Note that it tooks ~30 s for my computer to go through j = 0, 1, …, 85 145 795. I stopped the program manually after that.

Do you have a sense of what values of j might satisfy isInteger ((j * j + 1) / (j + 1))? Could it be that there’s some math trick which would allow you to skip over some values of j?

1 Like
#3

If you compile with -O2 and without profiling it runs in less than 2 seconds on my machine.

1 Like
#5

Another thing I would think about would be to stay far away from using floating-point values and floating-point operations for anything exact. I think the code is trying to select cases where j*j+1 is divisible by j+1, but your isInteger function is going to return true if (j*j+1) / (j+1) is too close to 1 to be distinguishable from 1. I’d go with something exact such as using Integer and testing rem x y == 0 instead.

This is a shot in the dark, since you didn’t actually describe what’s wrong …

3 Likes
#6

Here’s a program that might do what you want, but it runs forever because it can only find two elements in the resulting list and you are asking for 1000:

import Data.Ratio ((%), denominator)
import System.IO (hSetBuffering, stdout, BufferMode(NoBuffering))

isInteger :: Rational -> Bool
isInteger x = denominator x == 1

prf :: Int -> [Integer]
prf n = take n [j | j <- [0..], isInteger ((j * j + 1) % (j + 1)) ]

main :: IO ()
main = do
   putStrLn "Search  Integer result from sequences:"
   hSetBuffering stdout NoBuffering
   print (prf 1000)
1 Like
#7

Thank you a lot but Script do not ended job for me. How show only right result?

1 Like
#8

Depends on what you mean by the right result. To prove that only 0 and 1 should be in the result you would have to check all numbers. That is impossible! If you just want to check up to some bound like 1000 then you can do it like this:

import Data.Ratio ((%), denominator)

isInteger :: Rational -> Bool
isInteger x = denominator x == 1

prf :: Int -> [Integer]
prf n = [j | j <- [0..n], isInteger ((j * j + 1) % (j + 1)) ]

main :: IO ()
main = do
   putStrLn "Search  Integer result from sequences:"
   print (prf 1000)
1 Like