Частичная сумма ряда

[Ktina]

Вычислить:
$\sum\limits_{k=1}^{10^6}\lfloor\sqrt k\rfloor$

У меня получился ответ 666167500, хотела сверить с Альфой, но она такие большие числа не берёт: http://www.wolframalpha.com/input/?i=su ... to+1000000
Вот тысячу берёт, а миллион - хоть ложись да помирай!

Вот мои соображения:
Имеем ряд $1, 1, 1, 2, 2, 2, 2, 2, \dots$ , сумма которого равна $1\cdot 3+2\cdot 5+\dots +n(2n+1)+\dots$
Таким образом, искомая сумма равна $1000+\sum\limits_{k=1}^{999}2k^2+k$
Воспользовавшись формулой $\sum\limits_{k=1}^{n}k^2=\frac{n(n+1)(2n+1)}{6}$, имеем
$1000+\sum\limits_{k=1}^{999}2k^2+k=1000+\frac{999\cdot 1000\cdot 1999}{6}\cdot 2+\sum\limits_{k=1}^{999}k$, что, в свою очередь, равно $1000+333\cdot 1000\cdot 1999+999\cdot 500=666167500$

Где брешь?

[svv]

Проверил на C++, ответ правильный.

[nnosipov]

Ktina в сообщении #540602 писал(а):

Вот тысячу берёт, а миллион - хоть ложись да помирай!

Просто подождать подольше нужно. Но вручную, конечно, быстрее будет.

[Ktina]

svv в сообщении #540603 писал(а):

Проверил на C++, ответ правильный.

(Оффтоп)

Ой, а можно код?

-- 19.02.2012, 18:25 --

nnosipov в сообщении #540604 писал(а):

Ktina в сообщении #540602 писал(а):

Вот тысячу берёт, а миллион - хоть ложись да помирай!

Просто подождать подольше нужно. Но вручную, конечно, быстрее будет.

(Оффтоп)

Это же в каком веке мы живём, что вручную быстрее?

[Joker_vD]

Ktina

Используется синтаксис C++

double s = 0.0;
for (int i = 1; i <= 1000 * 1000; i++)
  s += floor(sqrt((double)i));
printf("%d\n", s);

[nnosipov]

Ktina в сообщении #540605 писал(а):

(Оффтоп)

Это же в каком веке мы живём, что вручную быстрее?

(Оффтоп)

Я имел в виду Ваше решение. У меня Maple пока не подсчитал А вот теперь подсчитал: 666167500. Минут 15 прошло.

[ewert]

Ktina в сообщении #540605 писал(а):

Ой, а можно код?

Используется синтаксис Pascal

{$N+E-}

var  i,k: longint;   s: comp;

begin

  s:=0;

  for i:=1 to 1000000 do begin
    k:=trunc(sqrt(i));
    s:=s + k;
  end;

  writeln(s:15:2);
  readln;

end.

Считает где-то одну десятую секунды.

[svv]

Используется синтаксис C++

int s=0, a=0;
for (int k=0; k<=1000000; ++k)
{
   while ((a+1)*(a+1)<=k) ++a;
   s+=a;
}
 

Здесь только целочисленные операции, чтобы не мучили сомнения, вдруг где-то что-то не туда округлилось или набежала ошибка.

[ewert]

svv в сообщении #540621 писал(а):

Здесь только целочисленные операции, чтобы не мучили сомнения,

Но это уже почти на пределе: int -- он ведь, насколько помню, четырёхбайтовый.

[arseniiv]

О временах счёта. Mathematica 8 на P4 3 ГГц (правда, ещё куча программ одновременно работала):

In[2]:= Timing[Sum[Floor[Sqrt[k]], {k, 1, 10^6}]]
Out[2]= {185.391, 666167500}
In[3]:= Timing[Sum[Floor[Sqrt[k]], {k, 1., 1000000.}]]
Out[3]= {4.25, 666167500}

(Timing выдаёт секунды, затраченные на вычисление, и результат.) Радует, что целочисленно меньше 15 минут.

P. S. Это я рекламирую.

[svv]

Программер обязан знать наизусть: -2147483648...+2147483647
Важно, что 1000000 меньше 2147483648.
А, понял, Вы о сумме. Да, где-то еще один порядок -- и int всё.
В моей среде есть еще __int64

[Joker_vD]

Да, svv молодец — мой код считается 100 миллисекунд, его же менее чем за 100 наносекунд.

[arseniiv]

(Оффтоп)

Да уж, никакая СКА не сравнится даже с не очень оптимизированным кодом на C++!

[svv]

Только, к сожалению, и C++ не сравнится по удобству с СКА в тех областях, для которых они были созданы...

[iXuta]

$\sum\limits_{k=1}^{n}k^2=\frac{n(n+1)(2n+1)}{6}$
А не подскажите вывод этой формулы (или где его можно найти)?