java - Java 中的 Eratosthenes 筛法 : A Puzzle and some optimization

Question

我用 Java 快速实现了 SoE 算法(代码在最后)。我的双核 AMD 处理器的输出是:

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

• The "Meat" section consumes the Maximum amount of time, as expected.

• One observation I had was that using Math.pow(variable, 2) is slower than (variable * variable). I think other than the function jump, there might be other overheads.

• Does Math.pow(x, 2) have optimizations for powers of 2, 3 etc? I ask because there are some user contributed Java libraries out there with much faster multiplication algos than Java's native ones.

Here are my questions:

• What arithmetic optimizations can you suggest to the Meat section? Is there any way I can avoid the modulus operator altogether?

• The function does not work when start == end. If I do sieve(4, 4), the returned array is of length 1: [4]. What am I doing wrong? It should return [] (basically new int(0)).

• What are some of the fast number/maths related Java libraries you know?

Thanks for reading. Finally Here's the code I wrote: Not GangOfFour/TopCoder quality, but not too pathetic either (I hope!, and code formatting at SO is sort of....weird?):

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) 的情况)。