Основной алгоритм оптимизации

Мое текущее задание — создать базовый алгоритм, который находит магическое число (1). Магическое число можно найти, разделив четное число на 2, пока оно не станет магическим, или умножив нечетное число на 3, добавив 1, разделив на 2 до 1. Мы должны сделать это для каждого натурального числа от 3 до 5 млрд. ,

MAGIC = 1;

DIV = 2;

START = 3;

MAX = 5000000000;

bool isOdd(int x);
void isMagic(int x);

int main () {

clock_t startTime = clock();
cout << "Beginning loop" << endl;

for (int i = START; i < MAX; i++)
{

if ( isOdd(i) == false )
isMagic(i);
else if ( isOdd(i) == true )
isMagic(i);

}

clock_t finishTime = clock();
cout << "Looping took " << double(finishTime - startTime) / CLOCKS_PER_SEC << " seconds" << endl;

return 0;
}bool isOdd(int x) {

if( x % DIV == 0 )
return false;
else
return true;

}

void isMagic(int x) {

if( isOdd(x) == false ) //Is even
{

while( x > MAGIC )
{
x /= DIV;
};

}
else if( isOdd(x) == true ) //Is odd
{

while( x > MAGIC )
{

x *= START;
x += MAGIC;
x /= DIV;

};

}

return;
}

Это работает, однако, это довольно медленно. Даже с -o3 флаг в моем makefile выполнение задачи занимает около 115 секунд. Мой профессор заявил, что приличное время будет ~ 60 секунд. Как бы я мог оптимизировать это?

-3

Решение

Я думаю, что вы неправильно поняли назначение.
«Либо деление четного числа на 2, пока оно не станет волшебным, либо умножение нечетного числа на 3 и добавление 1» должно быть реализовано как

while( x > 1 )
{
if( isEven(x) )
{
x /= 2;
}
else
{
x *= 3;
x += 1;
}
}

Предполагая действительность Гипотеза Коллатца, это может быть дополнительно оптимизировано как

x = 1;
4

Другие решения

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

 while( x > MAGIC )
{

x *= START;
x += MAGIC;
x /= DIV;

};

когда x равен 3 или больше, вы получаете бесконечный цикл, и поэтому он работает «медленно». Правильный код будет:

MAGIC = 1;

DIV = 2;

START = 3;

void isMagic(int x) {
while (x != MAGIC){
if(isOdd(x)){
x *= START;
x++;
} else {
x /= DIV;
}
}
}

Обратите внимание, что isOdd (x) возвращает логическое значение, поэтому нет необходимости в == true

0

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

Пример: при запуске isMagic(1742), вы можете запустить цикл для 179 или около того итераций — или признать, что вы уже решили isMagic(871) и закончите проверку на второй итерации.

И когда вы решаете isMagic(871), вы должны не просто записать, что вы решили 871, вы должны записать все числа, с которыми вы столкнетесь при его решении, это будет 2614 1307 3922 1961 5884 2942 1471 4414 2207 6622 3311 9934 4967 14902 7451 22354 11177 33532 16766 8383 25150 12575 37726 18863 56590 28295 84886 42443 127330 63665 190996 95498 47164 1432 на 8498 47164 1432 на 8488 471649 — то есть много чисел, которые больше чем оригинал 871. Найти способ достичь этого — суть вашего задания.

Как примечание стороны, void isMagic(int x) довольно странный подпись функции. Обычно имя как isXYZ(...) предлагает предикат, то есть функцию, которая возвращает логическое значение. void Функция без побочных эффектов может быть оптимизирована до void isMagic(int){},

0