Non-linear Thinking with CUDA (opens in new tab)

(viralfsharp.com)

42 pointsStylifyYourBlog10y ago8 comments

8 comments

Why is the naive solution n^3? Generating one partial sum costs n, and you need to do it n times, so n^2. Even if you need to store all the intermediate sums, you get them as you sum the entire partial sum. No memoization needed. What am I missing here?

ColinWright10y ago

Naively:

   There are n starting points
   There are n ending points
   The interval is n/2 in length on average
   Thus it requires n * n * (n/2) additions

You said:

    Generating one partial sum costs n, and
    you need to do it n times, ...

I think you need to do it n^2 times.

rielfowler10y ago

There are n^2 results, right?

1 more reply

amelius10y ago

I'm wondering if this problem can be approached as a standard convolution problem.

pavanky10y ago

Especially if you are doing it in frequency space, all you would need to do is 1 forward FFT and n reverse FFTs.

Alternatively you can just perform a prefix sum operation and subtract each (n - k)th element from nth element for results in the kth iteration. This could be even faster.

j / k navigate · click thread line to collapse

8 comments

rielfowler10y ago

ColinWright10y ago

Naively:

   There are n starting points
   There are n ending points
   The interval is n/2 in length on average
   Thus it requires n * n * (n/2) additions

You said:

    Generating one partial sum costs n, and
    you need to do it n times, ...

I think you need to do it n^2 times.

rielfowler10y ago

There are n^2 results, right?

1 more reply

amelius10y ago

I'm wondering if this problem can be approached as a standard convolution problem.

pavanky10y ago

Especially if you are doing it in frequency space, all you would need to do is 1 forward FFT and n reverse FFTs.

Alternatively you can just perform a prefix sum operation and subtract each (n - k)th element from nth element for results in the kth iteration. This could be even faster.

j / k navigate · click thread line to collapse