CODEWITHSUNDEEP
implementationadafactorial
stardust
stardust

Reputation: 339

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?

Upvotes: 1

Views: 1720

Answers (2)

Simon Wright
Simon Wright

Reputation: 25501

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?

Upvotes: 4

onaclov2000
onaclov2000

Reputation: 5841

Syntax aside (we're looking at this conceptually not syntatically),

Since we are really talking about summations here, I'll respond to that.

My first guess why the left is more general is possibly because most people forget that there is a shortcut to a summation of i from 1 to n. Since both equations are mathematically equivalent. Which one is the faster on your system?

One does the tedious task of adding each individual number from 1 to n.

If you take a look at the summation article on wikipedia, you will see that the summation from 1-100 requires 99 additions. http://en.wikipedia.org/wiki/Summation

Whereas the equation on the right (the shortcut) will only do a division and a multiplication and a single addition.

My second guess is perhaps in certain (maybe more) situations it would be faster to do n additions....that's a system dependent situation, as well as problem dependent, so I think that's less likely.

Could you give a reference as to this document, context would be really helpful.

Upvotes: 2

Related Questions