My Weblog

Blog about programming and math

SPOJ 291. Cube Root

SPOJ 291. Cube Root ‘s difficulty is about parsing inputs. Haskell provides very neat functions to parse inputs so just concentrate of solving problem . Lets say a is integer and b is fraction part of cube root of n so ( a + b ) ^ 3 = n . a^{3} + b^{3} + 3*a*b*(a+b) = n => b^{3} + 3*a*b*(a+b) = n - a^{3} . First i searched using binary search on Integer values for Integer part of cube root and then again binary search between 0 and 1 to find out b. Here is source code.

import Data.List
import qualified Data.Char as DC
import Numeric

format :: [[String]] -> [Integer]
format [] = []
format (x:xs)  = if null x then format xs else  ( map read x ) ++  format xs

cbrtNewton :: Double  -> Double -> Double
cbrtNewton 0 _ = 0
cbrtNewton x a = bsearch 0 1 where
	bsearch lo hi | abs ( lo - hi ) <= 1e-12 = lo
          	      | mid * ( mid * ( mid + 3*a ) + 3*a**2) <= x = bsearch mid hi
          	      | otherwise = bsearch lo mid
          	      where mid = ( lo + hi ) * ( 0.5 )

    --upperbound search
search :: Integer -> Integer
search 1 = 1
search n = bsearch 1  n  where
      bsearch lo hi | lo >= hi = ( lo - 1 )
          	    | mid ^ 3 <= n = bsearch ( mid + 1 ) hi
                    | otherwise = bsearch lo mid
          	    where mid = div ( lo + hi ) 2

solve :: Integer -> String
solve x =  a where
          y = search x
          z = showFFloat Nothing ( cbrtNewton ( fromIntegral ( x - y^3 ) ) ( fromIntegral y ) ) ""
          z' = tail . take 12 $  z  ++ "0000000000000000000000000000000000000"
          ps = show $ mod ( foldl ( \acc x -> if DC.isDigit x then acc + DC.digitToInt x else acc ) 0 ( show y ++ z' ) ) 10
          a = ps ++ " " ++ show y ++  z'

main = interact $  unlines.map  solve .  format .map words . tail . lines
Advertisements

May 31, 2011 - Posted by | 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: