I came across this problem while reading Blelloch's Prefix Sums and Their Applications:
Show how the recurrence $x_i = a_i + b_i/x_{i-1}$
where + is numeric addition and / is division, can be converted into a $2^{nd}$ degree recurrence of the form:
$\begin{equation} x_i=\begin{cases} a_i, & \text{$0 \leq i\lt2$}\\ (x_{i-1} \otimes a_{i,1} )\oplus(x_{i-2} \otimes a_{i,2})\oplus b_i, & \text{$2 \leq i \lt n$}. \end{cases} \end{equation} $
Where $ \oplus$ is associative, $ \otimes$ is semi-associative and $ \otimes$ distributes over $ \oplus$.
One this form is achieved, one can employ (parallel) prefix sum to compute $x_i$.
Initial findings:
1) Since division is neither associative nor does it distribute over addition, some sort of a clever transform is called for.
2) I thought about using transform $y_i := \log(x_i)$. While this will conveniently handle the division, it creates another problem, i.e. $\log()$ of a sum. Besides, it would have been $1^{st}$ not $2^{nd}$ order which the problem specifies.
Could you offer me some hints please?