I'm trying to solve what seems to be a simple math problem. I can write the problem as a for loop, but I'm not sure how to translate it into an equation. Can anyone help?
x = 10;
for(int i=0; i<3000; i++)
{
x = x^2
}
views:
265answers:
6Or in this case, 10^(2^3000)
David Zaslavsky
2009-08-19 02:15:29
All the x^6000 answers are wrong. It's true that (x^2)^3000 == x^6000. However, that is not what the loop is saying. I'm surprised (and rather disappointed) that you are in the minority in reading it correctly.
John Y
2009-08-19 02:34:42
A:
Given it's a constant, how about just
x = 10000000... (etc.)
But I suspect you want something a bit more intensional:
x = 10^6000
Or even more:
x = (10^2)^3000
Or (if you allow slightly looser notation):
x = (10^2) ... ^2
with a horizontal "} 3000" under the "...".
Edmund
2009-08-19 02:16:00
A:
Something (original value of 10 in your case) will be squared 3000 times.
DmitryK
2009-08-19 02:17:37
+4
A:
You provided code, and are asking us to provide the mathematical equivalent -- so I'm going to take your code literally, and assume it's a C-like language.
In that environment, ^ is the bitwise XOR operator. So after the loop x = 10, since it was XOR-ed with a constant 2 (toggling the next-to-LSB bit) an even number of times.
Or was this merely pseudocode -- did you really mean exponentiation?
Jim Lewis
2009-08-19 02:25:03
I think you deserve a certain amount of props for mentioning that ^ is not exponentiation in C. I think most C coders wouldn't have had to compile it to figure that out though. ;) Also, I will state for the record that you did answer before the OP clarified that he was using pseudocode. I will also state for the record that using C's for loop and braces is not the best choice for PSEUDOcode, which makes your confusion all the more understandable.
John Y
2009-08-19 02:43:36
+2
A:
The mathematical name for the class of problem you have given is recurrence relation. A recurrence relation defines a sequence An in terms of the preceding terms An-1, An-2, etc. In your case,
An = An-12
As other answers have shown, creating a closed-form solution for your given example is straightforward. Solving a recurrence relation can quickly become much more difficult with seemingly simple changes to the relation:
An = An-12 + c
Such a nonlinear recurrence relation may not even have a closed-form solution, depending on the value of c. (Incidentally, when used with complex numbers the above recurrence relation is at the heart of the Mandelbrot set.)
Greg Hewgill
2009-08-19 13:00:59