Сито Эратосфена в Java: головоломка и некоторая оптимизация

Question

Я сделал быструю реализацию алгоритма SoE в Java (код в конце). Выходной сигнал моего двухъядерного процессора AMD:

Allocation:      31
Meat:            10140
Listing:         10171
Preparing end:   10187

• Раздел «Мясо» потребляет максимальное количество времени, как и ожидалось.

• Одно наблюдение, которое я имел, было то, что использование Math.pow(variable, 2) медленнее, чем (variable * variable). Я думаю, что кроме функции jump, могут быть и другие издержки.

• Есть ли в Math.pow (x, 2) оптимизации для степеней 2, 3 и т. Д.? Я спрашиваю, потому что есть некоторые пользовательские библиотеки Java с гораздо более быстрыми алгоритмами умножения, чем нативные.

Вот мои вопросы:

• Какие арифметические оптимизации вы можете предложить разделу «Мясо»? Можно ли вообще избежать оператора модуля?

• Функция не работает, когда start == end. Если я делаю sieve (4, 4), возвращаемый массив имеет длину 1: [4]. Что я делаю неправильно? Он должен вернуть [] (в основном новый int (0)).

• Какие из быстрых библиотек Java, связанных с цифрами и математикой, вам известны?

Спасибо за чтение. Наконец, вот код, который я написал: не GangOfFour / TopCoder, но и не слишком пафосно (надеюсь!, А форматирование кода в SO - что-то вроде ... странно?):

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class Sieve {

    public static void main(String[] args) {

        /* small test */
        int[] primes = sieve(1, 1000000);
    }

    /**
     * returns an array of prime integers
     * in the given range
     * 
     * @param start     range start
     * @param end       range end
     * @return
     */
    private static int[] sieve(int start, int end) {

        long startTime = System.currentTimeMillis();

        /* some basic range checks */
        if(end < start || start < 1 || end  < 1) {
            throw new ArithmeticException("Messed up input");
        }

        /* generate ints within range */
        int[] naturals = new int[end-start+1];
        for (int j = 0; j < end - start + 1; j++) {
            naturals[j] = start + j;
        }
        System.out.println("Allocation: \t" + (System.currentTimeMillis() - startTime));

        /* init running prime to start, and increment until
         * running prime squared is greater than the end
         */
        for (int runningPrime = (start == 1 ? 2: start); end > runningPrime*runningPrime; runningPrime++) {
            for (int i = runningPrime; i < naturals.length; i++) {
                if(-1 != naturals[i]) {
                    if(naturals[i] % runningPrime == 0) {
                        naturals[i] = -1;
                    }
                }
            }
        }
        System.out.println("Meat: \t\t" + (System.currentTimeMillis() - startTime));

        if(naturals[0] == 1) {
            naturals[0] = -1;
        }

        /* list primes */
        List list = new ArrayList();
        for (int i = 0; i < naturals.length; i++) {
            if(-1 != naturals[i])
                list.add(naturals[i]);
        }
        System.out.println("Listing: \t" + (System.currentTimeMillis() - startTime));

        /* create the return int array */
        int[] primes = new int[list.size()];
        int k = 0;
        for (Iterator iterator = list.iterator(); iterator.hasNext();) {
            primes[k++] = ((Integer) iterator.next()).intValue();
        }

        System.out.println("Preparing end: \t" + (System.currentTimeMillis() - startTime));
        return primes;
    }
}

Спасибо за все отзывы. Ниже приведена исправленная версия (пока кому-то не удастся снова ее сломать:)

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class Sieve {
    public static void main(String[] args) {
        /* small test */
        int[] primes = sieve(2, 5);
        System.out.println("Number of primes: " + primes.length);
        for (int i : primes) {
            System.out.println(i);
        }
    }

/**
 * returns an array of prime integers
 * in the given range
 * 
 * @param start     range start
 * @param end       range end
 * @return
 */
private static int[] sieve(int start, int end) {

    long startTime = System.currentTimeMillis();

    /* some basic range checks */
    if(end < start || start < 1 || end  < 1) {
        throw new ArithmeticException("Messed up input");
    }

    /* generate ints within range */
    int[] naturals = new int[(int)Math.floor((end-start+1) / 2) + 1];
    int allocator = 0;
    for (int j = 0; j < end - start + 1; j++) {
        if(!((start + j) % 2 == 0)) {
            naturals[allocator++] = start + j;
        }
    }
    System.out.println("Allocation: \t" + (System.currentTimeMillis() - startTime));

    /* init running prime to 2, and increment until
     * running prime squared is greater than the end
     */
    for (int runningPrime = 2; end >= runningPrime*runningPrime; runningPrime++) {
        for (int i = 0; i < naturals.length; i++) {
            if(-1 != naturals[i]) {
                if(naturals[i] != runningPrime && naturals[i] % runningPrime == 0) {
                    naturals[i] = -1;
                }
            }
        }
    }
    System.out.println("Meat: \t\t" + (System.currentTimeMillis() - startTime));

    if(naturals[0] == 1) {
        naturals[0] = -1;
    }

    /* list primes */
    List list = new ArrayList();
    for (int i = 0; i < naturals.length; i++) {
        if(-1 != naturals[i])
            list.add(naturals[i]);
    }
    System.out.println("Listing: \t" + (System.currentTimeMillis() - startTime));

    /* create the return int array */
    int size = list.size();
    int k = 0;

    /* tricky tricky :) */
    if(start <= 2) {
        size += 1;
        k = 1;
    }

    int[] primes = new int[size];

    if(start <= 2) {
        primes[0] = 2;
    }

    for (Iterator iterator = list.iterator(); iterator.hasNext();) {
        primes[k++] = ((Integer) iterator.next()).intValue();
    }

    System.out.println("Preparing end: \t" + (System.currentTimeMillis() - startTime));
    return primes;
    }
}

Answer 1

Вы можете избежать по модулю, переписав внутренний цикл:

        for (int i = runningPrime; i < naturals.length; i++) {
            if(-1 != naturals[i]) {
                if(naturals[i] % runningPrime == 0) {
                    naturals[i] = -1;
                }
            }
        }

как

        for (int i = runningPrime; i < naturals.length; i+=runningPrime) {
             naturals[i] = -1;
        }

Я также немного обеспокоен тем, что включение параметра start усложняет ситуацию (учитывая случай sieve(4, 10)).

Answer 2

Ваше решение - , а не Сито Эратосфена. Это очевидно, потому что вы используете оператор modulo в своем коде; Правильное сито Эратосфена использует только сложение во внутренней петле, а не деление или по модулю. Вот простая версия Сита Эратосфена, которая импортирует BitSet и LinkedList из java.util и возвращает LinkedList простых чисел, меньших n :

public static LinkedList sieve(int n)
{
    BitSet b = new BitSet(n);
    LinkedList ps = new LinkedList();

    b.set(0,n);

    for (int p=2; p<n; p++)
    {
        if (b.get(p))
        {
            ps.add(p);
            for (int i=p+p; i<n; i+=p)
            {
                b.clear(i);
            }
        }
    }

    return ps;
}

Основная идея заключается в создании сита (BitSet b ) с каждым элементом, изначально установленным в Prime (представлен в виде установленного бита), итерацией по сито ищет и сообщает о каждом последующем простом числе, и, когда обнаруживается, что оно удаляет все его кратные числа из сита, помечая его Composite (обозначается как очищенный бит). Множители находятся путем сложения, а не деления, и внутренний цикл состоит только из сложения, операции очистки битов, сравнения для поиска конца сита и перехода назад к началу цикла, поэтому очень быстро.

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

Если вы хотите, чтобы простые числа в диапазоне, который не начинался с нуля, вам нужно сегментированное Сито Эратосфена. Я обсуждал сегментированное сито эратосфена ранее на переполнении стека, а также обсуждаю это в моем блоге.

Answer 3

Если я что-то не пропустил, то напишу:

 for(int runningPrime = (start == 1 ? 2: start); end > runningPrime*runningPrime;
 runningPrime++) 

как

int limit = Math.sqrt(end);
for(int runningPrime = (start == 1 ? 2: start); runningPrime < limit; 
runningPrime++) 

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

Answer 4

По моему мнению, прежде чем начать оптимизацию, вы должны исправить две серьезные ошибки.

Я скомпилировал ваш код как программу на Java, а затем попытался вычислить

sieve(1, 9)

и

sieve(4,10);

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

Во втором случае предполагаемые простые числа равны 4, 5, 6, 7, 8, 9.10. Это потому, что вы пропустили просеивание по любому из простых чисел ниже начала диапазона.Боюсь, это слишком оптимизация: -)

Answer 5

Заполнение только коэффициентами (кроме 2), увеличение с помощью runPrime и потеря проверки делимости, как уже предлагалось, являются, вероятно, наиболее важными оптимизациями.

Java Math.pow для парных! У него нет оптимизаций для возведения в квадрат, в основном, потому что он сразу же преобразует 2 в двойное число.