Hi Patrick,

On Mon, Sep 11, 2017 at 10:44 PM, PATRICK BROWNE <patrick.browne@dit.ie> wrote:

Why is it the sqrt0 function is so much slower than sqrt1. Does the where clause allow intermediate values to be stored?

Regards,

Pat

sqrt0 :: Int -> Int

sqrt0 0 =  0 

sqrt0 1 =  1 

sqrt0 n =   ((sqrt0 (n - 1)) + (n `quot` sqrt0 (n-1))) `quot` 2 

-- sqrt0 25 several minutes

 

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

sqrt0 :: Int -> Int

sqrt0 0 =  0 

sqrt0 1 =  1 

sqrt0 n =   let k = sqrt0 (n - 1) in (k + (n `quot` k)) `quot` 2

 

This code is not blowing exponentially because of you storing intermediate result leading to faster computation.

sqrt1 :: Int -> Int

sqrt1 n 

 | n ==  0              = 0

 | n ==  1              = 1 

 | otherwise            = div (k + ( div n k)) 2

 where k = sqrt1(n-1)

-- sqrt1 25 instant

On 9 September 2017 at 05:49, KC <kc1956@gmail.com> wrote:

One approach 

One function to compute the next iterate

Another function to call the computation function until results are within some tolerance 

It's usually presented as separation of control and computation 😎

--
Sent from an expensive device which will be obsolete in a few months
Casey

On Sep 3, 2017 1:23 AM, "mike h" <mike_k_houghton@yahoo.co.uk> wrote:

Hi,

To help me in learning Haskell I started blogging about some of the things I’ve looked at. 

One such topic was calculating square roots ‘by hand’ and then deriving a Haskell algorithm. 

I wrote about the well known  technique here

http://gitcommit.co.uk/2017/08/25/the-root-of-the-problem-part-1/

and it it is really quite a simple method. 

The second part of the post will be an implementation in Haskell. 

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. 

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. 

I’ve created a gist of the code here

https://gist.github.com/banditpig

Many Thanks

Mike

_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

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. www.dit.ie

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. www.dit.ie

Tá ITBÁC ag aistriú go Gráinseach Ghormáin – DIT is on the move to Grangegorman

_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners