Re: [gnugo-devel] paul_3_13.5.gz

[Arend Bayer]

Paul wrote:

> i've come up with another means of speeding up. first of all, we
> can diminish the transformation[] array significantly. since
> we always try to place pattern anchor somewhere near the center
> of a pattern, it is unlikely that offset will be something
> larger than (19/2, 19/2) or (-19/2, -19/2). that will decrease
> array size from 43k to something near 12k, which must do great
> things to caching. whether the offset fall into the range can
> be checked during pattern creation.

Maybe you can just compute it instead.

If you assume the offset is in this range, then you can reconstruct
dx and dy from offset = DELTA(dx, dy)

dy = (offset + 210 ) / 20 - 10,
dx = offset - 20 * dy

(I use 10 here instead of (MAX_BOARD + 1)/2 etc.)

Take e.g. the rotation by 90 degree. We need

rotated_offset = DELTA(-dy, dx) = -dy + 20 * dx
               = 20 * offset - 401 * ((offset + 210 ) / 20 - 10)

You can write all rotated offsets as a linear combination of
"offset" and "(offset + 10)/20". Then just make an array with these
coefficients.

Then AFFINE_TRANSFORM has to do 4 additions, 2 multiplications and one
division. Shouldn't be much worse than the old one, which had to do
5 additions and 5 multiplications. (And no, I won't start suggesting
to use 32 instead of 20 to speed up the division, although it would well
be possible...)

Arend