#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2010
    Posts
    6
    Rep Power
    0

    Integer Square Root


    Hi: I'm new to programming, and decided to learn Haskell. I am working through Thompson's book. Exercise 4.8 wants me to define a function which finds the integer square root of a positive integer by recursion.

    I assume that I can use Newton's Method to successively approximate values of m in n = m^2. I want as my first approximation

    m1 = (n/2) - (n - (n/2)^2)) / (2*(n/2)),

    because this will generate a sufficiently close value for the square root function, and I want to define the square root by:

    mi+1 = mi - ((n - mi^1) / 2*mi).

    I'm fairly sure that this will define sqrt n. For the integer square root, I think I could use whole number division, so:

    m1 = (div n 2) - (n - (n/2)^2)) `div` (2*(n/2))
    mi+1 = mi - ((n - mi^1) 'div' 2*mi).

    (A) I don't understand how to get Haskell to define m1.

    (B) When I use the "primitive recursion" format, I went from (n - 1), because of (A). But the following Haskell code doesn't work, and I can't figure out why (probably because it's incorrect, of course):

    Code:
    isqrt :: Int -> Int
    isqrt n | n < 4     = 1
            | otherwise = isqrt (n-1) - div (n - isqrt (n-1) (2 * isqrt (n -1))
    This gives me syntax errors. But the (seemingly) equivalent

    Code:
    isqrt :: Int -> Int
    isqrt n | n < 4     = 1
            | otherwise = m - (div (n-m) (2*m))
              where m = isqrt (n-1)
    gives me divide by zero errors. I'm not sure what is wrong: the math or my Haskell. Any help would be appreciated.
  2. #2
  3. Sarcky
    Devshed Supreme Being (6500+ posts)

    Join Date
    Oct 2006
    Location
    Pennsylvania, USA
    Posts
    10,908
    Rep Power
    6352
    1) You might want to check out this thread in the C programming forum which specifically deals with square roots.

    2) Why did you choose to learn haskell?

    -Dan
    HEY! YOU! Read the New User Guide and Forum Rules

    "They that can give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety." -Benjamin Franklin

    "The greatest tragedy of this changing society is that people who never knew what it was like before will simply assume that this is the way things are supposed to be." -2600 Magazine, Fall 2002

    Think we're being rude? Maybe you asked a bad question or you're a Help Vampire. Trying to argue intelligently? Please read this.
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2010
    Posts
    6
    Rep Power
    0
    1. I skimmed over the linked articles, but that's not what I'm looking for, particularly. I'm fairly sure the function definition should recursively define sqrt(n). If someone knows better though, then it would be helpful if they could point out where I am wrong; if the code is incorrect, it would be helpful if someone could point me in the right direction.

    2. I'm interested in Haskell via logic. So I thought learning Haskell would be a good way to talk about, and implement, what I am doing with different logics. I'm not interested in applications, efficiency, or anything like that.
  6. #4
  7. Sarcky
    Devshed Supreme Being (6500+ posts)

    Join Date
    Oct 2006
    Location
    Pennsylvania, USA
    Posts
    10,908
    Rep Power
    6352
    Generally, computers aren't great at handling floating point numbers. Most square root implementations are "close enough." For instance, the article I gave you shows that for Quake 3, a single iteration of the square root guessing formula was good enough for most applications. Two iterations was better, but not significantly so. You shouldn't need more than a few iterations, and there are some numbers where you'll never be able to calculate the actual square root, no matter how many iterations you use.

    I can't help you with your actual Haskell problems, as I don't know the language. I will say that all programming languages are Turing Complete, so there's nothing that one language can do that another language cannot. Some things are just easier in one language than another. I prefer Lisp for functional, logical programming.

    You may also want to check out an actual logical language, like Fitch Calculus. Logical languages cannot be compiled by a computer, but they're actually used for the formal study of logic itself.

    -Dan
    HEY! YOU! Read the New User Guide and Forum Rules

    "They that can give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety." -Benjamin Franklin

    "The greatest tragedy of this changing society is that people who never knew what it was like before will simply assume that this is the way things are supposed to be." -2600 Magazine, Fall 2002

    Think we're being rude? Maybe you asked a bad question or you're a Help Vampire. Trying to argue intelligently? Please read this.
  8. #5
  9. No Profile Picture
    Contributing User
    Devshed Novice (500 - 999 posts)

    Join Date
    May 2007
    Posts
    765
    Rep Power
    929
    For the first, count your parenthesis:

    Code:
    isqrt :: Int -> Int
    isqrt n | n < 4     = 1
            | otherwise = isqrt (n-1) - div (n - isqrt (n-1) (2 * isqrt (n -1))

    For the second the reason it doesn't work is you've misunderstood the formula and you have a few errors in it as well. (Use algebra to reduce that monster formula of your initial guess and see what you get).

    Here's the formula you want described iteratively:

    Code:
    M = initial guess
    
    Until M is good enough:
        M = M - ( (M**2 - N) / (2 * N) )

    Comments on this post

    • ManiacDan agrees
    sub{*{$::{$_}}{CODE}==$_[0]&& print for(%:: )}->(\&Meh);
  10. #6
  11. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Feb 2004
    Location
    San Francisco Bay
    Posts
    1,939
    Rep Power
    1313
    I don't think ManiacDan's article will help you too much, since you're working with integers, and presumably you want the answer to be exact (in the sense of being the floor or ceiling of the true square root). This thread may be useful to you: http://forums.devshed.com/c-programm...ay-700404.html

    In general, you can't just replace real-number division with integer division in an algorithm (such as Newton's method) and expect it to work, since the two are not mathematically equivalent.

    However, what you're implementing there isn't Newton's method at all. Newton's method wouldn't look at isqrt(n-1) to compute isqrt(n); if you're doing it that way, then the only sane solution is to check if (isqrt(n-1)+1)^2 is still greater than n, and select isqrt(n-1) or isqrt(n-1)+1 accordingly. (That assumes you really want floor(sqrt(n)); if you want it rounded to the nearest integer or something, then it's slightly more complicated.)

    Originally Posted by ManiacDan
    Generally, computers aren't great at handling floating point numbers. Most square root implementations are "close enough." For instance, the article I gave you shows that for Quake 3, a single iteration of the square root guessing formula was good enough for most applications. Two iterations was better, but not significantly so. You shouldn't need more than a few iterations, and there are some numbers where you'll never be able to calculate the actual square root, no matter how many iterations you use.
    Actually, on a machine that implements IEEE floating-point arithmetic, hardware square roots are as accurate as the type can represent. (Not all FPUs do, but I believe those that do are the vast majority now.) Of course, that guarantee goes out the window if you use a custom subroutine.

IMN logo majestic logo threadwatch logo seochat tools logo