An Unbounded Spigot Algorithm for the Digits of Pi
Rabinowitz and Wagon (<i>American Mathematical Monthly</i> 102(3):195–203, 1995) present a <em>spigot algorithm</em> for computing the digits of π. A spigot algorithm yields its outputs incrementally, and does not reuse them after producing them. Their algorithm is inherently...
| Main Author: | |
|---|---|
| Format: | Journal article |
| Published: |
2015
|
| _version_ | 1797061215531302912 |
|---|---|
| author | Gibbons, J |
| author_facet | Gibbons, J |
| author_sort | Gibbons, J |
| collection | OXFORD |
| description | Rabinowitz and Wagon (<i>American Mathematical Monthly</i> 102(3):195–203, 1995) present a <em>spigot algorithm</em> for computing the digits of π. A spigot algorithm yields its outputs incrementally, and does not reuse them after producing them. Their algorithm is inherently <em>bounded</em>; it requires a commitment in advance to the number of digits to be computed, and in fact might still produce an incorrect last few digits. We propose two <em>streaming algorithms</em> based on the same characterization of π, with the same incremental characteristics but without requiring the prior bound. |
| first_indexed | 2024-03-06T20:27:53Z |
| format | Journal article |
| id | oxford-uuid:30023054-4642-47d7-a138-f9ad4fff9add |
| institution | University of Oxford |
| last_indexed | 2024-03-06T20:27:53Z |
| publishDate | 2015 |
| record_format | dspace |
| spelling | oxford-uuid:30023054-4642-47d7-a138-f9ad4fff9add2022-03-26T12:59:00ZAn Unbounded Spigot Algorithm for the Digits of PiJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:30023054-4642-47d7-a138-f9ad4fff9addDepartment of Computer Science2015Gibbons, JRabinowitz and Wagon (<i>American Mathematical Monthly</i> 102(3):195–203, 1995) present a <em>spigot algorithm</em> for computing the digits of π. A spigot algorithm yields its outputs incrementally, and does not reuse them after producing them. Their algorithm is inherently <em>bounded</em>; it requires a commitment in advance to the number of digits to be computed, and in fact might still produce an incorrect last few digits. We propose two <em>streaming algorithms</em> based on the same characterization of π, with the same incremental characteristics but without requiring the prior bound. |
| spellingShingle | Gibbons, J An Unbounded Spigot Algorithm for the Digits of Pi |
| title | An Unbounded Spigot Algorithm for the Digits of Pi |
| title_full | An Unbounded Spigot Algorithm for the Digits of Pi |
| title_fullStr | An Unbounded Spigot Algorithm for the Digits of Pi |
| title_full_unstemmed | An Unbounded Spigot Algorithm for the Digits of Pi |
| title_short | An Unbounded Spigot Algorithm for the Digits of Pi |
| title_sort | unbounded spigot algorithm for the digits of pi |
| work_keys_str_mv | AT gibbonsj anunboundedspigotalgorithmforthedigitsofpi AT gibbonsj unboundedspigotalgorithmforthedigitsofpi |