[alexti]

Here's my original code:

code:

---

namespace math {

	inline double sum1toInfOf_q_power_n(double q)

	{

		double c = 1/(1-q);

		return c;

	}



	inline double sum1toInfOf_nq_power_n(double q)

	{

		double c = q/(1-q);

		return c/(1-q);

	}



	inline double sum1toInfOf_nnq_power_n(double q)

	{

		return q*(1+q)/pow(1-q,3);

	}

}





namespace illwinter_dice {

namespace probability {



	//	probability that roll of pair of dices is equal <n>

	inline double d2rollIsN(long n)

	{

		long u = (n-1)/5;

		long v = n - 5*u;

		return pow(q,u+1)*((v-1)*(u+1)*q + (6-v)*u);

	}



	//	probability that roll of 1 pair of dices is greater than the roll

	//	of another pair of dices at least by <n>

	double d2rollIsGreaterThanD2Roll2byAtLeastN(long n)

	{

		long u = (n-1)/5;

		long v = n - 5*u;

		double qu2 = pow(q,u+2);

		static double c0q2 = math::sum1toInfOf_q_power_n(q*q);

		static double c1q2 = math::sum1toInfOf_nq_power_n(q*q);

		static double c2q2 = math::sum1toInfOf_nnq_power_n(q*q);

		double total = 0;

		for (long s = 1; s <= 5; s++)

		{

			//	uu and vv are such that 5uu+vv = 5u+s+v, and 0<=uu and 1<=vv<=5

			double uu = u, vv = s+v;

			if (s+v > 5)

			{

				uu++;

				vv -= 5;

			}

			

			//	Calculate coefficients 

			double a1, a2, b1, b2;

			a1 = 6.0 - s*(1-q) - q;

			a2 = q*(s-1);

			

			b1 = 20.0 - 5.0*(vv-1)*(14-vv)/12.0;

			b2 = b1*uu + 6.0 - (vv-1)*(vv-2)/12.0;

			

			double x = qu2*(c2q2*a1*b1 + c1q2*(a1*b2+a2*b1) + c0q2*a2*b2);

			if (s+v > 5)

				x = x*q;

			total += x;

		}

		return total;

	}



}}

---

If you're figting for performance, you can use the following code

code:

---

template <int ROLL2_CACHE_LIMIT, int ROLL2_COMPARE_CACHE_LIMIT>

class CachedDiceProbability {

public:

	CachedDiceProbability() { init(); }



	inline double d2rollIsN(long n) const

	{

		assert(n>=0);

		if (n > ROLL2_CACHE_LIMIT)

			return illwinter_dice:obability::d2rollIsN(n);

		return Cache.d2roll[n];

	}

	inline double d2rollIsGreaterThanD2Roll2byAtLeastN(long n) const

	{

		assert(n>=0);

		if (n > ROLL2_COMPARE_CACHE_LIMIT)

			return illwinter_dice:obability::d2rollIsGreaterThanD2  Roll2byAtLeastN(n);

		return Cache.d2rollIsGreaterThanD2Roll2[n];

	}



protected:

	struct {

		double d2roll[ROLL2_CACHE_LIMIT+1];

		double d2rollIsGreaterThanD2Roll2[ROLL2_COMPARE_CACHE_LIMIT+1];

	} Cache;



	void init()

	{

		long i;

		Cache.d2roll[0] = 0;

		for (i = 1; i <= ROLL2_CACHE_LIMIT; i++)

			Cache.d2roll[i] = illwinter_dice:obability::d2rollIsN(i);

		for (i = 0; i <= ROLL2_COMPARE_CACHE_LIMIT; i++)

			Cache.d2rollIsGreaterThanD2Roll2[i] 

				= illwinter_dice:obability::d2rollIsGreaterThanD2  Roll2byAtLeastN(i);

	}

};

---

With 50,50 parameters this Cache will cover about 99.9999% of cases and revert to the actual calculations if you need to calculate for the roll (or difference) greater than 50. And it won't take much space either, only 800 bytes.

The root of performance issue is in simulation nature, meaning that you recalculate the same combat thousands of times to get ides of probabilities of outcome. To accelerate things it would be necessary to replace iterative process with analytic formulas. It's not that hard to make an analytic formula in particular cases, but there're so many different situations and analysing all of them is probably too much work.

I have few ideas to increase performance within the same framework though.

Replacing your current code with the my analytic formulas is not likely to produce much gain in general, but you could win some time on the checks (for example, to verify if you can roll required MR check you'd look into the Cached table and see that if you need to have 2 more than opponents, your probability of success is 0.376093, so you'd need to call RNG only once (for range 0..1) and compare result to 0.376093).

For quantative characteristics, like damage roll I would go with caching too (the same idea you suggested). I'm not sure why you're concerned about 100K Cache, is it something Java specific?
In C it would be just direct memory addressing which provides optimal performance and 100K isn't too much to worry about.

I have no idea how fast RNG in Java is, but there're pretty good and fast RNG algorithms. For example:
ftp://random.mat.sbg.ac.at/pub/data/tt800.c
http://www.math.keio.ac.jp/~matumoto...mt19937ar.html

In general I don't know Java much, but I believe it's in general slow at number crunching because of pseudo-code (unless Java optimizer correctly guesses that it needs to compile your code into a native instructions). Otherwise, if you could split interface part from the battle engine and translate engine in C/C++ you'd probably get significant performance boost. But again it would produce extra difficulties with passing data back and forth.