Prime sieve

Prime sieve

[montgrimpulo]

with Ada.Text_IO;         use Ada.Text_IO;
with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;
procedure Primes_by_Sieve is
   task type Sieve is
      entry Pass_on (Int : Integer);
   end Sieve;

   task P6n;

   type Sieve_Ptr is access Sieve;

   function Get_New_Sieve return Sieve_Ptr is
   begin
      return new Sieve;
   end Get_New_Sieve;

   task body P6n is
      Limit : constant Integer := 2580976;
      Num   : Integer          := 1;
      S     : Sieve_Ptr        := new Sieve;
   begin
      while Num <= Limit loop
         S.Pass_on (6 * Num - 1);
         S.Pass_on (6 * Num + 1);
         Num := Num + 1;
      end loop;
   end P6n;

   task body Sieve is
      New_Sieve  : Sieve_Ptr;
      Prime, Num : Integer;
   begin
      accept Pass_on (Int : Integer) do
         Prime := Int;
      end Pass_on;
      New_Line;
      Put (Prime);
      loop
         select
            accept Pass_on (Int : Integer) do
               Num := Int;
            end Pass_on;
         or
            terminate;
         end select;
         exit when Num rem Prime /= 0;
      end loop;

      New_Sieve := Get_New_Sieve;
      New_Sieve.Pass_on (Num);

      loop
         select
            accept Pass_on (Int : Integer) do
               Num := Int;
            end Pass_on;
         or
            terminate;
         end select;
         if Num rem Prime /= 0 then
            New_Sieve.Pass_on (Num);
         end if;
      end loop;
   end Sieve;

begin
   null;
end Primes_by_Sieve;

The program above stops normally long before Limit (2580976). Which internal 
restrictions do apply (GNAT, GPS 4.9.1) ?

Re: Prime sieve

[Paul Rubin]

montgrimpulo <aghte@hotlinemail.com> writes:
> The program above stops normally long before Limit (2580976). Which internal 
> restrictions do apply (GNAT, GPS 4.9.1) ?

From the prime number theorem there are around 175k primes less than
2580976.  If that program does what it looks like, I suspect you're
running out of tasks, which in Gnat are implemented with posix threads.
Try putting an error check in Get_New_Sieve.

Re: Prime sieve

[Egil H H]

To debug, you should add an exception handler to your P6n task that outputs which exception is raised within its body. Then you should start to wonder why TASKING_ERROR is raised when calling S.Pass_On.

Hint: What happens to the Sieve task when it believes it's OK to terminate and your main body is "null;"

Re: Prime sieve

[J-P. Rosen]

Le 27/05/2015 16:35, montgrimpulo a écrit :
> The program above stops normally long before Limit (2580976). Which internal 
> restrictions do apply (GNAT, GPS 4.9.1) ?

Under Linux, you may effectively be limited by the number of processes,
and the only thing you can do is increase the limit.

Under Windows, only available memory space is the limit. You can greatly
increase the number of tasks by specifying a small Storage_Size.

Note: I give regularly this exercise to my students. There is a solution
without any pointer to tasks (and simpler btw)...

-- 
J-P. Rosen
Adalog
2 rue du Docteur Lombard, 92441 Issy-les-Moulineaux CEDEX
Tel: +33 1 45 29 21 52, Fax: +33 1 45 29 25 00
http://www.adalog.fr

Re: Prime sieve

[Jeffrey R. Carter]

On 05/27/2015 07:35 AM, montgrimpulo wrote:
> with Ada.Text_IO;         use Ada.Text_IO;
> with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;
> procedure Primes_by_Sieve is
>    task type Sieve is
>       entry Pass_on (Int : Integer);

What happens when someone passes a negative value to Pass_On? If only a certain
range of values is acceptable, it's better to use an appropriate (sub)type to
prevent the use of invalid values.

>    type Sieve_Ptr is access Sieve;

Access types are not needed for this problem. Not using this access type
simplifies the body of Sieve.

>    task body P6n is
>       Limit : constant Integer := 2580976;

This constant does not need to be typed. I always prefer named numbers to typed
constants.

The ARM only guarantees a range of -(2 ** 15) + 1 .. (2 ** 15) - 1 for Integer.
This value makes your program non-portable.

>       while Num <= Limit loop

Why not use a for loop?

-- 
Jeff Carter
"This school was here before you came,
and it'll be here before you go."
Horse Feathers
48