Как проводить параллельную факторизацию? - PullRequest
Новая
       5

Как проводить параллельную факторизацию?

5 голосов
/ 26 июня 2011

Следующий фрагмент кода вычисляет простые множители заданного числа: 

public static LinkedList<Long> getPrimeFactors(Long number) {
    LinkedList<Long> primeFactors = new LinkedList<Long>();

    for (Long factor = Long.valueOf(2); factor <= number / factor; factor++) {
        if (number % factor == 0) {
            primeFactors.add(factor);
            while (number % factor == 0) {                  
                number /= factor;
            }
        }           
    }

    if (number > 1) {
        primeFactors.add(number);
    }

    return primeFactors;
}

Для вычисления простых множителей 9223372036854775783 требуется 140937 мс (это последнее простое число меньше Long.MAX_VALUE).Есть ли способ реализовать эту факторизацию с помощью параллелизма, т. Е. Используя ExecutorService?

Edit: 

public static void getPrimeFactors(Long number) {
    LinkedList<Long> primeFactors = new LinkedList<Long>();

    if (number % 2 == 0) {
        primeFactors.add(2L);

        while (number % 2 == 0) {
            number /= 2;
        }
    }

    long limit = (long) Math.sqrt(number) + 1;

    ExecutorService service = Executors.newFixedThreadPool(2);
    LinkedList<Future<LinkedList<Long>>> futures = new LinkedList<Future<LinkedList<Long>>>();
    futures.add(service.submit(new PrimeFactor(3, limit / 2, number)));
    futures.add(service.submit(new PrimeFactor(1 + limit / 2, limit, number)));

    for (Future<LinkedList<Long>> future : futures) {
        try {
            primeFactors.addAll(future.get());
        } catch (InterruptedException e) {
            e.printStackTrace();
        } catch (ExecutionException e) {
            e.printStackTrace();
        }
    }
    service.shutdown();

    if(number>1) {
        primeFactors.add(number);           
    }

    System.out.println(primeFactors);
}

private static class PrimeFactor implements Callable<LinkedList<Long>> {
    private long lowerLimit;
    private long upperLimit;
    private Long number;

    public PrimeFactor(long lowerLimit, long upperLimit, Long number) {
        this.lowerLimit = lowerLimit;
        this.upperLimit = upperLimit;
        this.number = number;
    }

    public LinkedList<Long> call() throws Exception {
        LinkedList<Long> primeFactors = new LinkedList<Long>();
        for (long i = lowerLimit; i < upperLimit; i += 2) {
            if (number % i == 0) {
                primeFactors.add(i);
                while (number % 2 == 0) {
                    number /= i;
                }
            }
        }
        return primeFactors;
    }

}

2nd Edit: 

public static LinkedList<Long> getPrimeFactorsByFastGeneralMethod(long number) {
    LinkedList<Long> primeFactors = new LinkedList<Long>();

    if (number % 2 == 0) {
        primeFactors.add(2L);

        while (number % 2 == 0) {
            number /= 2;
        }
    }

    long limit = (long) Math.sqrt(number);

    for (long factor = 3; factor <= limit; factor += 2) {
        if (number % factor == 0) {
            primeFactors.add(factor);
            while (number % factor == 0) {
                number /= factor;
            }
        }
    }

    if (number > 1) {
        primeFactors.add(number);
    }

    return primeFactors;
}

Теперь фрагмент кода: 

    LinkedList<Long> primeFactors = Factorization.getPrimeFactorsByConcurrentGeneralMethod(600851475143L);
    System.out.println("Result: " + primeFactors.get(primeFactors.size() - 1));

    primeFactors = Factorization.getPrimeFactorsByFastGeneralMethod(600851475143L);
    System.out.println("Result: " + primeFactors.get(primeFactors.size() - 1));

дает вывод: 

Result: 600851475143
Result: 6857

Примечание: имя класса Factorization, и я изменил имя метода getPrimeFactors на getPrimeFactorsByConcurrentGeneralMethod

Ответы [ 3 ]

6 голосов
/ 26 июня 2011

Э-э, прежде чем вы начнете думать о параллельных реализациях, я бы предложил немного оптимизировать алгоритм.Помимо 2 каждое простое число нечетное, поэтому сделайте 2 специальным случаем, а затем начните с 3 с вашего цикла и увеличьте коэффициент на 2. Затем вместо вычисления числа / фактора каждый конец цикла (что также делает оптимизацию для JIT более сложной, я думаю) просто вычислите Sqrt (N) один раз - ведь мы знаем, что у каждого числа может быть только один простой множитель> sqrt (N);)

Если бы вы сделали это, я бы изменил сигнатуру вашего метода так, чтобыВы не всегда начинаете с 3 и работаете до Sqrt (N), но задаете начальный и конечный диапазоны.Простейшим решением было бы разделить диапазон от 3-Sqrt (N) на K частей, где K - количество доступных ядер (так как это не очень сбалансировано, использование меньших частей может дать вам лучшую балансировку нагрузки) и бросить это впалач службы.Затем вам нужно просто собрать все результаты и создать один список из всех меньших списков.

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

PS: обратите внимание, что ваш алгоритм разделения диапазона по-прежнему должен правильно обрабатывать случаи 2 и sqrt (n).

PPS: И я надеюсь, что вы знаете, чтоэта проблема в NP, и вы делаете это только для того, чтобы немного узнать о параллелизме.

1 голос
/ 26 июня 2011

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

Вы можете использовать Метод факторизации эллиптической кривой (ECM) .Он хорошо подходит для параллельных вычислений.Но сам метод не тривиален - несколько тысяч строк кода.Источники доступны например здесь

0 голосов
/ 26 июня 2011

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

  1. Избегайте ненужных автобокс, как уже упоминал Кристиан Семрау в своем комментарии.
  2. Создайте ярлык для «простого» случая, напримерВы перебираете каждое число от 2 до число / 2.Это не нужно, так как 2 - единственный четный фактор.В лучшем случае вы сэкономите половину количества итераций с помощью этого ярлыка.
  3. Вам не нужно вычислять простые множители number, достаточно sqrt(number).

  4. Существуют более эффективные способы Целочисленная факторизация 

    public static List<Long> getPrimeFactors(long number) {
    List<Long> primeFactors = new ArrayList<Long>();

    // Only process natural numbers
    if(number < 1l) {
        return primeFactors;
    }

    // The only prime factor of 1 is 1
    if(number == 1l) {
        primeFactors.add(1l);
        return primeFactors;
    }

    // Even have the prime factor 2
    if(number % 2l == 0l) {
        primeFactors.add(2l);

        while(number % 2l == 0l) {
            number /= 2l;
        }
    }

    // Iterate from 3 to sqrt(number) to calculate the remaining prime factors
    for (long factor = 3l; factor < Math.sqrt(number); factor+=2l) {
        if (number % factor == 0) {
            primeFactors.add(factor);
            while (number % factor == 0) {                  
                number /= factor;
            }
        }           
    }

    if (number > 1) {
        primeFactors.add(number);
    }

    return primeFactors;
}
...