Given a long decimal (or hexadecimal) expansion of pi, it shouldn't be too hard to generate a very large number of terms in the continued fraction expansion. One first forms the fraction p/10^n. The division step can be done approximately, adjusting by one if the approximate division was wrong, and the take the remainder step requires a scalar (i.e., "short * long") multiplication and a subtraction. Both are linear time. We do not need a "long * long" FFT-style multiplication, because most continued fraction terms are "small".
No comments :
Post a Comment