Counting All Lattice Rectangles in the Square Grid in Near-Linear Time

We study the exact counting problem for all lattice rectangles contained in the square $[0,n)\times [0,n)$, including non-axis-parallel ones. Starting from the standard parametrization by a primitive direction $(u,v)$ and two side lengths, we derive several exact algorithms: the classical $O(n^2)$ sweep, decompositions of complexity $O(n^{3\mathrm{/}2}\log n)$ and $O(n^{4\mathrm{/}3}\log n)$, a ten-moment weighted-floor-sum reduction of complexity $O(n{\log }^{3}n)$, and a divisor-layer algorithm with the complexity $O(n{\log }^{2}n)$. We also give an all-values algorithm that computes $F(1),\dots ,F(N)$ in $O(N^{3\mathrm{/}2})$ arithmetic operations. The main idea behind the near-linear one-value algorithms is to reduce the geometric summation to constant-size families of weighted floor sums closed under Euclidean-style affine and reciprocal transformations. Besides the exact algorithmic results, we derive a two-term asymptotic expansion, $F(n)=\frac{4\log 2-1}{{\pi }^2}{n}^4\log n+B{n}^4+o(n^4)$ with the explicit formula for $B$, which provides an independent consistency check for the large-$n$ numerical data produced by the algorithms.