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.

Sounds like too much... Also, I'm not using the binary approach, though it's probably easier to use that to find a relatively short path instead of going into a deep-broad-search.

Keep in mind that you do not need to calculate if , and max is the highest damage one could do with one attack.

My calculator does not take randomized def into account. I assume that the defense is constant.

Noah