Abstract
A chained-matrices approach for parallel computing the nth convergent of continued fractions is presented. The resulting algorithm computes the entire prefix values of any continued fraction in O(log n) time on the EREW PRAM model or a network with O(n/log n) processors connected by the cube-connectedcycles, binary tree, perfect shuffle, or hypercube. It can be applied to approximate the transcendental numbers, such as π and e, in O(log m) time by using O(m/log m) processors for a result with m-digit precision. We also use it to costoptimally solve the second-order linear recurrence, the polynomial evaluation, the recurrence of vector norm, the general class of recurrence equation defined by Kogge and Stone (1973), and the general mth order linear recurrence. It is easy to implement because there are only some matrix multiplications and a division operation involved.
Original language | English |
---|---|
Pages (from-to) | 65-80 |
Number of pages | 16 |
Journal | Journal of Scientific Computing |
Volume | 9 |
Issue number | 1 |
DOIs | |
Publication status | Published - 1994 Mar |
Keywords
- Continued fractions
- parallel computation
- parallel-prefix problem
- polynomial evaluation
- recurrence equations
ASJC Scopus subject areas
- Software
- Theoretical Computer Science
- Numerical Analysis
- General Engineering
- Computational Theory and Mathematics
- Computational Mathematics
- Applied Mathematics