A chained-matrices approach for parallel computation of continued fractions and its applications

Shun-Shii Lin*

*此作品的通信作者

研究成果: 雜誌貢獻期刊論文同行評審

7 引文 斯高帕斯(Scopus)

摘要

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.

原文英語
頁(從 - 到)65-80
頁數16
期刊Journal of Scientific Computing
9
發行號1
DOIs
出版狀態已發佈 - 1994 三月

ASJC Scopus subject areas

  • 軟體
  • 理論電腦科學
  • 數值分析
  • 工程 (全部)
  • 計算機理論與數學
  • 計算數學
  • 應用數學

指紋

深入研究「A chained-matrices approach for parallel computation of continued fractions and its applications」主題。共同形成了獨特的指紋。

引用此