<Xgoff> lifning where is the next logic question, <Xgoff> for me to fail

write a procedure to calculate the sum of squares from 0 to n^2 (i.e. 0^2 + 1^2 + 2^2 + 3^2 + ... + (n-1)^2 + n^2)
without using multiplication
in O(n) time.

weirdest filter ever

you light the match first

hint: all you need is a way to calculate (n+1)^2 in terms of n^2 and n

also it can be in any programming language you think is capable.

This post has been edited by Lightning on Sep 19 2009, 06:52 PM

i think this excludes zzt-oop

so i'm assuming 'no multiplication' also means 'no exponentiation'

This post has been edited by Xgoff on Sep 19 2009, 06:55 PM

more specific: the only binary operators you are allowed to use are addition and subtraction.

the python implementation I came up with is pretty straightforward.


This post has been edited by Lightning on Sep 19 2009, 06:56 PM

i think i know the trick it's just aaaa i need to figure the rest out

you should only need three variables to do it. one of them is a loop counter and another is the return value

then what the hell am i doing using two variables

f(n) = n^2 + f(n - 1)
n^2 = (n-1)^2 + 2n - 1

int f (n) {
sq = 0;
ret = 1;
for (i = 0; i < n; i++) {
sq += (i + i - 1)
ret += sq;
}
return ret;
}

This post has been edited by Retriever II on Sep 19 2009, 07:20 PM

function pows (to)
local c = 0
for i = 0, to do
c = c + i^2
end
return c
end

function ssq (to)
local c, d = 0, 0
for i = 0, to + to - 1 do
c = c + i + i
end
return c
end

go = 10

print(ssq(go), pows(go) == ssq(go))
print()

-- 0 1 2 3 4 5 6 7 8 9 10
-- 0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100
-- 1 3 5 7 9 11 13 15 17 19

i was 5 off jesus

close, your math is slightly wrong. that minus should be a plus.
(also I think ret should start at 0)

This post has been edited by Lightning on Sep 19 2009, 07:24 PM

No, the minus should definitely be a minus (what should be changed is the < should be <=, which I didn't notice initially because so used to array looping). You're correct, ret's start value should be 0.

I originally wrote out a much longer recursive solution that should have been valid.

worked fine when i changed it to a plus

Your right it should be plus in this case. Another off by one error!

those are fun

anyway here's the python solution:

the logic behind it:
the sum of the first n+1 squares is (n+1)^2 + the sum of the first n squares.
the sum of the first 0 squares is 0. (alternatively, the sum of the first 1 squares is 1).

we can loop from 0 to n and calculate all the squares along the way, as long as we keep track of the previous x^2 and x, because we can use them to calculate the next square ((x+1)^2) using addition as follows:

(x+1)^2
= x^2 + 2x + 1
= x^2 + (x+x) + 1.

if we know x^2 and x from the previous loop iteration, this works.

Whenever I see these topics I just kinda smile and nod, and hope these guys don't make the next weapon of mass destruction

I recently turned down working on an unmanned underwater vehicle project for the department of defense
for, let's say, ethical reasons. (to be honest they couldn't tell me much about the project without me signing myself onto the team, so yeah--no.)