Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |
 User Name: Password: Remember me

The Shed is going Social! Join us on FaceBook and Twitter and chime in on the conversation.

 Dev Shed Forums Sponsor:
#1
June 22nd, 2010, 06:46 AM
 quickly
Registered User

Join Date: Jun 2010
Posts: 6
Time spent in forums: 4 h 1 m 40 sec
Reputation 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
June 22nd, 2010, 12:07 PM
 ManiacDan
Likely to be eaten by a grue.

Join Date: Oct 2006
Location: Pennsylvania, USA
Posts: 9,801
Time spent in forums: 2 Months 3 Weeks 16 h 59 m 20 sec
Reputation Power: 6112
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.

#3
June 22nd, 2010, 12:32 PM
 quickly
Registered User

Join Date: Jun 2010
Posts: 6
Time spent in forums: 4 h 1 m 40 sec
Reputation 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.

#4
June 23rd, 2010, 09:14 AM
 ManiacDan
Likely to be eaten by a grue.

Join Date: Oct 2006
Location: Pennsylvania, USA
Posts: 9,801
Time spent in forums: 2 Months 3 Weeks 16 h 59 m 20 sec
Reputation Power: 6112
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

#5
June 23rd, 2010, 07:44 PM
 OmegaZero
Contributing User

Join Date: May 2007
Posts: 737
Time spent in forums: 3 Weeks 4 Days 23 h 10 m 23 sec
Reputation Power: 928
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);

#6
June 26th, 2010, 01:22 PM
 Lux Perpetua
Contributing User

Join Date: Feb 2004
Location: San Francisco Bay
Posts: 1,936
Time spent in forums: 1 Month 1 Week 2 h 12 m 42 sec
Reputation Power: 1312
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.)

Quote:
 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.

 Viewing: Dev Shed Forums > Programming Languages - More > Other Programming Languages > Integer Square Root

## Developer Shed Advertisers and Affiliates

 Thread Tools Search this Thread Search this Thread: Advanced Search Display Modes Rate This Thread Linear Mode Rate This Thread: 5 : Excellent 4 : Good 3 : Average 2 : Bad 1 : Terrible

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts vB code is On Smilies are On [IMG] code is On HTML code is Off
 View Your Warnings | New Posts | Latest News | Latest Threads | Shoutbox Forum Jump Please select one User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home -------------------- Programming Languages    PHP Development        PHP FAQs and Stickies    Perl Programming        Perl FAQs and Stickies    C Programming        C Programming FAQs and Stickies    Java Help        Java FAQs    Python Programming        Python Programming FAQs    Ruby Programming        Ruby Programming FAQs    Game Development        Game Development FAQs Programming Languages - More    ASP Programming        ASP Programming FAQs    .Net Development        .Net Development FAQs    Visual Basic Programming        Visual Basic Programming FAQs    Software Design        Software Design FAQs    ColdFusion Development        ColdFusion Development FAQs    Delphi Programming        Delphi Programming FAQs    Regex Programming        Regex Programming FAQs    XML Programming        XML Programming FAQs    Other Programming Languages        Other Programming Languages FAQs Web Design    HTML Programming        HTML Programming FAQs    JavaScript Development        JavaScript Development FAQs    CSS Help        CSS Help FAQs    Flash Help        Flash Help FAQs    Photoshop Help        Photoshop Help FAQs    Web Design Help        Web Design Help FAQs    Website Critiques        Website Critiques FAQs    Search Engine Optimization        Search Engine Optimization FAQs Mobile Programming    Mobile Programming        Mobile Programming FAQs    iPhone SDK Development        iPhone SDK Development FAQs    Android Development        Android Development FAQs    BlackBerry Development        BlackBerry Development FAQs Web Site Management    Business Help        Business Help FAQs    Development Software        Development Software FAQs    Scripts        Scripts FAQs Databases    Database Management        Database Management FAQs    DB2 Development        DB2 Development FAQs    MySQL Help        MySQL Help FAQs    PostgreSQL Help        PostgreSQL Help FAQs    Firebird SQL Development        Firebird SQL Development FAQs    MS SQL Development        MS SQL Development FAQs    Oracle Development        Oracle Development FAQs    LDAP Programming        LDAP Programming FAQs System Administration    Mail Server Help        Mail Server Help FAQs    Apache Development        Apache Development FAQs    Security and Cryptography        Security and Cryptography FAQs    Antivirus Protection        Antivirus Protection FAQs    DNS        DNS FAQs    IIS        IIS FAQs    Networking Help        Networking Help FAQs    FTP Help        FTP Help FAQs Operating Systems    BSD Help        BSD Help FAQs    Linux Help        Linux Help FAQs    UNIX Help        UNIX Help FAQs    Windows Help        Windows Help FAQs    Mac Help        Mac Help FAQs Web Hosting    Web Hosting        Web Hosting FAQs    Free Web Hosting        Free Web Hosting FAQs    Web Hosting Requests        Web Hosting Requests FAQs    Web Hosting Offers        Web Hosting Offers FAQs Computer Hardware    Computer Hardware    CPUs        CPUs FAQs    Cooling        Cooling FAQs    Embedded Programming        Embedded Programming FAQs    Motherboards        Motherboards FAQs    Multimedia Hardware        Multimedia Hardware FAQs Other    Dev Shed Lounge        Dev Shed Lounge FAQs    Development Articles        Development Articles FAQs    Beginner Programming        Beginner Programming FAQs    Hire A Programmer        Hire A Programmer FAQs    Project Help Wanted        Project Help Wanted FAQs Latest News Updated Hourly    Technology News    Business News    Science News Forum Information    Forum Rules/Guidelines        Forum Rules/Guidelines FAQs    Forum Announcements        Forum Announcements FAQs    Dev Shed Gaming Center        Go to the Dev Shed Battle Arena        Go to the Dev Shed Arcade Games        Go to the Legend of the Green Dragon    Suggestions & Feedback        Suggestions & Feedback FAQs

 Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |