<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">On the original ‘using pairs’ algorithm I’ve now coded something slightly cleaner than the original State based one. <div class="">There’s still a lot of code for a seemingly simple problem but I s’pose a lot of the functions are helpers for various things and the core of the solution is contained in the fold.</div><div class="">An easier to read copy of the code is at <a href="http://gitcommit.co.uk/2017/09/15/the-root-of-the-problem-part-2/" class="">http://gitcommit.co.uk/2017/09/15/the-root-of-the-problem-part-2/</a></div><div class=""><br class=""></div><div class="">and the raw code is below. Thanks </div><div class="">Mike</div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">———————</div><div class=""><div class="">import Data.List.Split</div><div class="">import Data.Char </div><div class="">import Numeric</div><div class=""><br class=""></div><div class="">-- The entry point.</div><div class="">root :: Float -> Float</div><div class="">root n = f where</div><div class=""> ((f, _):_) = readFloat (lhs ++ "." ++ rhs)</div><div class=""> (_, rootDigits) = rootFold n</div><div class=""> (lhs, rhs) = splitAt (dpLocation n) rootDigits</div><div class="">-- </div><div class="">-- fold with the initial value based on intSquareRoot function</div><div class="">-- and subsequent calculations based on doubling and the biggestN function.</div><div class="">rootFold :: Float -> (Integer, String)</div><div class="">rootFold n = foldr calculate (makeStartVal p1 p2) pairs where</div><div class=""> (p1:p2:pairs) = digitList n </div><div class=""><br class=""></div><div class=""> makeStartVal :: Integer -> Integer -> (Integer, String)</div><div class=""> makeStartVal p1 p2 = res where</div><div class=""> rt = intSquareRoot p1</div><div class=""> res = (p2 + (p1 - rt * rt) * 100 , show rt)</div><div class=""><br class=""></div><div class=""> calculate :: Integer -> (Integer, String) -> (Integer, String)</div><div class=""> calculate p (n, res) = next where</div><div class=""> (toAppend, remain) = biggestN (2 * read res) n</div><div class=""> -- bring down the next pair and accumulate the result</div><div class=""> next = (remain * 100 + p, res ++ show toAppend)</div><div class=""><br class=""></div><div class="">-- Where should decimal point be?</div><div class="">dpLocation :: Float -> Int</div><div class="">dpLocation n = if (even len) then len `div` 2 else (len + 1) `div` 2 where</div><div class=""> [left, _] = splitOn "." . show $ n</div><div class=""> len = length left</div><div class=""> </div><div class="">-- helper for formatting</div><div class="">formatFloatN numOfDecimals floatNum = showFFloat (Just numOfDecimals) floatNum ""</div><div class="">showFlt = formatFloatN 16</div><div class=""><br class=""></div><div class="">-- Takes float and makes list of 'paired' integers</div><div class="">digitList :: Float -> [Integer]</div><div class="">digitList n = res where</div><div class=""> [l, r] = splitOn "." . showFlt $ n</div><div class=""> res = map read $ (pairs . pad $ l) ++ (pairs . pad $ r) where</div><div class=""> pairs [] = []</div><div class=""> pairs xs =</div><div class=""> let (ys, zs) = splitAt 2 xs</div><div class=""> in ys : pairs zs</div><div class=""> pad xs </div><div class=""> | odd . length $ xs = "0" ++ xs</div><div class=""> | otherwise = xs</div><div class=""><br class=""></div><div class=""> </div><div class="">-- eg largest number N such that 4N x N <= 161 </div><div class="">-- and biggestN 4 161 = (3, 32)</div><div class="">--</div><div class="">biggestN :: Integer -> Integer -> (Integer, Integer)</div><div class="">biggestN = get 0 where </div><div class=""> get n x y </div><div class=""> | (x*10 + n) * n > y = (n-1, y - (x*10 + n - 1)*(n - 1))</div><div class=""> | (x*10 + n) * n == y = (n , y - (x*10 + n) * n )</div><div class=""> | otherwise = get (n + 1) x y</div><div class=""><br class=""></div><div class="">-- gives the largest int whose square is <= n</div><div class="">intSquareRoot :: Integer -> Integer</div><div class="">intSquareRoot n = root 0 where</div><div class=""> root i </div><div class=""> | i*i <= n = root (i + 1) </div><div class=""> | otherwise = i - 1</div><div class=""><br class=""></div></div><div class="">———————</div><div class=""><br class=""></div><div class=""><br class=""><div><blockquote type="cite" class=""><div class="">On 13 Sep 2017, at 02:37, mukesh tiwari <<a href="mailto:mukeshtiwari.iiitm@gmail.com" class="">mukeshtiwari.iiitm@gmail.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class="">Hi Patrick, <br class=""><div class="gmail_extra"><br class=""><div class="gmail_quote">On Tue, Sep 12, 2017 at 7:21 PM, PATRICK BROWNE <span dir="ltr" class=""><<a href="mailto:patrick.browne@dit.ie" target="_blank" class="">patrick.browne@dit.ie</a>></span> wrote:<br class=""><blockquote class="gmail_quote" style="margin:0 0 0 ..8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr" class="">Mukesh,<div class="">Thanks for your reply.</div><div class="">Does the mean that my original sqrt0 makes (2^25=33554432) function calls?</div></div></blockquote><div class=""> </div><div class=""> Technically Yes, and more accurately for any given number n, you have 2 ^ (n - 1) call because your base case is 1. <br class=""></div><div class=""> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr" class=""><div class="">How many function calls does the let/where versions make?</div></div></blockquote><div class=""><br class=""></div><div class="">With let/where version you store the value of function call in in variable, so no more second call and total functional in this scenario is linear in number n. For you case with n = 25 the number of function calls is just 24. <br class=""></div><div class=""><br class=""></div><div class="">Best, <br class=""></div><div class="">Mukesh Tiwari<br class=""></div><div class=""> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr" class=""><div class="">Thanks,</div><div class="">Pat</div></div><div class="gmail_extra"><br class=""><div class="gmail_quote">On 12 September 2017 at 01:36, mukesh tiwari <span dir="ltr" class=""><<a href="mailto:mukeshtiwari.iiitm@gmail.com" target="_blank" class="">mukeshtiwari.iiitm@gmail.com</a>></span> wrote:<br class=""><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr" class="">Hi Patrick, <br class=""><div class=""><div class="gmail_extra"><br class=""><div class="gmail_quote"><span class="">On Mon, Sep 11, 2017 at 10:44 PM, PATRICK BROWNE <span dir="ltr" class=""><<a href="mailto:patrick.browne@dit.ie" target="_blank" class="">patrick.browne@dit.ie</a>></span> wrote:<br class=""><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr" class=""><div class="">Why is it the sqrt0 function is so much slower than sqrt1. Does the where clause allow intermediate values to be stored?</div><div class="">Regards,</div><div class="">Pat</div><div class="">sqrt0 :: Int -> Int</div><div class="">sqrt0 0 = 0 </div><div class="">sqrt0 1 = 1 </div><div class="">sqrt0 n = ((sqrt0 (n - 1)) + (n `quot` sqrt0 (n-1))) `quot` 2 </div><div class="">-- sqrt0 25 several minutes<br class=""></div></div></blockquote><div class=""> </div></span><div class="">In sqrt0, each function call with n > 1 creates two more function call, and this creates exponential blow up (factor of 2). You can make your code it faster by storing the intermediate result<br class=""></div><div class=""><br class=""></div><div class=""><span class=""><div class="">sqrt0 :: Int -> Int</div><div class="">sqrt0 0 = 0 </div><div class="">sqrt0 1 = 1 </div></span><div class="">sqrt0 n = let k = sqrt0 (n - 1) in (k + (n `quot` k)) `quot` 2 <br class=""></div></div><div class=""> </div><div class="">This code is not blowing exponentially because of you storing intermediate result leading to faster computation.</div><div class=""><br class=""></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div class=""><div class="m_-1694153706539080484h5"><div dir="ltr" class=""><div class=""></div><div class="">sqrt1 :: Int -> Int</div><div class="">sqrt1 n </div><div class=""> | n == 0 = 0</div><div class=""> | n == 1 = 1 </div><div class=""> | otherwise = div (k + ( div n k)) 2</div><div class=""> where k = sqrt1(n-1)</div><div class="">-- sqrt1 25 instant<br class=""></div><div class=""><br class=""></div></div><div class="gmail_extra"><br class=""><div class="gmail_quote">On 9 September 2017 at 05:49, KC <span dir="ltr" class=""><<a href="mailto:kc1956@gmail.com" target="_blank" class="">kc1956@gmail.com</a>></span> wrote:<br class=""><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="auto" class="">One approach <div dir="auto" class=""><br class=""></div><div dir="auto" class="">One function to compute the next iterate</div><div dir="auto" class=""><br class=""></div><div dir="auto" class="">Another function to call the computation function until results are within some tolerance </div><div dir="auto" class=""><br class=""></div><div dir="auto" class="">It's usually presented as separation of control and computation 😎<br class=""><br class=""><div dir="auto" class="">--<br class="">Sent from an expensive device which will be obsolete in a few months<br class="">Casey</div></div></div><div class="m_-1694153706539080484m_-8162227982148736475gmail-m_-2211523315161561755HOEnZb"><div class="m_-1694153706539080484m_-8162227982148736475gmail-m_-2211523315161561755h5"><div class="gmail_extra"><br class=""><div class="gmail_quote">On Sep 3, 2017 1:23 AM, "mike h" <<a href="mailto:mike_k_houghton@yahoo.co.uk" target="_blank" class="">mike_k_houghton@yahoo.co.uk</a>> wrote:<br type="attribution" class=""><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div class="">Hi,<div class=""><br class=""></div><div class="">To help me in learning Haskell I started blogging about some of the things I’ve looked at. </div><div class="">One such topic was calculating square roots ‘by hand’ and then deriving a Haskell algorithm. </div><div class="">I wrote about the well known technique here</div><div class=""><a href="http://gitcommit.co.uk/2017/08/25/the-root-of-the-problem-part-1/" target="_blank" class="">http://gitcommit.co.uk/2017/08<wbr class="">/25/the-root-of-the-problem-pa<wbr class="">rt-1/</a></div><div class=""><br class=""></div><div class="">and it it is really quite a simple method. </div><div class=""><br class=""></div><div class="">The second part of the post will be an implementation in Haskell. </div><div class=""><br class=""></div><div class="">I then tried implementing it and got something that works but really its not very pleasant to look at! And its something I don’t want to post! Some parts are fine but I think I locked myself into the notion that it had to be using State and really the end result is pretty poor. </div><div class=""><br class=""></div><div class="">I know this i perhaps a ‘big ask’ but I’d really appreciate any suggestions, solutions, hints etc. I will of course give full attribution. </div><div class=""><br class=""></div><div class="">I’ve created a gist of the code here</div><div class=""><a href="https://gist.github.com/banditpig" target="_blank" class="">https://gist.github.com/bandit<wbr class="">pig</a></div><div class=""><br class=""></div><div class="">Many Thanks</div><div class=""><br class=""></div><div class="">Mike</div></div><br class="">______________________________<wbr class="">_________________<br class="">
Beginners mailing list<br class="">
<a href="mailto:Beginners@haskell.org" target="_blank" class="">Beginners@haskell.org</a><br class="">
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" rel="noreferrer" target="_blank" class="">http://mail.haskell.org/cgi-bi<wbr class="">n/mailman/listinfo/beginners</a><br class="">
<br class=""></blockquote></div></div>
</div></div><br class="">______________________________<wbr class="">_________________<br class="">
Beginners mailing list<br class="">
<a href="mailto:Beginners@haskell.org" target="_blank" class="">Beginners@haskell.org</a><br class="">
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" rel="noreferrer" target="_blank" class="">http://mail.haskell.org/cgi-bi<wbr class="">n/mailman/listinfo/beginners</a><br class="">
<br class=""></blockquote></div><br class=""></div>
<br class="">
</div></div><p class=""><span lang="EN-GB" class=""><font size="2" class="">This email originated from DIT. If you received this email in error, please delete it from your system. Please note that if you are not the named addressee, disclosing, copying, distributing or taking any action based on the contents of this email or attachments is prohibited. <a href="http://www.dit.ie/" target="_blank" class="">www.dit.ie</a></font></span></p><p class=""><font size="2" class="">Is ó ITBÁC
a tháinig an ríomhphost seo. Má fuair tú an ríomhphost seo trí earráid, scrios
de do chóras é le do thoil. Tabhair ar aird, mura tú an seolaí ainmnithe, go
bhfuil dianchosc ar aon nochtadh, aon chóipeáil, aon dáileadh nó ar aon ghníomh
a dhéanfar bunaithe ar an ábhar atá sa ríomhphost nó sna hiatáin seo. <a href="http://www.dit.ie/" target="_blank" class="">www.dit.ie</a></font></p><p class=""><a href="http://www.dit.ie/grangegorman" target="_blank" class=""><font size="2" class="">Tá ITBÁC ag aistriú go Gráinseach Ghormáin – DIT is on the move to Grangegorman</font></a></p><span class=""><br class="">______________________________<wbr class="">_________________<br class="">
Beginners mailing list<br class="">
<a href="mailto:Beginners@haskell.org" target="_blank" class="">Beginners@haskell.org</a><br class="">
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" rel="noreferrer" target="_blank" class="">http://mail.haskell.org/cgi-bi<wbr class="">n/mailman/listinfo/beginners</a><br class="">
<br class=""></span></blockquote></div><br class=""></div></div></div>
</blockquote></div><br class=""></div>
<br class=""><p class=""><span lang="EN-GB" class=""><font size="2" class="">This email originated from DIT. If you received this email in error, please delete it from your system. Please note that if you are not the named addressee, disclosing, copying, distributing or taking any action based on the contents of this email or attachments is prohibited. <a href="http://www.dit.ie/" target="_blank" class="">www.dit.ie</a></font></span></p><p class=""><font size="2" class="">Is ó ITBÁC
a tháinig an ríomhphost seo. Má fuair tú an ríomhphost seo trí earráid, scrios
de do chóras é le do thoil. Tabhair ar aird, mura tú an seolaí ainmnithe, go
bhfuil dianchosc ar aon nochtadh, aon chóipeáil, aon dáileadh nó ar aon ghníomh
a dhéanfar bunaithe ar an ábhar atá sa ríomhphost nó sna hiatáin seo. <a href="http://www.dit.ie/" target="_blank" class="">www.dit.ie</a></font></p><p class=""><a href="http://www.dit.ie/grangegorman" target="_blank" class=""><font size="2" class="">Tá ITBÁC ag aistriú go Gráinseach Ghormáin – DIT is on the move to Grangegorman</font></a></p></blockquote></div><br class=""></div></div>
_______________________________________________<br class="">Beginners mailing list<br class=""><a href="mailto:Beginners@haskell.org" class="">Beginners@haskell.org</a><br class="">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners<br class=""></div></blockquote></div><br class=""></div></body></html>