typedef unsigned int uint32;
typedef unsigned long long uint64;
#define UINT64USE
//#define UINT128USE
const uint32 N = 1000; // max number is ~7131 for 64 bit values ( 18 446 744 073 709 551 616 )
#include <chrono>
#include <string>
#include <vector>
#include <iostream>
#include <stdlib.h>
typedef unsigned long long mainType;
typedef std::chrono::high_resolution_clock high_resolution_clock;
typedef std::chrono::milliseconds milliseconds;
// Array of powers
mainType powers[N];
mainType p5(mainType x)
{
return x * x * x * x * x;
}
milliseconds duration_cast_ms(high_resolution_clock::time_point minus)
{
return std::chrono::duration_cast<milliseconds>(high_resolution_clock::now() - minus);
}
void clearLine()
{
for (int i = 0; i < 77; ++i)
{
std::cout << " ";
}
std::cout << "\r";
}
int main()
{
high_resolution_clock::time_point _start = high_resolution_clock::now();
milliseconds speedTime;
std::vector<uint32> foundItems;
std::cout << "Building table of powers 1 - " << N << "^5\n";
uint32 mpow = 0;
for (uint32 i = 1; i < N; ++i)
{
powers[i] = p5(i);
}
speedTime = duration_cast_ms( _start );
std::cout << "Table ready. Building time: " << ((double)speedTime.count() / 1000 ) << "s, starting search...\n\n";
uint64 counter = 1, speed = 0, hitsspeed = 0;
uint32 foundVal = 0, nextIndex = 0;
mainType sum = 0U, baseSum = 0U;
uint32 lastRangeIndex = 5;
uint32 ix0 = 0x01;
uint32 ix1 = 0x01;
uint32 ix2 = 0x01;
uint32 ix3 = 0x01;
uint32 fVal;
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];
/* 128 only
nextIndex = sum.GetL();
if (((nextIndex & 0xF) > 0) && ((nextIndex & 0x1) == 0))
{
// filter odd values
continue;
}
*/
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;
}
}
// displaying some progress
counter++;
if ((counter & 0xFFFFFFF) == 0)
{
clearLine();
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 << "\r";
}
}
}
}
}
clearLine();
milliseconds time = duration_cast_ms(_start);
std::cout << "\nDone in: " << ( double(time.count()) / 1000 ) << "s\n" << "Total iterations: " << counter << "\n";
speed = counter / (uint64)time.count();
std::cout << "cnt/ms: " << speed << " itr/ms \n";
getchar();
return 0;
}