    Next: Sequences of operations Up: Logistic Map Previous: Dyadic Arithmetic

### Signed Binary Arithmetic

When we compute the logistic map using signed binary stream arithmetic, we observe that the maximum lookahead required is (n+2) for subtraction, (n+5) for multiplication and (n+2) for the shift left (multiplication by 4). This gives us a maximum lookahead of (n+9) for computation of f(x), and (n+9i) for f(x) iterated i times. Note that this is an upper bound as multiplication may be able to compute digits with as little as (n+2) lookahead and subtraction with (n+1), which would give lookahead (n+5i) as a lower bound.

The effect of this is that in order to compute 60 iterations of the logistic map to a precision of roughly 6 decimal digits (after this number of iterations our earlier test using double precision floating point arithmetic got no digits correct (see section 2.1.1), signed binary stream arithmetic would need to examine between 324 and 564 digits of input. In fact an experiment using the value `a` in section 7.2.2 as input showed the actual number of digits to be on the low side of this value at 382 digits. The actual lookahead will vary with the input used.

If we used signed binary (mantissa, exponent) arithmetic, the required upper bound would be only (n+6i).    Next: Sequences of operations Up: Logistic Map Previous: Dyadic Arithmetic
Martin Escardo
5/11/2000