elementary number theory - Evaluating Jacobi's symbol using Eisenstein's algorithm

The algorithm is described as follow,

Eisenstein proposed the following algorithm for computing the Jacobi symbol $(a|n)$ where $a$ and $n$ are odd numbers. Write
$n = aq + er$ where $q = \lfloor n/a \rfloor$ if this is even, or $q = \lfloor n/a \rfloor + 1$ otherwise, and $e = \pm 1$ accordingly.
Then $r$ is odd, and you can use the quadratic reciprocity law and the formula for $(-1|r)$ to continue by replacing the pair $n,a$ with

the pair $a, r$.

I understand the Euler's algorithm (division), and got it to work correctly. Unfortunately, I have no idea how this algorithm works. Furthermore, what's the end condition of this algorithm? My guess was $r \neq 1$ is the end condition, but the result was completely wrong.
An example to illustrate this algorithm would be greatly appreciated.

Edit
This is my solution, written in C#

public int eisensteinAlgo( int a, int n ) {

            int parity = 1;
            int q = 0;
            int epsilon;
            int r = 0;
            while ( ( n % a ) == 0 ) {
                q = n / a;
                if ( ( q % 2 ) == 1 ) {
                    q += 1;
                    epsilon = -1;
                }

                else {
                    epsilon = 1;
                }
                r = n - ( a * q );
                r *= epsilon;
                parity *= ( int )Math.Pow( -1.0, ( r - 1 ) / 2 );
                n = a;
                a = r;
            }
            return parity;

}    

Thank you,

Answer

The reduction step is simply to apply quadratic reciprocity in order to rewrite $(a|n)$ to $\pm (n|a)\:,\:$ then reduce $n$ modulo $a\:$ in a way that the remainder stays odd (by forcing the quotient $q\:$ to be even). The algorithm terminates when $a$ divides $n\:,$ with the result being either the accumulated sign (if $ a=1)\:,$ or else $\:0\:$ (if $ a>1)\:.\:$ The choice of odd remainder eliminates the need to pull out factors of $2\:.$ But one pays a price for this algorithmic simplification since it makes the algorithm less efficient.