Причина сравнения длиннее медленнее, чем сравнение двойной

Question

Я написал небольшую программу для вычисления первых 18 троек (x,y,z) с x<y<z, которые удовлетворяют x^3+y^3=z^3+1.

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

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

Вот мой код:

class Threes {
  public static void main(String[] args) {
    System.out.println("Threes --- Java");
    int Z_MAX = 60000, Y_MAX = Z_MAX-1, X_MAX = Y_MAX-1;
    double[] powers = new double[Z_MAX+1];
    for (int i = 0; i <= Z_MAX; i++) {
      powers[i] = Math.pow(i, 3);
    }
    System.out.println("Powers calculated");
    int x, y, z;
    double right, left;
    int[][] sets = new int[18][3];
    int foundCount = 0;
    long loopCount = 0;
    long start, end;
    start = System.currentTimeMillis();

    for (x = 1 ; x < X_MAX; x++) {
      for (y = x + 1; y < Y_MAX; y++) {
        right = powers[x] + powers[y];
        for (z = y + 1; z < Z_MAX; z++) {
          left = powers[z] + 1;
          if (right < left) {
            z = Z_MAX;
          } else if (right == left) {
            sets[foundCount][0] = x;
            sets[foundCount][1] = y;
            sets[foundCount][2] = z;
            foundCount++;
            end = System.currentTimeMillis();
            System.out.println("found " + foundCount + ". set:\t" + x + "\t" + y + "\t" + z + "\t" + ((end - start) / 1000.0));
            if (foundCount == 18) {
              x = X_MAX;
              y = Y_MAX;
              z = Z_MAX;
            }
          }
          loopCount++;
        }
      }
    }
    System.out.println("finished: " + loopCount);
  }
}

Я изменил следующие строки:

double[] powers = new double[Z_MAX+1];

становится

long[] powers = new long[Z_MAX+1];

и

powers[i] = Math.pow(i, 3);

становится

powers[i] = (long)Math.pow(i, 3);

и

double right, left;

становится

long right, left;

---

«Бонусный вопрос» : Какие еще возможности оптимизации всего кода с точки зрения общего времени выполненияДолжен ли я?Я знаю, что пропуск 1038 дает мне несколько миллисекунд.Я уверен, что мне нужно значительно сократить количество итераций цикла.Но как?

Answer 1

Если вы используете 32-битную операционную систему, производительность long-variable может быть хуже, поскольку long - это 64-битный тип.Например, в 64-битной ОС Java может выполнять сравнение только с одной машинной инструкцией, но в 32-битной среде она должна использовать несколько машинных инструкций, поскольку она может обрабатывать только 32-битную в то время.

Но для double это не обязательно, так как 32-разрядные системы имеют машинные инструкции для 64-разрядных чисел с плавающей запятой, даже если их нет для 64-разрядных целых чисел.

Кроме того, с кодом:

powers[i] = (long)Math.pow(i, 3);

есть два ненужных преобразования: сначала i (целое число) преобразуется в double (это то, что принимает Math.pow), а затем возвращаемое значение преобразуется обратно в 64-битное целое (длинное).

Answer 2

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

for (z = y + 1; z < Z_MAX; z++) {
    left = powers[z] + 1;
     if (right < left) {
        z = Z_MAX;
     }

И большую часть времени он всегда будет выводить одну и ту же ветку из условного. Поэтому, когда ваш код достигнет стационарного состояния (т. Е. После установки предиктора ветвления ЦП), во время выполнения будут доминировать сами вычисления: зависимости минимизируются, поэтому задержка конвейера команд не имеет значения.

На 32-разрядной машине для сложения и сравнения 64-разрядных целочисленных типов требуется больше инструкций, чем для double с. Для расчета double потребуется больше циклов, но это не имеет значения. У нас преобладает пропускная способность, а не задержка. Таким образом, общее время выполнения будет больше.

С точки зрения дальнейшей оптимизации, вы можете переместить +1 за пределы внутреннего цикла, вычислив right = powers[x] + powers[y] - 1. Но, возможно, оптимизатор уже заметил это.

Answer 3

Ваша самая большая «бонусная» оптимизация будет состоять в том, чтобы заменить цикл z на вычисления типа:

z = Math.round(Math.pow(left - 1, 1./3));

и проверить, если z > y && left == powers[(int)z] + 1.

Другие улучшения, если вы хотеличтобы найти все тройки в ваших пределах:

• начать x в 2 вместо 1
• заменить z = Z_MAX; на break;, чтобы досрочно выйти из цикла
• вычислить X_MAX как Math.pow((powers[Z_MAX] + 1)/2, 1./3) ~ = Z_MAX * Math.pow(0.5, 1./3), поскольку, если x больше этого значения, z будет превышать Z_MAX
• , повторно вычислять Y_MAX для каждого x как Math.pow(powers[Z_MAX] - powers[x] + 1, 1./3)/2

Кстати, более распространенный способ упорядочить тройки - использовать z в качестве первичного ключа сортировки, что может привести к тому, что первые 18 будут отличаться от тех, которые вы получили вначале по x.Чтобы изменить это, вы должны сделать внешний цикл итерацией по z, что в любом случае будет проще:

for (z = 1; z < Z_MAX; z++) {
    for (y = 1; y < z - 1; y++) {
       zy = powers[z] - 1 - powers[y];
       x = Math.round(Math.pow(zy, 1./3));
       if (x < y && zy == powers[(int)x])
           ...report triple found;
    }
}