наивный вопрос о времени выполнения для очень большого числа счетчиков

Question

У меня наивный вопрос о максимальном размере счетчика. Например, следующий код не может быть выполнен за разумное время, потому что ему нужно как минимум 2 ^ 512 арифметических операций, или, что более важно, ему нужно изменить значение i 2 ^ 512 раз!

c = 2 to the power 512;
for (i = 1, i < c, i++) {
   j = j + 1 / ( i * i + 1 );    

}

Но когда я использую программное обеспечение компьютерной математики "Mathematica", оно дает мне ответ менее чем за одну секунду. Мой вопрос заключается в том, как это может достичь этого?

пс. Мое наивное представление о размере счетчика связано с моим мнением о сложности. Когда я читаю некоторые книги (не слишком формальные, потому что они фокусируются только на сложности арифметических операций) о сложности, они всегда опускают стоимость индекса. Я могу себе это представить, только если счетчик маленький.

Answer 1

По некоторым предположениям, поскольку условие завершения вашего цикла установлено на 2 ^ 512, Mathematica могла бы рассматривать это как суммированную геометрическую последовательность и вычислять ее, используя формулу, вместо того, чтобы выполнять итерацию по всем значениям цикла.

Посмотрите на запись в Википедии Геометрическая прогрессия и страницу Вольфрама на Геометрическая серия .

Если бы это было на обычном языке программирования, например как C ++, Java или C #, вы были бы абсолютно правы! Кроме того, 2 ^ 512 - это очень большое число, которое может привести к переполнению «обычных» типов данных в этих языках.

Предполагая, что вы имеете в виду 2 для степени 512, а не 2 xor 512 (то есть 514).