# Kahan Summation for Three-Term Recurrences

Kahan summation applies to summation problems, but not to three-term recurrence relations. However, a three-term recurrence shares many of the features of a summation-albeit with a rescaling step at each iteration. Hence there seems to be hope for a Kahan summation for three-term recurrences. Has this idea been worked out in the literature or is the idea flawed in some way?

• Kahan summation is like emulating double-double arithmetic with only double numbers. So if you want to use double-double arithmetic for a three-term recurrence, it's probably easier to just find a double-double (or a quad-double) library, if it's not already part of the language you're using, and use that. – Kirill Apr 14 '17 at 19:16
• True. However, if the user wants the speed, they can just use the -ffast-math flag and have the optimizer kill off the Kahan summation. Shipping a dependency is more painful. – user14717 Apr 14 '17 at 19:24
• @user14717 There are plenty of examples in the literature how to implement a double-native precision addition yourself, e.g. this paper. Kahan summation uses native precision for the source data and double-native precision for the result, but in a three-term recurrence (e.g. to compute Bessel functions) the source data is double-native precision as well after the first step, so you need double-native precision operations throughout. – njuffa Apr 14 '17 at 22:12
• "...a three-term recurrence shares many of the features of a three-term recurrence..." - what? – J. M. Apr 16 '17 at 1:19
• If you're computing the dominant solution of a three-term recurrence (e.g. $Y_n(x)$ for the Bessel recurrence), I don't see how something like Kahan could be shoehorned. If you're computing the (usually more interesting) minimal solution (e.g. $J_n(x)$ for the Bessel recurrence), you could maybe use Kahan along with Miller's algorithm. – J. M. Apr 16 '17 at 1:21