[Haskell-beginners] Square root algorithm

[mukesh tiwari]

Hi Patrick,

On Mon, Sep 11, 2017 at 10:44 PM, PATRICK BROWNE <patrick.browne at 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 at 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 at 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 at haskell.org
>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>>
>>>
>> _______________________________________________
>> Beginners mailing list
>> Beginners at 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 <http://www.dit.ie/grangegorman>
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20170912/246d93a7/attachment.html>