Dev Diary #7: How game engine math got 3-4x faster
In short: We measured the number math of MKA Engine (division, square root, exponent, logarithm and power) on one bench and made it faster. Each of those operations got 3 to 4 times faster, and a game day late in the game got about 23 to 30 percent shorter. The results of division and square root stayed bit for bit the same; the results of exponent, logarithm and power changed slightly and came out more accurate than before.
In a strategy game, every day the tax, the population growth and the prices of thousands of provinces are computed. In the end all of it comes down to a few simple operations: adding, multiplying, dividing, taking a square root. So that the engine gives the same result on every computer, we use the fixed-point numbers we described in Diary #1. There we also gave a measurement: division and square root were much more expensive than with ordinary decimal numbers. In this diary we describe how we made those expensive operations cheap.
A ready table or by hand?
Think of two clerks in the treasury. One writes every tax calculation by hand on a long scroll. The other looks at a big table where the usual answers are ready, and makes the approximate answer exact with a small correction. Both reach the same right answer; the second is much quicker. This diary is the story of turning the engine's math from the first clerk into the second.
Why did we start?
First we had to know where to look. We profiled the late-game world with the headless runner: which functions eat the processor's time? The result was clear: 128-bit division took about 11 percent of the processor time. With this number we set our targets:
| Operation | Target | Why this target |
|---|---|---|
| Division | at most 6 ns | About 11 percent of the processor time in the day profile went to division; less than half of the measured 13 ns |
| Exponent | at most 45 ns | About a third of the measured 128 ns |
| Square root | at most 10 ns | Half of the measured 20 ns |
| Logarithm and power | at least 2 times faster | The starting times were very high (about 90 and 208 ns) |
| Share of division in the day | at most 4 percent | Less than half of the 7.6 percent in the profile |
These targets came from estimates, they are not rules. You will see below which ones held. We kept the measurement simple: headless runner, a million random numbers, the best of five runs for each operation.
What changed?
Multiplication. While rounding the result to the nearest number we branched on the sign. When the processor guesses a branch wrong, it loses time. We wrote the rounding without a branch.
Division. Division used to be done with two separate divisions (one for the quotient and one for the remainder). Now it does a single division and gets the remainder from the quotient. If the numbers are small enough, which they are for the typical numbers of a game, we use the processor's fast 64-bit division. If the numbers are very large the old 128-bit path stays.
Square root. The ready-table comparison is clearest here. A table of 769 points holds an approximate square root at each point. We find the point nearest the given number and take a single correction step. The method is called Newton's method; it improves an approximate answer at every step. The result is bit for bit the same as the library's own exact square root. The table is only 6 kilobytes.
Exponent and logarithm. Both come down to computing a polynomial; we wrote the polynomial as a sequence of multiplications and additions (Horner's method). The logarithm also has a table of 128 entries, and no division at all. We do not write the tables by hand: a script produces them with 80-digit precision and a separate check tests that the tables are up to date with the script.
Sharing out. When a treasury is shared among countries, fractional remainders appear; the remainders are handed out starting from the largest. Here the work was to turn many divisions into a multiplication with a single inverse number, and to pick the largest remainders instead of sorting them. The order of distribution and the result are the same as before.
Mod formulas. The formulas of mods run as WebAssembly, and there division used a 64-step loop. When the number is small enough we cut it down to a single division.
Results
Speed-up per operation (typical operands) (x)
| Label | Speed-up |
|---|---|
| Multiplication | 3.0 |
| Division | 3.6 |
| Square root | 4.1 |
| Exponent | 3.5 |
| Logarithm | 4.1 |
| Power | 3.5 |
| Operation | Before | After | Target | Result |
|---|---|---|---|---|
| Multiplication | 5.90 | 1.94 | — | — |
| Division | 13.49 | 3.76 | at most 6 | Met |
| Square root (0–65,536) | 20.48 | 4.95 | at most 10 | Met |
| Square root (0–1 million) | 21.90 | 8.49 | at most 10 | Met |
| Exponent | 127.11 | 36.67 | at most 45 | Met |
| Logarithm | 89.62 | 21.86 | at least 2x | Met (4.1x) |
| Power | 207.23 | 59.75 | at least 2x | Met (3.5x) |
This table uses "typical" operands: numbers with values roughly between 2⁻¹⁶ and 2²⁰, like prices, rates and populations. With very large numbers (the worst case) the gain is smaller: division goes from 13.25 ns to 7.25 ns, which is 1.8 times.
Ratios measured in the same run are more reliable; the machine was busy with other work during the measurement. That is why we do not compare directly with the numbers in #1. There the operand range and the machine load were different. The "before" values in this diary were measured again on the same bench.
- 7.6% → 0.24% share of 128-bit division in the length of a day
- 23–30% how much a game day late in the game got shorter (8 threads)
- 13.5 → 3.8 ns one division with typical operands
We measured the length of a day late in the game, over 300 days, on eight threads, in five runs one after another:
| Run | Before | After |
|---|---|---|
| 1 | 2.21 | 1.74 |
| 2 | 2.15 | 1.60 |
| 3 | 2.88 | 1.93 |
| 4 | 2.76 | 2.16 |
| 5 | 2.85 | 2.12 |
In every run the day got shorter, by about 23 to 30 percent. Most important: because division, square root and sharing out came out bit for bit the same, the fingerprint of the game is the same before and after. So we play the same game, faster.
Where in a game day does this speed-up help? Mostly inside the systems: tax, population and price calculations. We did not change the order of the day, we only made each step cheaper.
In mod formulas
The speed of division in the formulas of mods also went up. The path that comes down to a single division for small numbers was measured on two separate backends:
| Backend | Before | After | Gain |
|---|---|---|---|
| Native code (Cranelift) | 303 | 133 | 2.3x |
| Interpreter (Pulley) | 1,852 | 504 | 3.7x |
As a control, multiplication measured in the same run did not change. The results of the three routes, the native code, the interpreter and the engine's own number type, are bit for bit the same.
Limits
- Decimal numbers are still faster: With typical operands multiplication is about 2.4 times slower than decimal, division 3.2 times, square root 2.4 to 4.2 times; exponent 9.3, logarithm 5.8, power 5.4 times. In return we have the same result on every machine.
- Less gain with large numbers: With very large operands division got 1.8 times faster, and the combined multiply-then-divide (
mul_div) only 1.3 to 1.4 times. - The bits of exponent, logarithm and power changed: If a game made with the old version uses these functions, replaying its save and command log shows divergence in the low bits. There is no distributed save at the moment and no save sample in the repository depends on these functions; that is why we did not raise the save version. If a game that uses these functions appears outside, its saves must be produced again with the new version.
- Accuracy went up: In units of the smallest step of a number (1/16,777,216), the largest error went from 9.5 to 4.1 for exponent and from 35.5 to 6.4 for power; logarithm stayed at 0.5.
- Measurement: Simple, headless, on a shared and loaded machine. Not the absolute times but the ratios in the same run are meaningful. On a single thread the length of a day fluctuated because of the load, and the improvement is too uncertain to state.
- Not a real game: The scale world is a test world. The mix of numbers in a real game may differ.
Frequently asked questions
Why is math sped up in a game engine?
Grand strategy games repeat the same operations for thousands of locations every day. When costly operations such as division and square root are called very often they eat a large part of the game day. In MKA Engine 128-bit division took about 11 percent of the processor time in the profile.
If the square root is taken from a table, is the result approximate?
No. The table gives only the starting estimate; then one correction step makes the result exact. The result is bit for bit the same as the library's own exact square root.
Does the speed-up change the result of the game?
Not for division, square root and sharing out; in the scale world the fingerprint of the game is the same before and after. The last bits of exponent, logarithm and power changed, but the results are more accurate than before.
If decimal numbers are faster, why use fixed-point numbers?
Decimal numbers do not guarantee the same result on every processor. In a multiplayer game everybody must see the same result; so we use fixed-point numbers and try to close the speed gap as in this diary.
Sources and records
External sources:
- Wikipedia, Fixed-point arithmetic (opens in a new tab)
- Wikipedia, Newton's method (opens in a new tab)
- Wikipedia, Horner's method (opens in a new tab)
- Wikipedia, Lookup table (opens in a new tab)
Our internal records (the engine repository is closed, so we cannot link them):
- Number model decision: fixed-point number, rounding to nearest, panic on overflow.
- Speed target decision: daily targets in the scale world.
- Number math measurement: 16 October 2026; before and after on the same bench, one after another; profile of the day and length of the day measured separately.
More on this will come
MKA Engine is still in development. We will keep sharing our number math and speed work in new diaries; this one is the first of them.
If you have questions or ideas about this diary, write to us from the contact page. For an overview of the engine see the MKA Engine page, and for all diaries the Developer Diaries list.