My Weblog

Blog about programming and math

Newton–Raphson method to solve Ax+Bsin(x)=C

I was reading Newton–Raphson method and realized that you can encode this whole algorithm using until function in Haskell.

Type signature of until 
ghci>:t until
until :: (a -> Bool) -> (a -> a) -> a -> a

To encode Newton-Raphson algorithm in until

until ( you testing condition ) ( function )  ( initial value of x )

TRIGALGE is related to Newton-Raphson . \sin x will be in between [ -1.0 , 1.0 ] so Ax - B \leq C \leq Ax + B . My initial guess was \frac{C-B}{A} . See this stackoverflow discussion for initial approximation. Accepted Haskell code.

import Data.ByteString.Lazy.Char8 as BS hiding  ( map , tail , filter  , null )
import Data.Maybe ( fromJust )
import Text.Printf ( printf )

diffEQ :: Double -> Double -> Double -> Double
diffEQ a b x = a + b * cos x

valEQ :: Double -> Double -> Double -> Double -> Double
valEQ a b c x = a * x   +  b * sin x - c

evalFun :: [ Int ]  -> Double
evalFun [ a' , b' , c' ]  = ret where
          ( a , b , c  ) = ( fromIntegral a' , fromIntegral b' , fromIntegral c' )
          ret = fst . until ( \ ( _ , cnt ) -> cnt  >=  500 )  ( \( x , cnt ) -> ( x - (  valEQ a b c x  /  diffEQ a b x ) , succ cnt ) ) $ (  ( c - b ) / a  , 0   )

readD :: BS.ByteString -> Int
readD = fst . fromJust . BS.readInt

main = BS.interact $ BS.unlines . map (  BS.pack . ( printf "%.6f" :: Double -> String ) . evalFun .  map readD ) . filter ( not.null ) . map BS.words . tail . BS.lines

Changing the initial approximation of \frac{C}{A} and 50 iteration improves the time by 0.60 seconds ( from 0.80 to 0.22 ).

Advertisements

January 4, 2013 - Posted by | Haskell, Programming | , , ,

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: