Communications of the ACM
New Take on an Ancient Method Improves Way to Find Prime Numbers
A mathematician at Germany's University of Gottingen has proposed an improvement to the sieve of Eratosthenes method for finding prime numbers.
Credit: mathforum.org/isaac
Mathematician Harald Helfgott at Germany's University of Gottingen has proposed improving an ancient method for finding prime numbers by reducing the requirement of physical space in computer memory and shortening the execution time of programs designed to make that calculation.
Helfgott's proposal involves enhancing the sieve of Eratosthenes, which "grows in proportion to the size of the interval considered," notes Cornell University professor Jean Carlos Cortissoz Iriarte. "But if you look at what needs to be kept in memory for each step of the algorithm performed for large intervals [numbers], then the sieve stops being efficient."
Helfgott was inspired by combined approaches to the century-old circle method to modify the sieve to function with less physical memory space. In mathematical terms, this means it is now sufficient to have the cube root of "N" instead of a space "N."
"To calculate all primes up to a trillion, the modified version of the sieve requires a few million bits instead of a billion bits," Helfgott says.
He acknowledges this space reduction implies "minor" sacrifices in the algorithm's theoretical speed, but thinks in certain ranges this loss could be countered or surpassed by the possibility of chiefly or solely using the cache memory.
From Scientific American
View Full Article
Abstracts Copyright © 2016 Information Inc., Bethesda, Maryland, USA
No entries found