Search code examples
implementationadafactorial

Implementation of Sum in Ada

1) 

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

2)

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

enter image description here

I've read that the first(left) solution is more "general" - applicable to a wide range of values ​​- than second(right) solution. What does "general" mean - can be computed without overflow?

Solution

  • I think “more general” must mean “can be computed without overflow for a larger range of numbers”.

    The intermediate product in (2) will overflow at 2^31 - 1 (for a 32-bit Integer as you will get on most modern machines), which means that the largest legal result will be somewhat less than 2^30 - 1. (1) will let you continue almost as far again (if you can wait that long!)

    This program explores the limits:

    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;

    and if you compile with gnatmake -gnato summation.adb and run it it ends with

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

    If you leave out the -gnato, so that GNAT doesn’t do numeric overflow checks (a regrettable default, chosen as I remember for efficiency) this happens:

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

    I suppose you could get the longer range by dividing whichever of N and N + 1 was even (one clearly must be!) by 2 before doing the multiplication.

    This isn’t really an Ada problem (though -gnato makes it easier to see when things go wrong than might happen with some other languages), and it’s certainly not a factorial! Is it possible to edit the title?