I'm calculating two sequences:
$x_{n+1} = (a - x_n)/2$
and
$x_{n+1} = a - x_n/2$
The goal is to divide $a$ by 3 (both $a$ and $x_n$ are whole numbers). I don't have access to general division, only division by powers of 2. Both sequences converge very slowly. Could you give a hint as to how I might accelerate the rate of convergence and how to wisely select $x_0$?
I reformulated the equations so I could use Newton's method, but it requires general division and does not work that well with whole numbers anyway. This applies to most other root-finding methods as well and something complex is out of the question anyway.
The solution already exists in form of 6502 code, but the programmer opted not to document the method (s)he was using to accelerate convergence. There exists an online 6502 emulator.
EDIT: In the end I decided to expand formula 2:
$x_{n+2}=a-x_{n+1}/2=a-(a-x_n/2)/2=(a+x_n/2)/2$
This is how we obtain the result of 2 iterations after 1 iteration and now I use this formula instead of the previous one. If 6502 code uses this approach is unclear to me.
another formula I came up with is:
$y_{n} = (x_{n+1} + x_{n+2}) / 2 = 3/4a - x/8$
which converges even faster (lol).