Перуански математик оптимизира решетото на Ератостен за намиране на прости числа

0
574

38-годишният перуански математик Харалд Хелфгот преди три години доказа тринарната хипотеза на Голдбах, според която всяко нечетно число, започвайки от 7, може да бъде представено като сума от три прости числа. Доказателството се счита за голямо математическо откритие, което e важно в информатиката, понеже на практика всички криптиращи системи използват големи прости числа.

 

Този път Хелфгот оптимизира компютърния алгоритъм за намиране на прости числа чрез решетото на Ератостен, в който се използва значително по-малко памет.

Древногръцкият математик, астроном, географ, филолог и поет Ератостен през 3-ти век преди новата ера е измислил гениален начин за намиране на прости числа. Идеята е съвсем проста: в таблица с последователно записани числа зачеркваме всички съставни числа, след което остават само простите числа и методът наистина напомня пресяване с помощта на решето.

 

Идеята на перуанския математик е следната: той разглежда съставните числа като звукова вълна или сбор от звукови вълни. С помощта на преобразованието на Фурие той филтрира тези хармоници, а останалият шум са простите числа. Новият алгоритъм е по-сложен, но вместо N памет, използва ∛N (кубичен корен) обем памет.

Ако оригиналният алгоритъм използва примерно 1 GB (гигабайт) памет, новият алгоритъм при същите изчислени прости числа използва едва 1 KB (килобайт). По-малкото обръщение към паметта значително ускорява работата на новия алгоритъм и той е осезаемо по-бърз от стандартния.

ДОБАВИ КОМЕНТАР

avatar
  Абонирай се  
Извести ме за