Abstract
The paper describes an interesting (and unexpected) application of the Fast Fourier transform in number theory. Calculating more and more decimals of p (first by hand and then from the mid-20th century, by digital computers) not only fascinated mathematicians from ancient times but kept them busy as well. They invented and applied hundreds of methods in the process but the known number of decimals remained only a couple of hundred as of the late 19th century. All that changed with the advent of the digital computers. And although digital computers made possible to calculate thousands of decimals, the underlying methods hardly changed and their convergence remained slow (linear). Until the 1970's. Then, in 1976, an innovative quadratic convergent formula (based on the method of algebraic-geometric mean) for the calculation of p was published independently by Brent [10] and Salamin [14]. After their breakthrough, the Borwein brothers soon developed cubically and quartically convergent algorithms [8,9]. In spite of the incredible fast convergence of these algorithms, it was the application of the Fast Fourier transform (for multiplication) which enhanced their efficiency and reduced computer time [2,12,15].
Original language | English |
---|---|
Pages | 59-64 |
Number of pages | 6 |
Publication status | Published - 20 Jan 2000 |
Event | 3rd TEMPUS-INTCOM Symposium on Intelligent Systems in Control and Measurements 2000 - Veszprém, Hungary Duration: 9 Sept 2000 → 14 Sept 2000 Conference number: 3 |
Conference
Conference | 3rd TEMPUS-INTCOM Symposium on Intelligent Systems in Control and Measurements 2000 |
---|---|
Country/Territory | Hungary |
City | Veszprém |
Period | 9/09/00 → 14/09/00 |
Keywords
- Fast Fourier transform
- Approximation theory
- Elliptic function