Skip to main content
MathOverflow

Return to Answer

edited body
Source Link
Qiaochu Yuan
Qiaochu Yuan
  • 118.2k
  • 40
  • 447
  • 741

I guess it's worth saying this in an answer: I don't think this is a meaningful question. Consider the function defined recursively by $f(1) = 1, f(n+1) = 2 f(n)$$f(0) = 1, f(n+1) = 2 f(n)$. Clearly $f(n) = 2^n$ for all $n$. You shouldn't consider this formula an "escape" from the recursive definition, for the very simple reason that the exponential function is usually defined by this very recursion! (One can, of course, do something incredibly silly like define $2^n$ to be $e^{n \ln 2}$. Whether you think this constitutes an "escape" from the recursive definition is up to you, but what it doesn't constitute is a fast method to compute powers of two.)

What you can ask for, instead, is an algorithm faster than the naive one above. There is, in fact, such an algorithm; it goes by the name binary exponentiation or exponentiation by squaring, and it basically works by replacing the recursion $f(n+1) = 2f(n)$ by a pair of recursions $$f(2n) = f(n)^2, f(2n+1) = 2f(n)^2.$$

Does this constitute an "escape" from the recursive definition? I don't know; it still requires that you compute some smaller powers of two, just not as many.

I guess it's worth saying this in an answer: I don't think this is a meaningful question. Consider the function defined recursively by $f(1) = 1, f(n+1) = 2 f(n)$. Clearly $f(n) = 2^n$ for all $n$. You shouldn't consider this formula an "escape" from the recursive definition, for the very simple reason that the exponential function is usually defined by this very recursion! (One can, of course, do something incredibly silly like define $2^n$ to be $e^{n \ln 2}$. Whether you think this constitutes an "escape" from the recursive definition is up to you, but what it doesn't constitute is a fast method to compute powers of two.)

What you can ask for, instead, is an algorithm faster than the naive one above. There is, in fact, such an algorithm; it goes by the name binary exponentiation or exponentiation by squaring, and it basically works by replacing the recursion $f(n+1) = 2f(n)$ by a pair of recursions $$f(2n) = f(n)^2, f(2n+1) = 2f(n)^2.$$

Does this constitute an "escape" from the recursive definition? I don't know; it still requires that you compute some smaller powers of two, just not as many.

I guess it's worth saying this in an answer: I don't think this is a meaningful question. Consider the function defined recursively by $f(0) = 1, f(n+1) = 2 f(n)$. Clearly $f(n) = 2^n$ for all $n$. You shouldn't consider this formula an "escape" from the recursive definition, for the very simple reason that the exponential function is usually defined by this very recursion! (One can, of course, do something incredibly silly like define $2^n$ to be $e^{n \ln 2}$. Whether you think this constitutes an "escape" from the recursive definition is up to you, but what it doesn't constitute is a fast method to compute powers of two.)

What you can ask for, instead, is an algorithm faster than the naive one above. There is, in fact, such an algorithm; it goes by the name binary exponentiation or exponentiation by squaring, and it basically works by replacing the recursion $f(n+1) = 2f(n)$ by a pair of recursions $$f(2n) = f(n)^2, f(2n+1) = 2f(n)^2.$$

Does this constitute an "escape" from the recursive definition? I don't know; it still requires that you compute some smaller powers of two, just not as many.

Source Link
Qiaochu Yuan
Qiaochu Yuan
  • 118.2k
  • 40
  • 447
  • 741

I guess it's worth saying this in an answer: I don't think this is a meaningful question. Consider the function defined recursively by $f(1) = 1, f(n+1) = 2 f(n)$. Clearly $f(n) = 2^n$ for all $n$. You shouldn't consider this formula an "escape" from the recursive definition, for the very simple reason that the exponential function is usually defined by this very recursion! (One can, of course, do something incredibly silly like define $2^n$ to be $e^{n \ln 2}$. Whether you think this constitutes an "escape" from the recursive definition is up to you, but what it doesn't constitute is a fast method to compute powers of two.)

What you can ask for, instead, is an algorithm faster than the naive one above. There is, in fact, such an algorithm; it goes by the name binary exponentiation or exponentiation by squaring, and it basically works by replacing the recursion $f(n+1) = 2f(n)$ by a pair of recursions $$f(2n) = f(n)^2, f(2n+1) = 2f(n)^2.$$

Does this constitute an "escape" from the recursive definition? I don't know; it still requires that you compute some smaller powers of two, just not as many.