Реализация Sum в Аде

1) 

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

2)

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

введите здесь описание изображения

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


implementation factorial ada
person stardust    schedule 10.01.2012    source источник
comment
Оператор присваивания в Аде — := без пробела посередине. Что-то не так с (1), Sum каждый раз перезаписывается и не дает правильного значения ни для одного ввода. (2) случайно дает правильное значение для ввода 3. Я думал, вы просто шутите, но я вижу, вы уже задавали дельные вопросы...   -  person Simon Wright    schedule 11.01.2012
comment
Ни один из них не вычисляет факториальную функцию, и ни один из них не является синтаксически правильным Ада. (Оператор := представляет собой одиночный токен, и вам не хватает многих точек с запятой.)   -  person Keith Thompson    schedule 11.01.2012
comment
Sum := 0; for J in 1 .. N loop Sum := Sum + J; end loop; Ой, простите! Я скопировал из PDF. Поэтому это было не правильно.   -  person stardust    schedule 11.01.2012
comment
Первое уравнение, судя по всему, является суммированием, а не факториалом, факториал, если я правильно помню, представляет собой что-то вроде функции типа 1*2*3*4...n.   -  person onaclov2000    schedule 11.01.2012
comment
Я думаю, что сегодня я слишком многому научился. Ты прав! Я стал таким тупым :) ...   -  person stardust    schedule 11.01.2012
comment
Я отредактировал вопрос, чтобы удалить факториал из вопроса, но у меня пока нет сумасшедших навыков редактирования, поэтому, если кто-то еще хочет сделать это быстрее, во что бы то ни стало.   -  person onaclov2000    schedule 11.01.2012

Ответы (2)


arrow_upward
4
arrow_downward

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

Промежуточный продукт в (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 легче увидеть, когда что-то пойдет не так, чем это может случиться с некоторыми другими языками), и это определенно не факториал! Можно ли отредактировать заголовок?

person Simon Wright    schedule 11.01.2012

arrow_upward
2
arrow_downward

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

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

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

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

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

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

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

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

person onaclov2000    schedule 10.01.2012