Programming Praxis – Egyptian Fractions

In today’s Programming Praxis exercise, our goal is to convert a given fraction to a sum of fractions with numerator 1. Let’s get started, shall we?

import Data.Ratio

The implementation is fairly similar to the provided one. The main difference is that the ceiling of the fraction is performed via a div, eliminating potential problems with floating point inaccuracies.

egypt :: Integer -> Integer -> [Integer]
egypt 1 d = [d]
egypt n d = e : egypt (numerator r) (denominator r)
            where (e,r) = (div (d+n-1) n, n%d - 1%e)

Some tests to see if everything is working properly:

main :: IO ()
main = do print $ egypt 5 6 == [2,3]
          print $ egypt 7 15 == [3,8,120]
          print $ egypt 5 121 == [25,757,763309,873960180913
                                 ,1527612795642093418846225]
About these ads

Tags: , , , , , , ,

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


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: