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):



This gives me syntax errors. But the (seemingly) equivalent



gives me divide by zero errors. I'm not sure what is wrong: the math or my Haskell. Any help would be appreciated.

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

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.

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

For the first, count your parenthesis:




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:

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-program...way-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.)

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.