К вопросу о «потерянном времени»

[crea7or]

Переборов меньше на 1млрд. (время -50%)

	for (ix0 = 1; ix0 < N; ++ix0)
	{
		for (ix1 = 1; ix1 < ix0; ++ix1)
		{
			for (ix2 = 1; ix2 < ix1; ++ix2)
			{
				baseSum = powers[ix2] + powers[ix1] + powers[ix0];
				while (lastRangeIndex > 0 && powers[lastRangeIndex] > baseSum)
				{
					--lastRangeIndex;
				};
				for (ix3 = 1; ix3 < ix2; ++ix3)
				{
					fVal = (ix3 + ix2 + ix1 + ix0 - lastRangeIndex) % 30;
					if ( fVal )
					{
						ix3 += 30 - fVal;
					}
					if (ix3 >= ix2)
					{
						break;
					}
					sum = baseSum + powers[ix3];
					while (lastRangeIndex < (N - 1) && powers[lastRangeIndex] < sum)
					{
						++lastRangeIndex;
					};
					if (lastRangeIndex == (N - 1))
					{
						break;
					}
					foundVal = sum == powers[lastRangeIndex] ? lastRangeIndex : 0;
					if (foundVal > 0)
					{
						// clear line
						clearLine();
						for (auto ind : foundItems)
						{
							if ((foundVal % ind) == 0)
							{
								// duplicate
								//foundVal = 0;
								break;
							}
						}
						if (foundVal != 0)
						{
							std::cout << "found: ";
							std::cout << ix0 << "^5 ";
							std::cout << ix1 << "^5 ";
							std::cout << ix2 << "^5 ";
							std::cout << ix3 << "^5 ";
							speedTime = duration_cast_ms(_start);
							// it/ms: iterations per millisecond, it: total iterations, spd:
							std::cout << "it/ms: " << (counter / (uint64)speedTime.count()) << " it: " << counter << "\n";
						}
						else
						{
							std::cout << "duplicate";
						}
					}
					else
					{
						if (( 30 + ix3) >= ix2)
						{
							break;
						}
					}
					counter++;
				}
			}
		}
	}

[GarryC]

Хм, я выводил время полного перебора, а у Вас после нахождения выводится?
И тут весь код? Я что то не вижу объявления LastRangeIndex.

[crea7or]

Вот тут весь, я только идею хотел показать.

[GarryC]

Ну я идею не очень понял, лучше бы словами )
И насчет времени — когда у Вас выводится — в конце или при нахождении?

[crea7or]

Не, я другим интересовался. Вот со временем (i5 3.5GHz). Суть в вычислении модуля 30 и переходов только по этим значениям. Вот тут есть код самый быстрый (с предрасчётом разниц значений). С модулем 30 второй по скорости (я его маленько ещё ускорил).

Building table of powers 1 — 1000^5
Table ready. Building time: 0.001s, starting search…

found: 133^5 110^5 84^5 27^5 time: 0.007 it: 253739
found: 266^5 220^5 168^5 54^5 time: 0.053 it: 6350001
found: 399^5 330^5 252^5 81^5 time: 0.249 it: 36244461
found: 532^5 440^5 336^5 108^5 time: 0.778 it: 121110577
found: 665^5 550^5 420^5 135^5 time: 1.894 it: 305357953
found: 798^5 660^5 504^5 162^5 time: 3.937 it: 646553812

Done in: 7.177s
Total iterations: 1196060398
cnt/ms: 166651 itr/ms

[Deosis]

Судя по предложениям, дальше ускорить можно только с помощью математики.
Есть где-нибудь список идей для уменьшения перебора и результат их применения (даже если неудачен)?
Например, если нам не нужны кратные, то

• Среди чисел, как минимум 2 нечетных
• Для любого простого: Среди чисел, как минимум 2 не делящихся на него.

[crea7or]

Если именно для переборов я кроме как на розеттакоде ничего не видел. Если найти формулу вычисления типа той, которой и нашли первое значение — вот тогда задача будет закрыта.

[GarryC]

Насчет формул не уверен — формула утверждает, что набор чисел, отвечающий определенным правилам конструирования, обладает определенными свойствами, но ничего не говорит о существовании других наборов, отличных от сконструированных, так что остается простор для поиска.

[LaRN]

При расчете степени можно сэкономить на одном умножении:
Pow5[i]=(rez_t)i*(rez_t)i;
Pow5[i]=Pow5[i]*Pow5[i]*(rez_t)i;

[GarryC]

Разумеется, можно, я не проверял, но компилятор должен свернуть сам.

[sergey-b]

Скажите, а почему вы начинаете очередную итерацию от i3 = i4-1 и i2 = i3-1? Они разве не могут быть равны?

[GarryC]

Да, конечно, не могут, я забыл указать, что это условие задачи.