Есть ли более оптимизированный способ сделать простое вычисление в Java?

Question

Я пытаюсь найти способ, чтобы решить эту конкретную проблему быстрее и более оптимизированным способом. Я не знаю, возможно ли запустить этот код на нескольких ядрах и потоках, или я мог бы каким-то образом разгрузить его на GPU, но чем быстрее это сможет вычислить, тем лучше.

public class numberCounter 
{
    public static void main(String[] args) 
    {
        //Used only to check speed of calculation
        long start = System.currentTimeMillis();

        //Initialized variables
        double x, y, z;

        //30 can be substituted out but i used it as a test. 
        //I am unable to calculate 31 and above.
        long t = (long) Math.pow(2, 30);

        //used later for counting
        long counter = 0;

        //starting number
        System.out.println("Number - " + t);

        for(int i = 1; i < t; i++)
        {
            x = i % 2;
            y = i % 3;
            z = i % 5;

            if(x*y*z > 0)
                counter++;
        }

        System.out.println();

        //prints out number of numbers that follow the rule above
        System.out.printf("Numbers: %.0f\n", counter);

        long end = System.currentTimeMillis();

        //prints out time taken
        System.out.println((end - start) + " ms");

    }
}

Answer 1

Самым большим бременем является цикл, поэтому лучше решить его, если мы хотим получить что-то для оптимизации. Вы должны обратить эту проблему вспять, вместо того, чтобы искать числа, неделимые на 2, 3 или 5, мы искали числа, делимые на 2, 3 или 5. Полученное число таких чисел вычитает все числа и даст нам число неделимых. числа на 2 или 3 или 5. Таким образом, мы получаем алгоритм с постоянным временем выполнения. Время выполнения не зависит от ввода.

public static long indivisbleBy_2or3or5(long t) {
    long x, y, z;

    //amount of numbers divisible by 2, and several for 3 and 5. 
    x = t / 2;

    //amount of numbers divisible by 3 - numbers divisible by 3 and 2 = amount of numbers divisible by 3, and several for 5.
    y = t / 3;
    y = y - y / 2;

    //amount of numbers divisible by 5 - numbers divisible by 5 and 2 - (numbers divisible by 5 and 3 - numbers divisible by 5 and 3 and 2)  = number only divisible by 5  
    z = t / 5;
    z = z - z / 2 - (z / 3 - z / (2 * 3) );

    //All numbers - (The amount of numbers divisible by 2, and several for 3 and 5 
    //+ The amount of numbers divisible by 3 and several for 5 + number only divisible by 5)
    //= indivisible by 2 or 3 or 5
    return t - (x + y + z);
}

Я не знаю, есть ли у "pow" какая-то оптимизация, но обычно лучше выполнить действие (2 ^ 15) ^ 2, которое дает 15 операций, чем 2 ^ 30, что дает 29 операций. По принципу "разделяй и властвуй".:)