How do you calculate %xHKO?

Mm, interesting. I never thought of the binary approach.

Edit: But it actually doesn't save time if you want to calculate each p_n anyway. Hm...

Code:

function convolute(a, b)
  local p = {
    min = a.min + b.min,
    max = a.max + b.max,
  }
  for n = p.min, p.max do
    local sum = 0
    for k = math.max(a.min, n-b.max), math.min(a.max, n-b.min) do
      sum = sum + a[k]*b[n-k]
    end
    p[n] = sum
  end
  return p
end

 Time complexity

The convolution step as I've written it here has time complexity O(r1*r2) where r1 is the range of the larger interval and r2 is the range of the smaller interval. I tried to explain why without using example numbers, but it was too hard.

Assume interval 1 is [200, 700] and interval 2 is [100, 300]
n=300 to n=500 -> inner loop iterates n-300 times (average 100) -> r2*r2/2
n=500 to n=800 -> inner loop iterates 200 times -> (r1-r2)*r2
n=800 to n=1000 -> inner loop iterates 1000-n times (average 100) -> r2*r2/2
total -> (r1-r2+r2)*r2 -> r1*r2

If you loop a single interval with range r and convolute cumulatively k times:

r1	r2	r1*r2
r	r	r^2
2r	r	2r^2
3r	r	3r^2
4r	r	4r^2
kr	r	kr^2
sum	sum	k(k+1)/2 * r^2

And so the total time complexity is on the order of k^2*r^2. Since k = hp/min and r = max-min, this is also hp^2*(max/min-1)^2.

Quadratic time in HP? Yikes.

Of course, one optimization would be to binary convolute until you actually need the numbers. In that case you'd have something like

r1	r2	r1*r2
r	r	r^2
2r	2r	4r^2
4r	4r	16r^2
8r	8r	64r^2
kr	kr	k^2*r^2
sum	sum	(4k^2-1)/(4-1)*r^2

Which is still somehow quadratic.

I tested this on my system and it took about 6.2 seconds to compute hits(1000, 2000, 10000). Quadratic in HP means it takes ten minutes to work with 100000 HP.