On Sat, 24 Jul 1999, Dave Bell wrote:

> Bob Drzyzgula <pic@DRZYZGULA.ORG> wrote:
>
> >I was fooling around with this today (avoiding fixing
> >the oven, I'm sure I'll have to pay for that soon),
> >and I found an interesting twist on this series.
>
> >I had this gut feeling that the series Myke listed had
> >popped out of an Euler transformation somehow, and I was
> >fooling around with that. What I noticed, however, was that
> >if the Euler transformation was applied backward of what
> >I had first thought (and I'm not this smart, this is an
> >immediate consequence of a derivaton in R.W. Hamming's
> >book on Numerical Methods, section 12.6, on page 203 of
> >the Dover edition), that you can improve the convergence
> >of such a series while still working exclusively with
> >powers of two. In particular, the series
>
> >  1/2 * ( 1/4 + 1/16 + 1/64 + 1/256 + ... + 1/(4^n) + ... )
>
> >Also converges to 1/3, but at a much quicker rate.
> >I calculated the two series in Excel to demonstrate:
>
> >Index   Myke's Series   Powers of 1/4
> >1       0.5             0.25
> >2       0.25            0.3125
> >3       0.375           0.328125
> >4       0.3125          0.33203125
> >5       0.34375         0.333007813
> >6       0.328125        0.333251953
> >7       0.3359375       0.333312988
> >8       0.33203125      0.333328247
>
> ...  all of which amounts to multiplying the Numerator (N) by the binary
> expansion of 1/the Denominator (1/D). Note that the binary digits of 1/3
> are a repeating fraction, 0.01010101......, and that the positions with
> 1's correspond to the terms that are present in Bob's series. Take the
> same expansion of any fraction, and do likewise. In Myle's original case,
> 1/7 = 0.0010010010......

Bingo!

This is the way those routines I posted yesterday work. 1/7 is
particularly 'nice' because there are only two binary 1's in a run of 8
binary digits. Hence there are only two additons. The only caveat is that
these need to be 16 bits. Roundoff errors would kill you otherwise.

If I were to obtain a 16-bit result instead of 8, I'd certainly
investigate that repeating '001' pattern.

As a general rule-of-thumb, I'd say that series approximations on a pic
are not the way to go. If you're looking for upto 16-bit results then an
optimized algorithm and/or a look-up table with interpolation is a better
way to go.  If you need more than 16-bits then the trade off is less
clear. (Division by a constant would still be handled more efficiently
using these specialized algorithms. However, finding the arcsine of a
32-bit floating point number, well... Who'd want to do that on a pic? :)