Square root algorithm

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|

Square root algorithm

Mike Houghton
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

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

Many Thanks

Mike

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Square root algorithm

yi lu
I don't know why this email was marked as spam, but it could be worth discussing.

On Sun, Sep 3, 2017 at 4:22 PM, mike h <[hidden email]> 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

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

Many Thanks

Mike

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners



_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
KC
Reply | Threaded
Open this post in threaded view
|

Re: Square root algorithm

KC
In reply to this post by Mike Houghton
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" <[hidden email]> 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

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

Many Thanks

Mike

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Square root algorithm

Mike Houghton
Thanks I’ll look into that.

To recap I have an unattractive but working implementation here https://gist.github.com/banditpig
Thanks

Mike


On 9 Sep 2017, at 05:49, KC <[hidden email]> 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" <[hidden email]> 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

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

Many Thanks

Mike

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Square root algorithm

Mike Houghton
In reply to this post by KC
I’m sort of seeing this as a foldr over a list of digit pairs with the seed value of the fold being the first step of the algorithm (which is different from the other steps).
The list of pairs will be of indeterminate length as ’00’ is used until the required number of digits in the result is achieved.
A minor wrinkle with this is if the input number is a perfect square then a lot of ‘0’s would be in the result.

Then, after the fold,  apply some simple function to determine where the decimal point should go.


M


On 9 Sep 2017, at 05:49, KC <[hidden email]> 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" <[hidden email]> 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

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

Many Thanks

Mike

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Square root algorithm

Patrick Browne
In reply to this post by KC
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
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 <[hidden email]> 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" <[hidden email]> 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

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

Many Thanks

Mike

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners


_______________________________________________
Beginners mailing list
[hidden email]
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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Square root algorithm

mukesh tiwari
Hi Patrick,

On Mon, Sep 11, 2017 at 10:44 PM, PATRICK BROWNE <[hidden email]> 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 <[hidden email]> 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" <[hidden email]> 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

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

Many Thanks

Mike

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners


_______________________________________________
Beginners mailing list
[hidden email]
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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners



_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Square root algorithm

Patrick Browne
Mukesh,
Thanks for your reply.
Does the mean that my original sqrt0 makes (2^25=33554432) function calls?
How many function calls does the let/where versions make?
Thanks,
Pat

On 12 September 2017 at 01:36, mukesh tiwari <[hidden email]> wrote:
Hi Patrick,

On Mon, Sep 11, 2017 at 10:44 PM, PATRICK BROWNE <[hidden email]> 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 <[hidden email]> 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" <[hidden email]> 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

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

Many Thanks

Mike

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners


_______________________________________________
Beginners mailing list
[hidden email]
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
[hidden email]
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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Square root algorithm

mukesh tiwari
Hi Patrick,

On Tue, Sep 12, 2017 at 7:21 PM, PATRICK BROWNE <[hidden email]> wrote:
Mukesh,
Thanks for your reply.
Does the mean that my original sqrt0 makes (2^25=33554432) function calls?
 
 Technically Yes, and more accurately for any given number n, you have 2 ^ (n - 1) call because your base case is 1. 
 
How many function calls does the let/where versions make?

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.

Best,
Mukesh Tiwari
 
Thanks,
Pat

On 12 September 2017 at 01:36, mukesh tiwari <[hidden email]> wrote:
Hi Patrick,

On Mon, Sep 11, 2017 at 10:44 PM, PATRICK BROWNE <[hidden email]> 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 <[hidden email]> 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" <[hidden email]> 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

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

Many Thanks

Mike

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners


_______________________________________________
Beginners mailing list
[hidden email]
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
[hidden email]
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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Square root algorithm

Mike Houghton
On the original ‘using pairs’ algorithm I’ve now coded something slightly cleaner than the original State based one. 
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.
An easier to read copy of the code  is at http://gitcommit.co.uk/2017/09/15/the-root-of-the-problem-part-2/

and the raw code is below. Thanks 
Mike


———————
import Data.List.Split
import Data.Char 
import Numeric

-- The entry point.
root :: Float -> Float
root n = f   where
  ((f, _):_) = readFloat (lhs ++ "." ++ rhs)
  (_, rootDigits) = rootFold n
  (lhs, rhs) = splitAt (dpLocation n) rootDigits
--    
-- fold with the initial value based on intSquareRoot function
-- and subsequent calculations based on doubling and the biggestN function.
rootFold :: Float -> (Integer, String)
rootFold n = foldr  calculate (makeStartVal p1 p2) pairs where
  (p1:p2:pairs) = digitList  n 

  makeStartVal :: Integer -> Integer -> (Integer, String)
  makeStartVal p1 p2 = res where
    rt =  intSquareRoot  p1
    res = (p2 + (p1 - rt * rt) * 100 , show rt)

  calculate :: Integer -> (Integer, String) -> (Integer, String)
  calculate  p (n, res) = next where
    (toAppend, remain) = biggestN (2 * read res) n
    -- bring down the next pair and accumulate the result
    next = (remain * 100 + p, res ++ show toAppend)

-- Where should decimal point be?
dpLocation :: Float -> Int
dpLocation n =  if (even len) then len `div` 2 else (len + 1) `div` 2  where
  [left, _] = splitOn "." . show $ n
  len = length left
 
-- helper for formatting
formatFloatN numOfDecimals floatNum  = showFFloat (Just numOfDecimals) floatNum ""
showFlt = formatFloatN 16

-- Takes float and makes list of 'paired' integers
digitList :: Float -> [Integer]
digitList n = res where
    [l, r] = splitOn "." . showFlt $ n
    res = map read $ (pairs . pad $ l) ++  (pairs . pad $ r) where
      pairs [] = []
      pairs xs =
        let (ys, zs) = splitAt 2 xs
        in  ys : pairs  zs
      pad xs 
        | odd . length $ xs = "0" ++ xs
        | otherwise = xs

     
-- eg  largest number N such that 4N x N <= 161 
-- and biggestN 4 161 = (3, 32)
--
biggestN :: Integer -> Integer -> (Integer, Integer)
biggestN  = get 0  where 
    get n x y 
        | (x*10 + n) * n >  y = (n-1, y - (x*10 + n - 1)*(n - 1))
        | (x*10 + n) * n == y = (n  , y - (x*10 + n) * n )
        | otherwise           = get (n + 1) x y

-- gives the largest int whose square is <= n
intSquareRoot :: Integer -> Integer
intSquareRoot n = root 0 where
  root i   
   | i*i <= n  = root (i + 1) 
   | otherwise = i - 1

———————


On 13 Sep 2017, at 02:37, mukesh tiwari <[hidden email]> wrote:

Hi Patrick,

On Tue, Sep 12, 2017 at 7:21 PM, PATRICK BROWNE <[hidden email]> wrote:
Mukesh,
Thanks for your reply.
Does the mean that my original sqrt0 makes (2^25=33554432) function calls?
 
 Technically Yes, and more accurately for any given number n, you have 2 ^ (n - 1) call because your base case is 1. 
 
How many function calls does the let/where versions make?

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.

Best,
Mukesh Tiwari
 
Thanks,
Pat

On 12 September 2017 at 01:36, mukesh tiwari <[hidden email]> wrote:
Hi Patrick,

On Mon, Sep 11, 2017 at 10:44 PM, PATRICK BROWNE <[hidden email]> 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 <[hidden email]> 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" <[hidden email]> 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

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

Many Thanks

Mike

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners


_______________________________________________
Beginners mailing list
[hidden email]
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
[hidden email]
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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners