Are there any fast algorithms to evaluate a sum of the form (a * n b) / (c * n d) for a, b, c, d fixed, and n ranging from 1 to around 10^14 or so?

Obviously, summing each term individually won't work due to the size of the sum.

Edit: An algorithm to sum 1 / (c * n d) would suffice, since you can split the fraction up and sum each numerator in O(1) time.

CodePudding user response：

You can reduce the summation to that of the inverses of n α, which yields a shifted Harmonic number, corresponding to the Digamma function. The value is asymptotic to ln(n) Γ (Euler's constant), with a correction for the missing/additional initial terms from 1 to floor(α).

For an approximation of the Digamma function, check https://en.wikipedia.org/wiki/Digamma_function#Computation_and_approximation