Freshman Seminar 23j: Chess and Mathematics (Fall 2003)
Preliminary Question: Computing
The function
f(x) = 1 + x + x2 + x3 + x4
+ ... + x2002 + x2003
takes about 2 million arithmetic operations to compute as it stands,
using n-1 multiplications to compute each term xn.
Rewriting it as
f(x)=(1-x2004)/(1-x)
still leaves more than 2000 operations -- one of which is a division,
which may be problematic
(harder to implement, and imprecise if x is too close to 1).
But the number of operations to compute f(x)
can be brought much lower than 2000. In how few operations
can you calculate f(x):
i) Using all four arithmetic operations +, - ,* , /
(but no logarithms and exponentials...),
ii) Using only additions and multiplications?