A chained-matrices approach for parallel computation of continued fractions and its applications. (English) Zbl 0810.65018
A chained-matrices approach for parallel computing the \(n\)th convergent of continued fractions is presented here. The algorithm developed 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 connected cycles etc. The algorithm is applied to approximate \(\pi\) and \(e\) in \(O(\log m)\) time by using \(O(m/ \log m)\) processors for a result with \(m\) digit precision. Cost optimal solutions of a number of related problems are also given here.
Reviewer: C.L.Koul (Jaipur)
MSC:
| 65D20 | Computation of special functions and constants, construction of tables |
| 65Y05 | Parallel numerical computation |
| 65B05 | Extrapolation to the limit, deferred corrections |
| 33B10 | Exponential and trigonometric functions |
| 26A09 | Elementary functions |
| 40A15 | Convergence and divergence of continued fractions |
References:
| [1] | Akl, S. G. (1989).The Design and Analysis of Parallel Algorithms, Prentice-Hall, Englewood Cliffs, New Jersey. · Zbl 0754.68053 |
| [2] | Bilardi, G., and Preparata, F. P. (1989). Size-time complexity of boolean networks for prefix computations,Journal of the ACM 36(6), 362–382. · Zbl 0679.68071 · doi:10.1145/62044.62052 |
| [3] | Brent, R. P. (1974). The parallel evaluation of general arithmetic expressions,Journal of the ACM 21(2), 201–206. · Zbl 0276.68010 · doi:10.1145/321812.321815 |
| [4] | Brent, R. P., and Lung, H. T. (1982). A regular layout for parallel adders,IEEE Trans. Comput. C-31(3), 240–264. · Zbl 0477.94037 · doi:10.1109/TC.1982.1675982 |
| [5] | Carlson, D. A., and Sugla, B. (1984). Time and processor efficient parallel algorithms for recurrence equations and related problems, inProc. Int’l. Conf. on Parallel Processing, pp. 310–314. |
| [6] | Chung, K. L., and Lin, F. C. (1991). A cost-optimal parallel algorithm for B-spline surface fitting,Graphical Models and Image Processing 53(6), 601–605. · Zbl 0799.65007 · doi:10.1016/1049-9652(91)90010-H |
| [7] | Chung, K. L., Lin, F. C., and Chen, W. C. (Unpublished). Parallel computation of continued fractions (Submitted toJournal of Parallel and Distributed Computing). |
| [8] | Fich, F. E. (1983). New bounds for parallel prefix circuits, inProc. of the 15th Annual ACM Symposium on Theory of Computing, pp. 100–109. |
| [9] | Goldschlager, L. M. (1982). A universal interconnection pattern for parallel computers,Journal of the ACM 29(4), 1073–1086. · Zbl 0489.68042 · doi:10.1145/322344.322353 |
| [10] | Gottlieb, A., and Schwartz, J. T. (1982). Networks and algorithms for very-large-scale parallel computation,Computer, pp. 27–36. |
| [11] | Gries, D., and Levin, G. (1980). Computing Fibonacci numbers (and similarly defined functions) in log time,Inform. Process. Lett. 11(2), 68–69. · Zbl 0452.68052 · doi:10.1016/0020-0190(80)90003-4 |
| [12] | Hsu, W. J., Page, C. V., and Liu, J. S. (1992). Computing prefixes on a large family of interconnection topologies, inProc. Int’l. Conf. on Parallel Processing, pp. 153–159. · Zbl 0850.68213 |
| [13] | Jaluria, Y. (1988).Computer Methods for Engineering, Allyn and Bacon, Inc. · Zbl 0693.68001 |
| [14] | Knuth, D. E. (1981).The Art of Computer Programming, Vol. 2, 2nd edition, Addison-Wesley, Reading, Massachusetts. · Zbl 0477.65002 |
| [15] | Kogge, P. M., and Stone, H. S. (1973). A parallel algorithm for the efficient solution of a general class of recurrence equations,IEEE Trans. Comput. C-22(8), 786–793. · Zbl 0262.68015 · doi:10.1109/TC.1973.5009159 |
| [16] | Lander, R. E., and Fischer, M. J. (1980). Parallel prefix computation,Journal of the ACM 27 831–838. · Zbl 0445.68066 · doi:10.1145/322217.322232 |
| [17] | Lin, S. S., and Lin, F. C. (1991). AnO(logn) algorithm for computing periodic continued fractions and its applications,Computers Math. Applic. 21(2–3), 1–6. · Zbl 0714.11089 · doi:10.1016/0898-1221(91)90074-E |
| [18] | Manber, U. (1989).Introduction to Algorithms A Creative Approach, Addison-Wesley Publishing Company Inc. · Zbl 0825.68397 |
| [19] | Martin, A. J., and Rem, M. (1984). A representation of the Fibonacci algorithm,Inform. Process. Lett. 19(2), 67–68. · Zbl 0563.10004 · doi:10.1016/0020-0190(84)90099-1 |
| [20] | Meijer, H., and Akl, S. G. (1987). Optimal computation of prefix sums on a binary tree of processors,IJPP 16(2), 127–136. · Zbl 0639.68032 |
| [21] | Munro, J. I., and Paterson, M. (1973). Optimal algorithms for parallel polynomial evaluation,Journal of Computers and System Sciences 7(2), 189–198. · Zbl 0256.68013 · doi:10.1016/S0022-0000(73)80043-1 |
| [22] | Olds, C. D. (1963).Continued Fractions, Random House Inc., L. W. Singer Company, New York. · Zbl 0123.25804 |
| [23] | Preparata, F. P., and Vuillemin, J. (1981). The cube-connected cycles: a versatile network for parallel computation,Communications of the ACM, pp. 300–309. |
| [24] | Stone, H. S. (1971). Parallel processing with the perfect shuffle,IEEE Trans. Comput. C-20(2), 153–161. · Zbl 0214.42703 · doi:10.1109/T-C.1971.223205 |
| [25] | Urbanek, F. J. (1980). AnO(logn) algorithm for computing thenth element of the solution of a difference equation,Inform. Process. Lett. 11(2), 66–67. · Zbl 0458.68010 · doi:10.1016/0020-0190(80)90002-2 |
| [26] | Wilson, T. C., and Shortt, J. (1980). AnO(logn) algorithm for computing general order-k Fibonacci numbers,Inform. Process. Lett. 10(2), 68–75. · Zbl 0437.10004 · doi:10.1016/S0020-0190(80)90076-9 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
