Author |
Topic: Mysterious Function (Read 1336 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Mysterious Function
« on: Feb 27th, 2004, 7:45am » |
 Quote  Modify
|
What does the following function do?
Code:M(a, b)
{
eps = 0.00001;
p = max(a, b);
q = min(a, b);
while (q > eps) {
r = (q*q)/(p*p);
s = r/(r+4);
p = (2*s + 1)*p;
q = s*q;
}
return p;
}
|
|
Note: you need to prove your answer - simulation is not enough!
|
| « Last Edit: Feb 28th, 2004, 2:48am by Barukh » |
 IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Mysterious Function
« Reply #1 on: Feb 27th, 2004, 9:49am » |
Quote Modify
|
M(1,1) looks suspiciously familiar, so compute a table of M(a,b)2. Then it's clear that M(a,b)2 = a2 + b2.
::Initially, {p,q} = {a,b}, and in the limit as eps goes to 0, the loop terminates at {p,q} = {0, sqrt(a2+b2)}, so it's reasonable to suggest that at all points, p2+q2 = a2+b2 = C. Let's prove this. After one iteration, p,q take on the new values:
p' := p(3q2+4p2)/(q2+4p2) > p,
q' := q3/(q2+4p2) < q,
and doing the algebra, p'2 + q'2 = p2 + q2, so this quantity never changes, and is always C.
Therefore, when the loop terminates and q < eps, we must have p > sqrt(C-eps).
To see that the loop does terminate, we may write
q' = f(q) = q3/(4C - 3q2), and since q is strictly decreasing and bounded below by 0, it must converge to some limit less than q0 = min(a,b). But the only fixed points of f(q) are q=0 and q = sqrt(C) >= max(a,b). Therefore q converges to 0, and p converges to sqrt(C).
|
|
IP Logged |
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
    
 
Gender:
Posts: 767
|
|
Re: Mysterious Function
« Reply #2 on: Feb 27th, 2004, 8:40pm » |
Quote Modify
|
What is "eps"?
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Mysterious Function
« Reply #3 on: Feb 28th, 2004, 2:50am » |
Quote Modify
|
on Feb 27th, 2004, 8:40pm, John_Gaughan wrote:
It's a very small number. I modified the code to reflect this.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print