Случайный поиск или на удивление быстрый поиск

Постановка задачи простая: найти глобальный минимум функции. Метод решения - постой случайных поиск.
После моих испытаний случайной сортировки я немного не доверял этому методу - за сколько времени он может найти решение с требуемой точностью. Оказалось, что при правильной оптимизации алгоритма это может произойти довольно быстро.

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

Собственно алгоритм простой:

1. Вычисляем требуемое количество точек, чтобы с указанной вероятностью P найти минимум с указанной точностью;
2. Генерируем с равномерным распределением нужное количество точек и находим в какой из целевая функция принимает минимальное значение.

Алгоритм очень простой, теперь поговорим про две реализации, первая - которая приходит первой на ум, вторая - немного оптимизированный вариант. На счёт генерации - стандартный генератор C/С++ примерно воспроизводит равномерное распределение, поэтому использовать можно его.

Первая реализация
Всё просто на очередной итерации генерируем новую точку - если значение в ней меньше значения в текущем приближении, выбираем её за новое приближение, иначе приближение остаётся старым.
Плюсы: быстрота и компактность реализации.
Минусы: для достижения приличной точности в большой области требуется выполнить очень много вычислений(более миллиарда) и поэтому эта реализация очень медленная.
Ну а теперь моя версия, как улучшить реализацию алгоритма, не затратив слишком много памяти, но выйграв по времени.

Вторая реализация
Поскольку точки могут генерироваться независимости друг от друга, а так же вычисляться значение функции, то первое что пришло на ум - распараллелить. Осталось это сделать так, чтобы прога не занимала слишком много памяти(3 миллиарда double - это всё-таки уже много, если я не ошибся 22.4 Гб, если размер типа 8 байт). Поэтому реализовывалось всё так:
У нас есть n потоков, каждый поток должен посчитать по m точек, за раз он считает N точек(тоже параллельно), выбирает из них минимум и сравнивает с текущим приближением, далее, если надо меняет текущее приближение и генерирует ещё N точек и так пока не сгенериует их m штук. В конце у нас остаётся n чисел - минимум из каждого потока, их них выбирается уже глобальный минимум.
Число N можно высчитывать как-нибудь из сходя из общего числа точек на поток, но я просто бал фиксированно N = 10000 (были и другие варианты). Потому что меньших N (при N = 100) затраты на создание потоков были больше чем выгода.
Так что если нам надо хранить три числа(координаты точки и значение функции), то уйдёт всего 3*(n + n*N) ячеек памяти, что намного меньше чем 3*n*m (учитываем, что число потоков n на персональном компьютере невелико - от 2 до 16, примерно, а число m может быть несколько сотен миллионов, то выигрыш в памяти, по сравнению в всеобщим распараллеливанием виден).
Теперь зачем нужно делать это порциями по N штук, а не посчитать по m на потоке - по тем же самым причинам время и память, в рассматриваемом случае минимум из N ищется очень быстро(если ещё упорядочивать при добавлении то ещё быстрее) и памяти надо дополнительной, под 3*N, а не 3*m.
Плюсы: скорость - вот тут и было моё удивление, меньше за минуту на 4-х потоках обрабатывает до миллиарда точек.
Минусы: в реализации конечно не сильно труден, но значительно труднее чем первый метод.

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