composing floor and sqrt in haskell

floor, haskell, sqrt

Solution

As copumpkin remarked, it might actually be a bad idea to convert to floating point here, because this comes with loss of precision and therefore might, even with rounding, yield incorrect results for sufficiently large integer inputs.

I assume all numbers you're dealing with will at least be small enough that there is some floating-point representation for them, e.g. all are < 10300. But, for instance

Prelude> round(sqrt.fromInteger$10^60 :: Double) ^ 2
1000000000000000039769249677312000395398304974095154031886336
Prelude>  {-   and not   -}     10^60    {-  == (10^30)^2 == (sqrt$10^60) ^ 2  -}
1000000000000000000000000000000000000000000000000000000000000

Which is way off, in terms of absolute difference. Still it's certainly a rather good approximation relative to the numbers themselves, so you can use it as a quickly determined starting point for an algorithm to find the exact result. You can implement Newton/Raphson (in this case AKA Heron) with `Integer`s:

flrt :: Integer -> Integer  -- flrt x ≈ √x,  with  flrt x^2 ≤ x < flrt(x+1)^2
flrt x = approx (round . (sqrt::Double->Double) . fromInteger $ x)
   where approx r
            | ctrl <= x, (r+1)^2 > x  = r
            | otherwise               = approx $ r - diff
          where ctrl = r^2
                diff = (ctrl - x) // (2*r)    -- ∂/∂x x² = 2x

         a//b = a`div`b + if (a>0)==(b>0) then 1 else 0   -- always away from 0

This now works as desired:

*IntegerSqrt> (flrt $ 10^60) ^ 2
1000000000000000000000000000000000000000000000000000000000000

The division always away from 0 in the Newton-Raphson correction is here necessary to prevent getting stuck in an infinite recursion.

Problem

I'm just learning haskell (on my own, for fun) and I've come up against a wall. My Question: How can I define a function ``` flrt = (floor . sqrt) ``` When I try it in a file and compile, GCHi complains with the following: ``` AKS.hs:11:9: No instance for (RealFrac Integer) arising from a use of `floor' Possible fix: add an instance declaration for (RealFrac Integer) In the first argument of `(.)', namely `floor' In the expression: (floor . sqrt) In an equation for `flrt': flrt = (floor . sqrt) AKS.hs:11:17: No instance for (Floating Integer) arising from a use of `sqrt' Possible fix: add an instance declaration for (Floating Integer) In the second argument of `(.)', namely `sqrt' In the expression: (floor . sqrt) In an equation for `flrt': flrt = (floor . sqrt) ``` I don't understand why the resulting function isn't just Int -> Int. I've just finished my second year of CS and done a basic PL course. I've heard of, but don't quite get types yet. I tried reading through a few haskell tutorials but it's all going above my head. P.S. - I also don't understand what a monad is. (a lot of the other questions that my search turned up talked about these) P.P.S. - My full source ``` bar = \a b -> if (2^a) > b then (a-1) else bar (a+1) b foo = bar 1 flrt :: Integer -> Integer flrt = (floor . sqrt) aks target = if (target < 2) then putStr "Not a Prime.\n\n" else if elem (mod target 10) [0,2,4,5,6,8] then putStr "Composite\n\n" else if (elem target) [a^b | a <- [3,5..(flrt target)], b <- [1.. (foo target)]] then putStr "Composite\n\n"--} else putStr "filler" ```

Original source