Check Levi9 best QA positions to Backbase team! ✖

×Закрыть

Разработка · 13 декабря 2009, 22:14 1178

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

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

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

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

Темы: алгоритм

👍НравитсяПонравилось0

В избранноеВ избранном0

Facebook

Twitter

Похожие топики

Ctrl + Enter

Yuri Bonya Scala Developer в Daxx 14.12.2009 12:56

Александр, я соглашусь с Mike Gorchak, что браться за задачу в такой постановке невозможно — задачи найти все простые числа в интервале и просто генерировать большие простые числа совершенно разные. Если вы возьметесь за задачу генерации (псевдо) простых чисел, то одной многословной арифметики вам не хватит — нужна будет модульная арифметика. Вряд ли от вас требуется все это. Если же я ошибаюсь, то неплохой связкой для работы в том числе с большими числами, модульной арифметикой и генерацией простых чисел является библиотека NTL, собранная с уже упомянутой GMP.

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

Ответить

Поддержать

Александр Колосов 14.12.2009 10:56

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

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

Ответить

Поддержать

Mike Gorchak Graphics Device Driver Developer 14.12.2009 10:38

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

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

Ответить

Поддержать

Александр Колосов 14.12.2009 09:50

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

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

Ответить

Поддержать

Mike Gorchak Graphics Device Driver Developer 14.12.2009 07:30

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 секунд. На том же питоне такого не сделаешь — эффективные алгоритмы необходимо реализовывать средствами самого питона, тогда будет проблема скорости выполнения интрепретируемого кода.

Ответить

Поддержать

Illia Khabibrakhmanov SSE 14.12.2009 06:53

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

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

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

Ответить

Поддержать

Yuri Bonya Scala Developer в Daxx 14.12.2009 06:32

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

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

Ответить

Поддержать

Mike Gorchak Graphics Device Driver Developer 14.12.2009 05:52

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

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

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

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