3 ms·

Love the complexity gotcha in the power example: function p(x:real; n:integer):real; begin if n = 0 then p := 1 else if odd(n) then p :

Love the complexity gotcha in the power example: function p(x:real; n:integer):real; begin if n = 0 then p := 1 else if odd(n) then p := p( x, n div 2 ) * p( x, n div 2 ) * x else p := p( x, n div 2 ) * p( x, n div 2 ) end Can you see why this is O(n) and not O(lg n)? I've seen that (or its equivalent) in so many people's code. This is the one place where "pure" functional languages have such potential. If the function is guaranteed side-effect free then the calls can be memo-ised, and this routine becomes O(lg n) "for free".

3pt14159 16y ago
Is it that p is double called the majority of the calculations, thereby making the function call itself twice when a simple "save" of the result would have stopped a geometrically growing tree? I've never studied this, just curious.
- RiderOfGiraffes 16y ago
  Yes. Consider calling p with n=1. Then it takes one call. Now call it with n=2. It gets called twice with n=1, and you need to do the multiply. Thus T(2)=2 calls + 1 multiply. Now call it with n=4. Time taken is 2T(2) plus a multiply. Hence T(4)=2(2c+m)+m=4c+3m. Inductively we can prove that T(n)=n * c + m, where c is the time of a call, and m is the time of a multiply, and I'm ignoring small details. If you save the result of a call and reuse it then you get a different result, of course, and if you really want to learn how this works then you should try to figure it out.
  - gabaix 16y ago
    So what would be the operation to keep O(log n)? save p(x, n div 2) in memory?
deleted 16y ago
[deleted]
TimJYoung 16y ago
One option would be to have the language (in this case Pascal) support a hint keyword that indicates that p is side-effect-free and doesn't modify any global data, or any data outside of its local scope. Then the compiler can use a simple common subexpression elimination optimization. The SQL 2003 standard does this with functions in order to aid the implementor's compiler/optimizer ability to optimize functions that don't modify or read any data and are purely functional.

3pt14159 16y ago

Is it that p is double called the majority of the calculations, thereby making the function call itself twice when a simple "save" of the result would have stopped a geometrically growing tree? I've never studied this, just curious.

RiderOfGiraffes 16y ago
Yes. Consider calling p with n=1. Then it takes one call. Now call it with n=2. It gets called twice with n=1, and you need to do the multiply. Thus T(2)=2 calls + 1 multiply. Now call it with n=4. Time taken is 2T(2) plus a multiply. Hence T(4)=2(2c+m)+m=4c+3m. Inductively we can prove that T(n)=n * c + m, where c is the time of a call, and m is the time of a multiply, and I'm ignoring small details. If you save the result of a call and reuse it then you get a different result, of course, and if you really want to learn how this works then you should try to figure it out.
- gabaix 16y ago
  So what would be the operation to keep O(log n)? save p(x, n div 2) in memory?

deleted 16y ago

[deleted]

TimJYoung 16y ago

One option would be to have the language (in this case Pascal) support a hint keyword that indicates that p is side-effect-free and doesn't modify any global data, or any data outside of its local scope. Then the compiler can use a simple common subexpression elimination optimization. The SQL 2003 standard does this with functions in order to aid the implementor's compiler/optimizer ability to optimize functions that don't modify or read any data and are purely functional.