Выполняю тестовое задание «вычисление простых чисел». Там есть пунктик «Цель задания: оценить уровень соискателя в написании многопоточных программ и синхронизации потоков»
А ведь сам знаю, что вычисление простых чисел потянет за собой: «длинную» арифметику, умножение с помощью БПФ и еще кучу всего...
Как вы думаете, может ограничится диапазоном «поиска» 0−2^32, и не напрягаться особо?
Для случая с написанной самостоятельно длинной арифметикой возможности распараллеливания тоже есть, так что у вас большой простор для фантазии (для практического применения будет достаточно реализовать алгоритм Карацубы или Тума-Кука или вообще школьный алгоритм умножения в столбик).
QNX у нас нас 15 компах.
2) Я бы не взялся за задачу в такой постановке:)
и скалько денег Вы бы за это взяли? :)
Mike Gorchak, скажите, а чем функциональные языки плохи для это задачи?Дело не типе языков, а в том что изначально они не разрабатывались как средства для написания числодробительных задач, и реализации поддержки больших чисел в них сделаны на неплохом уровне, но тем не менее применённые алгоритмы далеки от совершенных, и это просто операции с большими числами, не более того. С уверенностью могу сказать только за python. Конечно, это поправимо за счёт использования быстрых реализаций. Это первое:) Второе, в интерпретируемых языках простые математические операции над большими числами будут медленее при частых использованиях: сравнение, сложение, вычитание, умножение, деление. Например,
Я помню как ждал 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)
Плохой совет для такой задачи:)
* или использовать язык со встроенной поддержкой больших чисел (к примеру: python, haskell, erlang, common lisp)
Да смысла особого нет. Тем более за качественно сделанную работу еще могут заплатить премию (прочитал по вышеуказанной ссылке) :)
Есть ли смысл в многопоточных программах и синхронизации потоков для «поиска» 0−2^32?
Yuri Bonya
Александр Колосов
Mike Gorchak
Illia Khabibrakhmanov
anonymous
Sergii Voloshyn
11 комментариев
Добавить комментарий Подписаться на комментарииОтписаться от комментариев