Повышение производительности программы

Question

Я все еще новичок, который пытается получить основы C ++. Я писал консольное приложение, которое печатает простые числа в определенном диапазоне, и вот код (я использую CodeBlocks ):

bool isInteger(double i)
{
    int x = i;
    if ( i/x == 1)
    {
        return true;
    }else
    {
        return false;
    }
}

int DivTimes(double i)
{
    int counter = 0;
    for (int y = 2; y <= i; y++)
    {
        if (isInteger(i/y))
        {
            counter ++;
        }
    }
    return counter;
}

bool isPrime(double i)
{
    if (DivTimes(i) > 1)
        return false;
    else
        return true;
}

int main()
{
    for(int i = 999999910; i <= 1000000000 ; i++)
    {
        if (isPrime(i))
            cout << " " << i;
    }
}

для такого большого числа, как 1E9, производительность моей программы становится очень низкой и использует только 10% моего процессора. Итак, мне было интересно, есть ли способ заставить мою программу использовать больше ресурсов процессора и улучшить производительность программы?

Answer 1

Должно быть довольно легко улучшить скорость этого процесса.

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

Это означает, что нам нужно смотреть только на факторы вплоть до (и включая) квадратного корня из числа. Если нет коэффициента, меньшего или равного квадратному корню, то не будет и того, который больше квадратного корня. Мы также можем перестать искать, как только найдем один фактор (кроме 1), так как этого достаточно, чтобы сказать нам, что число не простое. Наконец, мы можем начать с попытки делить на 2. Если число делится на 2, оно не простое, и мы закончили. В противном случае мы знаем, что это странно, и нам не нужно пытаться делить на любые другие четные числа. Итак, после проверки делимости на два, мы начинаем наш цикл с 3 и добавляем 2 каждый раз вместо добавления 1.

Итак, давайте рассмотрим разницу в скорости для 1e9. Прямо сейчас вы делаете примерно 1e9 делений. Квадратный корень из 1e9 составляет около 31 623. Нам нужно только попытаться разделить на нечетные числа, поэтому мы разрезаем это пополам, поэтому в худшем случае мы пытаемся разделить на 15 811 различных чисел. Итак, в круглых числах мы ускорили работу примерно в 1e9 / 15811 = 63 000.

Если вы хотите пойти дальше, вы можете посмотреть на Сито Эратосфена. Используя его, вы можете найти все 50847534 простых чисел до 1e9 примерно за 30 секунд (на моей машине это занимает около 29 секунд, используя старый AMD A8-7600, которому не только 5 лет, но он был довольно медленным процессором, даже когда он был новым).

После этого вы можете сделать гораздо больше (Сегментированное сито, Сито Аткинса и т. Д.), Но этого, вероятно, достаточно, чтобы хотя бы начать работу.

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

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

#include <vector>
#include <iostream>

unsigned long primes = 0;

int main() {
    int number = 1'000'000'000;
    std::vector<bool> sieve(number,false);
    sieve[0] = sieve[1] = true;

    for(int i = 2; i<number; i++) {
        if(!sieve[i]) {
            ++primes;
            for (int temp = 2*i; temp<number; temp += i)
                sieve[temp] = true;
        }
    }
    std::cout << "found: " << primes << " Primes\n";
    return 0;
}

Answer 2

Короткий ответ : Не надо.

Длинный ответ : Это, вероятно, наиболее подходит для запроса в Computer Science SE, поскольку речь идет не о C ++а скорее об алгоритмах.

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

Если у вас есть веская причина использовать астрономические числа, то никакой компилятор C ++ вам не поможет, вам лучше использовать специализированныйматематическая платформа.Мы использовали Magma в университете, в который я ходил.

Вы, вероятно, не найдете никого, кто бы дал вам прямой код, потому что то, что вы пытаетесь выполнить, не легко.Удачи.