1
$\begingroup$

Suppose that $a,b,c,d$ are real number and $k$ is a positive integer number. Define the following function:

$f(k) = \frac{a + ck}{b + dk}.$

So, $f(0) = \frac{a}{b}$, $f(1) = \frac{a+c}{b+d}$, and so on. Is there a way to incrementally compute $f(1), f(2),\ldots, f(n)$ avoiding any division and possibly multiplications?

PS. This is related to this (Fast patch extraction using homography). I want to avoid homography-vector multiplications in a real-time image processing code. I think i got a way to do that, but for every pixel coordinates that i compute using the homography, i need to divide by the third component (please, look at that question to understand better what i am saying). I was wondering if i could avoid the 2 extra division-per-pixel, since i need it fast...

  • 2
    Why? Where does this come from?2011-09-21

2 Answers 2

1

If you write $f(k) = N(k)/D(k)$ then there is a simple incremental scheme for $N$ and $D$ which will avoid multiplications but I don't see how you can avoid the division: $ N(k+1) = N(k) + c, \qquad D(k+1) = D(k) + d $

1

Surely avoiding any division and possibly multiplications is a joke, so here is a formula to compute recursively $f(n)$ for every nonnegative integer $n$: $f(0)=a/b$ and, for every nonnegative $n$, $ \frac1{df(n+1)-b}=\frac1{df(n)-b}+\frac{d}{da-cb}. $