Математика гипотеза Коллатца "3N+1", ускорение вычислений.[Решено]

[Oki]

Эта задача хорошо параллелится и ее можно выполнить на нескольких ядрах процессора что дополнительно уменьшит время.

Каким образом хорошо параллелится?

 

[Prog]

Каким образом хорошо параллелится?

Разве выполнение следующих вычислений зависит от предыдущих? То есть чтобы к примеру вычислить значение для числа 100 нужны данные предыдущих вычислений?

Вычисление в 10 потоках. Миллион чисел обрабатываются за 200 мс. Если исключить из кода запись результата в массив, время уменьшается до 80 мс. Результат записывается в файл Result.txt

 

[Oki]

Разве выполнение следующих вычислений зависит от предыдущих? То есть чтобы к примеру вычислить значение для числа 100 нужны данные предыдущих вычислений?

Да, зависит. Вычисления итераций идут по цепочке. Можно, конечно, заготовить файл или массив (что сильно ограничено в объёме) результатов применения итерации для всех последовательных чисел, но так никто обычно не делает (кроме специфических целей), так как объём требующейся информации намного превышает длины цепочек, да к тому же скорость помещения результатов в блоки информации и чтения из них по индексу занимает время, сравнимое с выполнением одной итерации даже при работе с оперативной памятью (а при работе с файлом вообще сильно проигрывает), а посему не даёт практического эффекта даже при равноценном сравнении, о котором и речи нет, поскольку в некотором смысле в среднем старт с числа N требует порядка 3 * Log(N) / Log (4/3) итераций, что куда меньше полного перебора всех чисел от 1 до N. Поэтому многопоточность вижу целесообразной только при работе с очень огромными числами в последовательности исключительно для ускорения арифметики огромных чисел. Ну или для специфической постановки исследовательской задачи на эту тему.

 

[Prog]

Да, зависит.

Где вы увидели зависимость в этом коде? https://autoit-script.ru/threads/gi...orenie-vychislenij-resheno.28551/#post-156682
Глобальных и статических переменных нет. В функцию не передается ничего кроме числа. Это значит что вычисление для каждого числа производится независимо.

В предыдущем сообщении я прикрепил файлы. Запустите приложение и посмотрите результат в файле Result.txt (в блокноте не открывать - повиснет из-за большого размера файла).
Он такой же как при вычислении в одном потоке. Но скорость вычисления во много раз выше.

 

[Oki]

Стоп, если имеется в виду не единичное выполнение алгоритма, а реализация собственно цикла работы алгоритма для различных чисел, то, конечно же, сам такой цикл легко параллелится, но выполнение алгоритма для заданного числа требует последовательного прохождения цепочки итераций.

Сообщение автоматически объединено: 19 Янв 2022

На несколько секунд моё добавление запоздало. Действительно, имелось в виду распараллеливание цикла повторений алгоритма, а не алгоритма, как такового. А вот в большом проекте распределённых вычислений для исследовательских целей сама постановка задачи изменена для ещё намного более эффективного распараллеливания.