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.
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