Вычисление простых чисел

Выполняю тестовое задание «вычисление простых чисел». Там есть пунктик «Цель задания: оценить уровень соискателя в написании многопоточных программ и синхронизации потоков»

А ведь сам знаю, что вычисление простых чисел потянет за собой: «длинную» арифметику, умножение с помощью БПФ и еще кучу всего...

Как вы думаете, может ограничится диапазоном «поиска» 0−2^32, и не напрягаться особо?

👍НравитсяПонравилось0
В избранноеВ избранном0
LinkedIn
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Александр, я соглашусь с Mike Gorchak, что браться за задачу в такой постановке невозможно — задачи найти все простые числа в интервале и просто генерировать большие простые числа совершенно разные. Если вы возьметесь за задачу генерации (псевдо) простых чисел, то одной многословной арифметики вам не хватит — нужна будет модульная арифметика. Вряд ли от вас требуется все это. Если же я ошибаюсь, то неплохой связкой для работы в том числе с большими числами, модульной арифметикой и генерацией простых чисел является библиотека NTL, собранная с уже упомянутой GMP.

Для случая с написанной самостоятельно длинной арифметикой возможности распараллеливания тоже есть, так что у вас большой простор для фантазии (для практического применения будет достаточно реализовать алгоритм Карацубы или Тума-Кука или вообще школьный алгоритм умножения в столбик).

А я наверное возьмусь за этот проект, на тестовое задание под Винду чего-нибудь накрапаю, ,
но хочется попробовать сделать распределенные вычисления в QNX. Благо на работе можно этим по вечерам заниматься.

QNX у нас нас 15 компах.

1а) При использовании gmp и при условии наличия опыта работы с gmp, то где-то пол дня работы. В gmp есть реализация и вероятностных алгоритмов поиска простых чисел и реализации различных алгоритмов проверки на простоту. Т.е. фактически работа сводится к «Цель задания: оценить уровень соискателя в написании многопоточных программ и синхронизации потоков». Фактически есть поток-диспетчер, который определяет вероятность нахождения простого числа в заданном диапазоне, и рабочие потоки, которые проверяют наличие этого самого простого числа в заданном диапазоне.
1 б) Если всю математику работы с большими числами делать самому, то данного условия задачи недостаточно для определения времени разработки. Если мне память не изменяет, то у Кнута весь второй том посвящен этому, и выбор какого-то конкретного алгоритма нужно делать осознанно, зная с каким объёмом данных придётся работать. Вычислительная сложность реализации vs. скорость работы на определённом объёме данных. Я всё-таки склоняюсь к мысли, что ограничиться диапазоном 0...2^32−1, используя один из алгоритмов решёт, как тут советовали. Ибо цель задачи всё-таки никак не связана с простыми числами:) 3 часа в такой облегчённой постановке.

2) Я бы не взялся за задачу в такой постановке:)

Mike Gorchak, часто читаю Ваши посты, очевидно Вы занимаетесь программированием давно и серьезно.
Можете ответить на вопрос:
Сколько бы Вам потребовалось бы часов на написание черновой, но рабочей версии данного приложения,

и скалько денег Вы бы за это взяли? :)


Mike Gorchak, скажите, а чем функциональные языки плохи для это задачи?
Дело не типе языков, а в том что изначально они не разрабатывались как средства для написания числодробительных задач, и реализации поддержки больших чисел в них сделаны на неплохом уровне, но тем не менее применённые алгоритмы далеки от совершенных, и это просто операции с большими числами, не более того. С уверенностью могу сказать только за python. Конечно, это поправимо за счёт использования быстрых реализаций. Это первое:) Второе, в интерпретируемых языках простые математические операции над большими числами будут медленее при частых использованиях: сравнение, сложение, вычитание, умножение, деление. Например,
for (i=0; i< 1024; i++)
{
y (i+1) = (19381*y (i) +c) mod 2^16;
}
Третье, спаренные операции (возможность объединения операций). На C гораздо проще написать некоторые такие операции, например, эффективную классическую MULTIPLY-ADD конструкцию, чем на питоне, в питоне такой операции просто нет.

Я помню как ждал 30 минут расчёт двух ^1024 взаимнопростых чисел после первого запуска программки, которая использовала элементарные математические конструкции, и впоследствии за две недели довёл её до 17 секунд. На том же питоне такого не сделаешь — эффективные алгоритмы необходимо реализовывать средствами самого питона, тогда будет проблема скорости выполнения интрепретируемого кода.


* или использовать язык со встроенной поддержкой больших чисел (к примеру: python, haskell, erlang, common lisp)

Плохой совет для такой задачи:)

Mike Gorchak, скажите, а чем функциональные языки плохи для это задачи?

зы. спрашиваю потому что не знаю

Думаю, что в задании просто требовалось реализовать решето Эратосфена с использованием нескольких потоков.
Разделяемым ресурсом будет массив битовых флагов, оптимальное количество потоков и стратегию их возвращения в пул (очевидно, что трудоемкость задачи каждого потока растет линейно) надо продумать отдельно.

Если же требуется генерация больших (псевдо) простых чисел, то это совсем другая история. Могу посоветовать почитать Handbook of Applied Cryptography www.cacr.math.uwaterloo.ca/...about/chap4.pdf или Лекции по арифметическим алгоритмам в криптографии, Черемушкин А.В.

Мне кажется что чаще всего как раз нужны большие простые числа.

Как правило, нужнее всего взаимнопростые числа.

А ведь сам знаю, что вычисление простых чисел потянет за собой: «длинную» арифметику, умножение с помощью БПФ и еще кучу всего...

БПФ появляется тогда, когда числа действительно очень большие, обычное умножение в столбик с разрядами 2^64 гораздо эффективнее. 4096 бит на число — это ещё не большое число.

* использовать готовую библиотеку для длинной арифметики, напр., libgmp

Хороший вариант для начала, не оптимален, правда, по скорости.

* или использовать язык со встроенной поддержкой больших чисел (к примеру: python, haskell, erlang, common lisp)

Плохой совет для такой задачи:)

Александр: не напрягаться можно, если:
* использовать готовую библиотеку для длинной арифметики, напр., libgmp

* или использовать язык со встроенной поддержкой больших чисел (к примеру: python, haskell, erlang, common lisp)

Да смысла особого нет. Тем более за качественно сделанную работу еще могут заплатить премию (прочитал по вышеуказанной ссылке) :)

Мне кажется что чаще всего как раз нужны большие простые числа.
Большие простые числа (порядка 10^300) используются в криптографии с открытым ключом.

Есть ли смысл в многопоточных программах и синхронизации потоков для «поиска» 0−2^32?

Подписаться на комментарии