Алгоритм вычисления полуцелых целых чисел, отсутствие эффективности

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

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

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

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

В любом случае, это мой код (написанный на Java), который будет возвращать логическое значение, указывающее, является ли число полусовершенным:

/**
 * 
 * @param x
 *          a number to test if it is semiperfect or not.
 * @param list
 *          this is a array of the factors of x (e.g factors of 6 are 3, 2, 1 excluding itself).
 * @return true if x is semiperfect, false otherwise.
 */
public static boolean isSemiPerfect(int x, List<Integer> list) {
    if (x == 0)
        return true;
    for (int i = 0; i < list.size(); i++) {
        int temp = list.remove(i);
        if (isSemiPerfect(x - temp, list)) // using recursion
            return true;
        list.add(i, temp);
    }

    return false;
}

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

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

Поэтому, если число, о котором идет речь (x), не превышает 1,8 * 10 19 , каждое нечетное число не нужно проверять, если оно полусовершенно или нет, потому что каждое странное число ниже этого четный.

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

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

11 голосов | спросил Linus 29 J000000Tuesday14 2014, 02:41:04

3 ответа


3

Как указано в @vnp, не известно эффективного эффективного (то есть полиномиально-временного) решения проблемы сумм подмножества. Тем не менее, ваш код может запускаться быстрее, но сначала я хочу обратиться к нескольким пунктам.

  

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

Предположим, я сказал, что у меня был быстрый способ определить, является ли число not полусовершенным; быстрее, чем наилучший способ определить, является ли число полусовершенным. Откуда вы знаете, что я был неправ? Даже не глядя на мой код?

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

public static boolean isSemiPerfect(int n) {
  if (isNotSemiPerfect(n)) {
    return false;
  }
  return true;
}

Итак, вы видите, что проблемы так же сложны, как и другие.

  

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

Полу-совершенство (это слово?) определяется только для положительных целых чисел; бесконечность не является целым числом.

Теперь о коде. Удаление и вставка в код List ужасно неэффективна. То, что мы хотим, - это способ перечислить разные суммы собственных дивизоров \ $ 2 ^ k \ $, где \ $ k \ $ - число собственных делителей.

Вот способ сделать это, который использует BigInteger как счетчик. Допустим, что диапазон счетчиков превышает \ $ [0, 2 ^ k) \ $, и на каждом шаге добавьте делитель \ $ j \ $ th к сумме, если установлен бит \ $ j \ $ th счетчика.

public static boolean isSemiPerfect(int n, List<Integer> divisors) {
  BigInteger combinations = BigInteger.valueOf(2).pow(divisors.size());
  for (BigInteger i = BigInteger.ZERO; i.compareTo(combinations) < 0; i = i.add(BigInteger.ONE)) {
    int sum = 0;
    for (int j = 0; j < i.bitLength(); j++) {
      sum += i.testBit(j) ? divisors.get(j) : 0;
    }

    if (sum == n) {
      return true;
    }
  }

  return false;
}

Я проверил тест на полусовершенные числа до 500. На моей машине этот метод занимает время выполнения от ~ 25 с до ~ 0,9 с.

На практике вы можете использовать int вместо BigInteger для вашего счетчика, так как если число содержит более 32 собственных делителей, вы будете ждать долгое время.

ответил mjolka 1 AM000000100000002731 2014, 10:03:27
7

Забавно, что я работал над той же проблемой. Моя проблема с производительностью - это не Semi-Perfect часть, а проверка обилия.

Вы можете вызвать эту функцию (C #), чтобы проверить, что число SemiPerfect.

static bool IsSemiPerfect(BigInteger delta, BigInteger[] d, BigInteger[] dSum, int index, BigInteger sum)
{
    if (sum == delta)
        return true;

    if (index >= d.Length || sum > delta || delta > (dSum[index] + sum))
        return false;

    for (int i = index; i < d.Length; i++)
    {
        if (IsSemiPerfect(delta, d, dSum, i + 1, sum + d[i]))
            return true;
    }

    return false;
}

Параметры следующие:

  • delta: сумма делителей - n
  • d: divisors, сортировка по убыванию!
  • dSum: кешированный расчет оставшейся суммы

BigInteger[] dSum = new BigInteger[d.Length];
for (int i = d.Length - 1; i > -1; i--)
{
    BigInteger sum = 0;
    for (int j = divsIndex - 1; j >= i; j--)
        sum += d[j];
    dSum[i] = sum;
}
  • index: 0, используется для рекурсии
  • sum: 0, используется для рекурсии

Код работает намного быстрее по сравнению с другим ответом из-за трех основных сокращений в дереве поиска и немного другого подхода к проблеме. Он также оптимизирован для поиска ответа прогрессивным способом.

Проверка большого N = 190000006875 с 119 делителями проходит значительно ниже 1 секунды. Я не делал реального профилирования, но мое узкое место в производительности действительно где-то в другом месте. Это может быть NP, но очень хорошо выполняется таким образом.

Кажется, что отправка ответа в коде C # на тему Java - это немного плохое поведение. Чтобы сделать это, я дам немного не по теме, но классный код, чтобы найти действительно большие записи, разбивающие странные цифры на Java, используя алгоритм Сидни Кравица.

public static BigInteger getPossibleWeirdNumber(int bits)
{
    BigInteger q = BigInteger.probablePrime(bits, new Random());
    int k = q.bitLength() - 1;
    BigInteger power2k = BigInteger.valueOf(2).pow(k);
    BigInteger r = ((power2k.multiply(q)).subtract(q.add(BigInteger.ONE))).divide(q.add(BigInteger.ONE).subtract(power2k));
    if(r.compareTo(power2k) > 0)
    {
        if(r.isProbablePrime(1000000) && q.isProbablePrime(1000000)) //Some final checking on primes
        {
            BigInteger weirdNumber = (BigInteger.valueOf(2).pow(k-1)).multiply(q).multiply(r);
            return weirdNumber;
        }
    }
    return null;
}

public static BigInteger getWeirdNumber(int bits)
{
    BigInteger r = getPossibleWeirdNumber(bits);
    while(r == null)
        r = getPossibleWeirdNumber(bits);

    return r;
}

Единственная проблема заключается в том, что этот алгоритм не находит странных странных чисел. Легко понять, почему: \ $ 2 ^ {k-1} \ $ всегда будет четным числом. Умножение четным числом всегда приводит к четному числу, поэтому трюк Сидни Кравица поможет вам найти большие странные числа, но нечетные. Вот почему я вручную начал искать.

Кстати, причина, по которой я использовал C #, - это более чистый вид кода при использовании BigInteger. Перегрузка оператора в .Net прекрасна.

ответил Nipokkio 6 PM00000050000002331 2014, 17:11:23
5

У меня плохие новости. Из опубликованной вами ссылки

  

Идентификация псевдомерных номеров поэтому эквивалентна решению   проблема суммы подмножества.

и в статье суммы подмножества указано, что

  

Задаваемая сумма задачи NP-полная.

Поэтому я не ожидал бы действительно эффективного решения.

ответил vnp 29 J000000Tuesday14 2014, 03:11:19

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132