Реализация Суммы в Аде

Question

1)

Sum := 0;
for J in 1 .. N loop
Sum := Sum + J;
end loop;

2)

Sum := ((N + 1) * N) / 2;

Я читал, что первое (левое) решение более "общее" - применимо к широкому диапазону значений - чем второе (правое) решение Что означает «общее» - может быть вычислено без переполнения?

Answer 1

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

Промежуточный продукт в (2) будет переполнен при 2 ^ 31 - 1 (для 32-битного Integer, как вы получите на большинстве современных машин), что означает, что самый большой юридический результат будет несколько меньше 2 ^ 30 - 1. (1) позволит вам продолжить почти так же далеко (если вы можете ждать так долго!)

Эта программа исследует ограничения:

with Ada.Exceptions;
with Ada.Text_IO; use Ada.Text_IO;
procedure Summation is
   N : Integer := 1;
   Sum : Integer;
begin
   loop
      Put (Integer'Image (N) & " => ");
      Sum := ((N + 1) * N) / 2;
      Put_Line (Integer'Image (Sum));
      N := N + 1;
   end loop;
exception
   when E : others =>
      Put_Line (Ada.Exceptions.Exception_Message (E));
end Summation;

, а если вы скомпилируете с gnatmake -gnato summation.adb и запустите его, он заканчивается

46337 =>  1073581953
46338 =>  1073628291
46339 =>  1073674630
46340 =>  1073720970
46341 => summation.adb:9 overflow check failed

Если вы пропустите -gnato, чтобы GNAT не выполнял проверки переполнения чисел (прискорбное значение по умолчанию, выбранное, как я помню, для эффективности), это произойдет:

46337 =>  1073581953
46338 =>  1073628291
46339 =>  1073674630
46340 =>  1073720970
46341 => -1073716337
46342 => -1073669995
46343 => -1073623652

Полагаю, вы могли бы получить более длинный диапазон, поделив деленное на N и N + 1 четное (однозначно должно быть!) На 2 перед выполнением умножения.

Это на самом деле не проблема Ады (хотя -gnato позволяет легче увидеть, когда что-то идет не так, как может случиться с некоторыми другими языками), и это, конечно, не факториал! Можно ли редактировать заголовок?

Answer 2

Синтаксис в стороне (мы рассматриваем это концептуально, а не синтетически),

Поскольку мы действительно говорим о суммировании здесь, я отвечу на это.

Моя первая догадка, почемуСлева более общий, возможно, потому, что большинство людей забывают, что существует кратчайший путь для суммирования i от 1 до n.Поскольку оба уравнения математически эквивалентны.Какой из них быстрее в вашей системе?

Каждый выполняет утомительную задачу добавления каждого отдельного номера от 1 до n.

Если вы посмотрите статью о суммировании в Википедии, вы увидите, что для суммирования от 1 до 100 требуется 99 сложений.http://en.wikipedia.org/wiki/Summation

Принимая во внимание, что уравнение справа (ярлык) будет выполнять только деление, умножение и одно сложение.

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

Не могли бы вы дать ссылку на этот документ, контекст будетдействительно полезно.