There's something very strange about this algorithm, in some places on the web they say that it can only generate 2^n terrains and in other places like http://www.lighthouse3d.com/opengl/terrain/index.php?mpd they say that it can only generate 2^n+1 terrains. The last one seems the most reasonable because we always need a middle point for the diamond step. But in game programming gems I Shankel makes a different implementation. Can anyone clarify this I’m truly confused...

You start with a 2x2 square, but then introduce one point in the middle of each edge and the middle of the patch. Now you have 3x3 and from now on you always introduce an even amount of points in each dimention, so you end up with an array n^2+1 points in each dimention, defining 2^n segments.

I'm not sure i'm understanding it cleary, for example in the jmonkey engine implementation of this algorithm (a copy of Shankel implementation) for a 128x128 we end up with a 128x128 heightmap not with a 129x129 heightmap...

Line 90
http://www.koders.com/java/fid5BED0172F4AAAE5A11BCA2BED2805CBD661C6CEE.aspx?s=MidPointHeightMap

and from line 90 to 189 of
http://www.koders.com/java/fid834444E124C3062EAC915A7CFDB5B4052378C46D.aspx?s=MidPointHeightMap