Sign In

Communications of the ACM

ACM TechNews

New Take on an Ancient Method Improves Way to Find Prime Numbers


View as: Print Mobile App Share: Send by email Share on reddit Share on StumbleUpon Share on Hacker News Share on Tweeter Share on Facebook
An illustration of the sieve of Eratoshthenes.

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

Sign In for Full Access
» Forgot Password? » Create an ACM Web Account