Thread: "ODD" Square root Algorithm View Single Post
 2008-03-15, 07:35 #4 nibble4bits     Nov 2005 2×7×13 Posts Do I understand right? That this is based on this formula for quadratics: (n+1)^2=n^2+2n+1; let m=n+1 m^2-n^2-1=2n Thus consecutive squares are always 2n+1 appart. That formule you mentioned is equivilent to this code: Code: Let x = 0 For i = 1 to n x = x + i + i - 1 Next i REM Returns in x, the square of n using recursive addition instead of multiplication. The optimizes trivially without multiplication to: Code: Let x=0 For i = 1 to n x = x + i + i Next i x = x - n You can further remove the For...Next loop using an identity but you get this: Let x = 2 * n * (n + 1) / 2 - n Or: Code: Let x = n * (n + 1) - n Or: Code: Let x = n^2 + n - n As you can see, this leads you back to your original equation of x=n^2. EDIT: You should note that for m=n+1: m^3 - n^3 - 1 = (n+1)^3 - n^3 - 1 = n^3 + 3n^2 + 3n + 1 - n^3 - 1 = 3(n^2 + n) = 3n(n+1) Last fiddled with by nibble4bits on 2008-03-15 at 07:44 Reason: Added note