June 22nd, 2010, 06:46 AM

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 (n1)  div (n  isqrt (n1) (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 (nm) (2*m))
where m = isqrt (n1)
gives me divide by zero errors. I'm not sure what is wrong: the math or my Haskell. Any help would be appreciated.
June 22nd, 2010, 12:07 PM

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.
June 22nd, 2010, 12:32 PM

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.
June 23rd, 2010, 09:14 AM

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.
June 23rd, 2010, 07:44 PM

For the first, count your parenthesis:
Code:
isqrt :: Int > Int
isqrt n  n < 4 = 1
 otherwise = isqrt (n1)  div (n  isqrt (n1) (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
sub{*{$::{$_}}{CODE}==$_[0]&& print for(%:: )}>(\&Meh);
June 26th, 2010, 01:22 PM

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/cprogramm...ay700404.html
In general, you can't just replace realnumber 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(n1) to compute isqrt(n); if you're doing it that way, then the only sane solution is to check if (isqrt(n1)+1)^2 is still greater than n, and select isqrt(n1) or isqrt(n1)+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 floatingpoint 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.