Как сократить время выполнения программы [C++]?

Question

[LanternOfDarkness]

Здравствуйте. Помогите сократить время работы программы на ~0.014 секунды.

#include <iostream>
#include <math.h>
using namespace std;
int main()
{
  int n,S,c;
   cin >> n;
   for(long i=1; i<=n; i++)
   {
       c = pow(i,0.5);
       if(i==1)
       {S=4;}
       else if(i==c*c+1||i==c*c+c+1)
       {S+=3;}
       else{S+=2;}
   }
   cout << S << "\n";
return 0;
}

Условие: Необходимо посчитать минимальное количество сторон квадрата при заданном количестве квадратов n(1<=n<=10^9). При этом квадратом считаются только квадраты со стороной 1. Выполняться должно меньше 1 секунды.

Answer 1

[DancingOnWater]

Во-первых.
Вместо
с = pow(i, 0.5) используйтес= sqrt(i);
Во-вторых, закешируйте выражение с*с. Операция умножения дорогая.
В-третьих, у вас первый if работает только на первой итерации, в топку его, начинайте итерации с 2.
В-четветрых, если есть возможность, то надо использовать OpenMP, а еще лучше OpenCL

Это что касается техники программирования. Но мне кажется, что если покопать математику,. то можно изменить алгоритм.
О как, после переоформления вопроса я увидел саму задачу. Тогда однозначно стоит начинать перебор
с s*s, гдеint s =sqrt(n);

Answer 2

[Дмитрий Скрыльников]

можно попробовать заменить if на чтонибудь другое. например switch

Answer 3

[jcmvbkbc]

Помогите сократить время работы программы на ~0.014 секунды.

Запускайте её с меньшим n.
А если серьёзно, то начните с начала -- что вы хотели посчитать?

Comments

[LanternOfDarkness]

Необходимо посчитать минимальное количество сторон квадрата при заданном их количестве n(1<=n<=10^9). При этом квадратом считаются только квадраты со стороной 1. Выполняться должно меньше 1 секунды, а у меня при определенных значениях n оно выполнятся дольше.

[jcmvbkbc]

> посчитать минимальное количество сторон квадрата при заданном их количестве n
Ничего не понял. У квадрата всегда 4 стороны. n -- количество чего?

[LanternOfDarkness]

квадратов

Answer 4

[SHVV]

Я бы сделал цикл не по i до n, а по c до с*с < n. Сам код будет сложнее, но, во-первых, цикл будет выполняться меньшее число раз, во-вторых, вы сэкономите медленную операцию возведения в произвольную степень.

Comments

[cjey]

Можно даже оставить цикл по i, а извлечение квадратного корня заменить возведением в квадрат.
p = 1;
p2 = p*p;
for (i...)
{
if (p2 <= i)
{
p += 1;
p2 = p*p;
}
c = p - 1;
.....
}

[SHVV]

Как вариант. Но при больших n всё равно глупо гонять цикл лишние тысячи раз ради одного +1, лучше просто прибавлять сразу разницу между соседними числами последовательности. Это сразу понизит сложность алгоритма с O(N) до O(sqrt(N)).

Answer 5

[bogolt]

Очевидно что самая долгая операция это пользовательский ввод, поэтому нужно быстрее водить число =)

Шутки в сторону. Для начала убедитесь что вы собираете проект с включенной оптимизацией. Например мой старенький Core2Duo для n=999999 выдает ответ почти за секунду, после того как я собрал вашу программу с O2.

ps. Чтобы выложить код в вопрос не нужно вставлять его картинкой - достаточно просто обернуть его в тег код ( поглядите на кнопки доступные в редакторе сообщений).