# Accession Number:

## AD0743914

# Title:

## A Bound on the Multiplication Efficiency of Iteration.

# Descriptive Note:

## Technical rept.,

# Corporate Author:

## CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

# Personal Author(s):

# Report Date:

## 1972-03-01

# Pagination or Media Count:

## 14.0

# Abstract:

For a convergent sequence xi generated by xi1 phi xi,Xi-1,...,xi-dt1, define the multiplication efficiency measure E to be log of p to the base 2M, where p is the order of convergence, and M is the number of multiplications or divisions needed to compute phi. Then, if phi is any multivariate rational function, E or 1. Since E 1 for the sequence xi generated by xi1 xi squared xi - 14 with the limit - 12, the bound on E is sharp. Let PM denote the maximal order for a sequence generated by an iteration with M multiplications. Then PM or 2 sup M for all positive integer M. Moreover this bound is sharp. Author

# Descriptors:

# Subject Categories:

- Theoretical Mathematics