= Arithmetic work of the Dirichlet hyperbola method
The direct <divisor summatory function> formula evaluates $N$ floor divisions. Its balanced <Dirichlet hyperbola method> formula evaluates $r=\lfloor\sqrt N\rfloor$ floor divisions and reuses their <sum> for the other strip, followed by doubling and square-overlap subtraction. Thus it uses $O(\sqrt N)$ <arithmetic operations>, with <big O notation>, in a model that counts each division, addition and multiplication as one operation. At $N=10^6$, the division counts for these two formulas are $10^6$ and $10^3$.
\Image[/dirichlet-hyperbola-work-and-partial-sums.png]
{title=The balanced <Dirichlet hyperbola method> reduces floor divisions from $N$ to $\lfloor\sqrt N\rfloor$; for $N=12$, two sequences of <partial sums> reach the same exact answer 35}
For a general <Dirichlet convolution>, the asymmetric formula has $\lfloor A\rfloor+\lfloor B\rfloor$ outer terms; evaluating $F$ and $G$ has an additional cost. Under $AB=N$, equal thresholds minimize $A+B$, but an asymmetric split can be useful if the two <partial sums> have different evaluation costs. The balanced <divisor summatory function> gains the further reuse because its two <arithmetic functions> are identical.
These are <arithmetic operation> counts, rather than counts of elementary operations on <binary digits>: the <integers> grow with $N$, and division of longer <integers> costs more in that model of <computational complexity theory>. Computing $r$ also requires an exact integer <square root>, or checking and correcting a numerical <square root> until $r^2\le N<(r+1)^2$ holds.
Back to article page
