Converting Floats to integers - Haskell
Taz
would be great!
My Task: define a function that takes an int parameter (n) and returns the
nth decimal point of root2
i.e myfunc 5
= 1
root2 = 1.1414216
Now, n could be anything up 1000+ and so i need some special method for
calculating root 2 (as i need to capture to a higher precision than a
typical FLoat or Double would allow), i have been given the following code
todo with as i please, im sure i have to add some more to it then call it
from my own function 'myfunc' for extra processing,
squareRoot :: Float-> Float
squareRoot x = until p f 1.0
where
eps = 1.0e-6
p y = abs(x - y^2) < eps * x
f y = (y + x/y) / 2
From what I can see, i need to use the 'Integer' data type as this can store
values of unlimited length, however it cannot store decimal value and so I
have to 'undecimal' my data.
My idea was to calculate root2 and then multiply it by 10^n. The lhs of the
decimal point can then be placed into an integer field and the final digit
of the stored number is the nth value im looking for. Im totally lost as to
how todo this. Ahhhh ... functional programming hurts my head :)
Please help.
Thank you.
Taz
Glynn Clements
"Taz" <ad...@e-tones.co.uk> writes:
> Hi all, i've been set a task below and got stuck on a few parts, any help
> would be great!
>
> My Task: define a function that takes an int parameter (n) and returns the
> nth decimal point of root2
>
> i.e myfunc 5
> = 1
>
> root2 = 1.1414216
>
> Now, n could be anything up 1000+ and so i need some special method for
> calculating root 2 (as i need to capture to a higher precision than a
> typical FLoat or Double would allow), i have been given the following code
> todo with as i please, im sure i have to add some more to it then call it
> from my own function 'myfunc' for extra processing,
>
> squareRoot :: Float-> Float
> squareRoot x = until p f 1.0
> where
> eps = 1.0e-6
> p y = abs(x - y^2) < eps * x
> f y = (y + x/y) / 2
OK; this is the "successive approximation" method which I learned at
school. It isn't the way that one would normally calculate square
roots for practical purposes, but it will produce the correct answer
eventually.
> From what I can see, i need to use the 'Integer' data type as this can store
> values of unlimited length, however it cannot store decimal value and so I
> have to 'undecimal' my data.
>
> My idea was to calculate root2 and then multiply it by 10^n. The lhs of the
> decimal point can then be placed into an integer field and the final digit
> of the stored number is the nth value im looking for. Im totally lost as to
> how todo this. Ahhhh ... functional programming hurts my head :)
If you want the nth decimal place of sqrt(2), the simplest solution
would probably be to bear in mind that:
sqrt(2 * 10^(2n))
= sqrt(2) * sqrt(10^(2n))
= sqrt(2) * 10^n
and compute the units digit of sqrt(2 * 10^(2n)), i.e. pre-multiply 2
by a sufficiently large power of n that you only need the integer part
of the square root.
However, this might give an off-by-one answer due to rounding error;
in that case, multiply by 10^(2n+2) and use the tens digit instead of
the units.
Aside: a more realistic method for calculating square roots (and one
particularly suited to binary numbers) is to use bisection. E.g.:
intSqrt' :: Int -> (Int, Int) -> (Int, Int)
intSqrt' x (lo, hi) =
let mid = (lo + hi) `div` 2
in if (x < mid*mid)
then (lo, mid)
else (mid, hi)
intSqrt :: Int -> Int
intSqrt x = fst $ head $ dropWhile tooVague $ iterate (intSqrt' x) bounds
where bounds = (0, 65536)
tooVague (lo, hi) = hi - lo > 1
If you look at the intermediate list returned by the call to iterate
you will note that each iteration adds a decreasing power of two to
either the lower or upper bound; i.e. each iteration computes exactly
one bit. Furthermore, you can compute mid^2 inductively; the net
result is that bisection is a lot less expensive than successive
approximation.
--
Glynn Clements <glynn.c...@virgin.net>
Dirk Thierbach
> Hi all, i've been set a task below and got stuck on a few parts, any help
> would be great!
I don't think it's a good idea to ask for homework help for *all* of your
tasks here, but
> My Task: define a function that takes an int parameter (n) and
> returns the nth decimal point of root2 [with a given Newton iteration
> function squareRoot :: Float-> Float]
> From what I can see, i need to use the 'Integer' data type as this can store
> values of unlimited length, however it cannot store decimal value and so I
> have to 'undecimal' my data.
I have the impression that the task wasn't meant to take into account
that Float has limited precision, so your initial idea is a lot
better.
However, the given algorithm does not handle decimal digits well,
so it's probably easier to replace it with an algorithm that calculates
the next digit directly. The Newton iteration will converge faster, but
as it is homework, we don't care for speed :-) Correctness and a systematic
development of ideas is more important.
> My idea was to calculate root2 and then multiply it by 10^n.
Let's look at the step to calculate the next digit directly. Assume
you already have some integer approximation x and you know that x^2 <= y,
but (x+1)^2 > y. For example, you have calculated 2 digits and you
know that 141^2 <= 2000 (since 1.41^2 <= 2.0) and 142^2 > 2000 (since
1.42^2 > 2.0). For the next digit, you have to multply x by 10. Since
x is squared in the inequality, you have to multiply y by 100, however.
So we get x' = 1410 and y' = 200000, which is correct as 1410^2 <= 200000.
Now you only have to test the digits 9,8,7,... in order, e.g. (1410+9)^2,
(1410+8)^2, ... until you find the first one with a result that is below y'.
So let's write the program bottom up:
* Give the list of numbers 9,8,7, ... a name. ([9..0] doesn't work. Why?)
* Write an auxiliary function that finds the first digit d between 9 and 0
such that (x'+d)^2 <= y'. (Haskell is nice, so you can write this
as a one liner that reads exactly as the description does, and lazy
evaluation will make it efficient).
* Write an auxiliary function for one step of the calculation, finding
the next digit. What parameters do you need?
* Write the main function that calls the auxiliary function with the
correct initial arguments. How do you make sure you get the last
digit as result? Maybe you have to change the auxiliary function
a bit?
* Sanity check: Look at the border cases. (This should become a reflex
when writing programs). What value should your function return for
the "0-th" digit, what values (or errors?) for negative digits?
Where do you have to put the changes to make sure everything works
correctly?
* If you want, you can try to make the algorithm more efficient by
trying to avoid really large numbers where possible, but that's a
bonus question :-)
HTH,
- Dirk
Dylan Thurston
> "Taz" <ad...@e-tones.co.uk> writes:
>> squareRoot :: Float-> Float
>> squareRoot x = until p f 1.0
>> where
>> eps = 1.0e-6
>> p y = abs(x - y^2) < eps * x
>> f y = (y + x/y) / 2
>
> OK; this is the "successive approximation" method which I learned at
> school. It isn't the way that one would normally calculate square
> roots for practical purposes, but it will produce the correct answer
> eventually.
> Aside: a more realistic method for calculating square roots (and one
> particularly suited to binary numbers) is to use bisection. E.g.:
This is very wrong. The method Taz posted, Newton's method,
approximately *doubles* the number of digits of accuracy with each
iteration, while bisection merely adds one bit with each iteration.
Try it!
Peace,
Dylan