Разделения очень больших чисел

Question

Я написал следующий код в C++:

#include <cmath> 
#include <iostream> 

using namespace std; 

int main() 
{ 
    double sum, containers, n ,c, max_cap, temp; 

    unsigned int j = 1; 
     cin >> n >> c; 
     sum = containers = n; 


     for (unsigned int i = 2 ; i <= c; ++i) 
     { 
      max_cap = i * n; 

      if (max_cap - sum > 0) 
      { 
       temp = ceil((max_cap - sum)/i); 
       containers += temp; 
       sum += i * temp; 
      } 
     } 

     cout << containers << '\n'; 
} 

Когда вход дан этот код «728 1287644555» она занимает около 5 секунд, чтобы вычислить ответ, но когда вход примерно три раза, т. е. «763 3560664427», это не дает долгого времени (я ждал около полутора часов). Как видно, алго имеет линейный порядок. Следовательно, это займет примерно 15 секунд. Почему это происходит? Это потому, что вход слишком велик во втором случае? Если да, то как это влияет на время?

Answer 1

Мое предположение было бы беззнаковым целочисленным переполнением.

 for (unsigned int i = 2 ; i <= c; ++i) 

i увеличивается до тех пор, пока не будет>c, но c является двойным тогда i является беззнаковой Int. Он достигает максимума (UINT_MAX) и обертывается до 0 до достижения значения c.

I.e. 1287644555 составляет менее UINT_MAX, поэтому он завершается. Но 3560664427 больше, чем UINT_MAX, поэтому он петли навсегда. Что только ставит вопрос о том, какую странную архитектуру вы используете на этом:

На моей собственной машине (UINT_MAX = 4294967295) первый вход занимает 16 секунд, а второй занимает 43,5 секунды, в значительной степени то, что вы ожидать.