An Algorithm for some Sum of Reciprocals

V. I. Vichirko

Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part II, Tome 137 (1984), pp. 3-6

Résumé

We describe an algorithm for approximate evaluation of the set of sums $\varphi_k=\sum_{j=1}^ncj/(\lambda_j+\lambda_k),\;1\leqslant k\leqslant n$, where $0\alpha\leqslant \lambda_j\leqslant \beta$. The time complexity of the algorithm is $O(n(t+\log n)\Psi(t+\log n))$, when computing $\varphi_k$ with precision $2^{-t}$, where the function $\Psi(l)$ denotes the time required for snjutiplieation of two integers of binary length $l$.