In studying the complexity of iterative processes it is usually assumed that the arithmetic operations of addition, multiplication, and division can be performed in certain constant times. This assumption is invalid if the precision required increases as the computation proceeds. We give upper and lower bounds on the number of single-precision operations required to perform various multiple-precision operations, and deduce some interesting consequences concerning the relative efficiencies of methods for solving nonlinear equations using variable-length multiple-precision arithmetic. A postscript describes more recent developments.
翻译:在研究迭代过程的复杂性时,通常假定在一定的固定时间内可以进行加法、乘法和分法的算术操作。如果计算过程随着计算过程的进行而增加精确度,这一假设是无效的。我们给出了进行各种多精度操作所需的单精度操作数量的上下限,并推断了使用可变长多精度算术解决非线性方程的方法的相对效率所产生的一些有趣的后果。一个上标描述了最近的发展情况。