NateTut has asked for the wisdom of the Perl Monks concerning the following question:

I'm playing around with a little program comparing different ways of implementing the Sieve of Eratosthenes. Yes I stole all the routines from the good old internet. I wrote a little routine to print out all of the primes found and I had the bright idea of using the number of iterations as the length argument to sprintf so that all the primes would line up regardless of value.


Unfortunately it's not working. I'm using perl 5.16 on Window$ 7. Here's the subroutine that doesn't work followed by the whole shebang if you're interested:


sub PrintPrimes
{
   my($Primes, $WrapAt, $Iterations) = @_;

   my $PrimeString = '';
   my $PrimeStrings;
   my $ItLength = length($Iterations);

   foreach my $Prime (@$Primes)
      {
      my $PreviousPrimeString = $PrimeString . "\n";
      $PrimeString .= sprintf("%*.0d", $ItLength, $Prime) . ', ';
      if(length($PrimeString) > $WrapAt)
         {
         push(@$PrimeStrings, $PreviousPrimeString);
         $PrimeString = $Prime . ', ';
         }
      }

   chop($PrimeString);
   $PrimeString .= "\n\n";
   push(@$PrimeStrings, $PrimeString);
   $PrimeString = '';

   foreach my $String (@$PrimeStrings)
      {
      $PrimeString .= $String;
      }

   return($PrimeString);
}

[download]

#!/usr/bin/perl
use strict;
use warnings;

use constant error            => -1;
use constant noerror          => 0;
use constant false            => 0;
use constant true             => 1;

$| = true;

#
# Modules Used
#
use Data::Dumper::Simple;
use DEM::Print;
use Time::HiRes qw( gettimeofday tv_interval );

#
# PrintPrimes
#
# Print Primes in a line, wrap at $column
#
# Arguments: $Primes - Array of Primes
#            $WrapAt - Column to wrap at
#
# Returns: $PrimeString - Comma seperated list of primes Found
#
sub PrintPrimes
{
   my($Primes, $WrapAt, $Iterations) = @_;

   my $PrimeString = '';
   my $PrimeStrings;
   my $ItLength = length($Iterations);

   foreach my $Prime (@$Primes)
      {
      my $PreviousPrimeString = $PrimeString . "\n";
      $PrimeString .= sprintf("%*.0d", $ItLength, $Prime) . ', ';
      if(length($PrimeString) > $WrapAt)
         {
         push(@$PrimeStrings, $PreviousPrimeString);
         $PrimeString = $Prime . ', ';
         }
      }

   chop($PrimeString);
   $PrimeString .= "\n\n";
   push(@$PrimeStrings, $PrimeString);
   $PrimeString = '';

   foreach my $String (@$PrimeStrings)
      {
      $PrimeString .= $String;
      }

   return($PrimeString);
}

#
# Classic
#
# Classic Sieve of Eratosthenes
#
# Arguments: $n - Number of Iterations
#
# Returns: @Primes - List of Primes Found
#
sub Classic
{
   my $n = shift;
   my @composite;
   for my $i (2 .. int(sqrt($n)))
      {
      if (!$composite[$i])
         {
         for (my $j = $i*$i; $j <= $n; $j += $i)
            {
            $composite[$j] = 1;
            }
         }
   }
   my @primes;
   for my $i (2 .. $n)
      {
      $composite[$i] || push @primes, $i;
      }
   @primes;
}

#
# OddsOnly
#
# Odds Only a Faster Sieve
#
# Arguments: $n - Number of Iterations
#
# Returns: @Primes - List of Primes Found
#
sub OddsOnly
{
  my($n) = @_;
  return @{([],[],[2],[2,3],[2,3])[$n]} if $n <= 4;

  my @composite;
  for (my $t = 3;  $t*$t <= $n;  $t += 2)
     {
     if (!$composite[$t])
        {
        for (my $s = $t*$t;  $s <= $n;  $s += $t*2)
           {
           { $composite[$s]++ }
           }
     }
  }

  my @primes = (2);
  for (my $t = 3;  $t <= $n;  $t += 2)
     {
     $composite[$t] || push @primes, $t;
     }

  @primes;
}

#
# OddsOnlyVectors
#
# Odds Only a Faster Sieve With Vectors
#
# Arguments: $end - Number of Iterations
#
# Returns: @Primes - List of Primes Found
#
sub OddsOnlyVectors
{
  my($end) = @_;
  return @{([],[],[2],[2,3],[2,3])[$end]} if $end <= 4;
  $end-- if ($end & 1) == 0; # Ensure end is odd

  my ($sieve, $n, $limit, $s_end) = ( '', 3, int(sqrt($end)), $end >> 
+1 );
  while ( $n <= $limit ) {
    for (my $s = ($n*$n) >> 1; $s <= $s_end; $s += $n) {
      vec($sieve, $s, 1) = 1;
    }
    do { $n += 2 } while vec($sieve, $n >> 1, 1) != 0;
  }
  my @primes = (2);
  do { push @primes, 2*$_+1 if !vec($sieve,$_,1) } for (1..int(($end-1
+)/2));
  @primes;
}

#
# OddsOnlyStrings
#
# Odds Only With Strings
#
# Arguments: $end - Number of Iterations
#
# Returns: @Primes - List of Primes Found
#
sub OddsOnlyStrings
{
  my($end) = @_;
  return @{([],[],[2],[2,3],[2,3])[$end]} if $end <= 4;
  $end-- if ($end & 1) == 0;
  my $s_end = $end >> 1;

  my $whole = int( ($end>>1) / 15);    # prefill with 3 and 5 marked
  my $sieve = '100010010010110' . '011010010010110' x $whole;
  substr($sieve, ($end>>1)+1) = '';
  my ($n, $limit, $s) = ( 7, int(sqrt($end)), 0 );
  while ( $n <= $limit ) {
    for ($s = ($n*$n) >> 1; $s <= $s_end; $s += $n) {
      substr($sieve, $s, 1) = '1';
    }
    do { $n += 2 } while substr($sieve, $n>>1, 1);
  }
  # If you just want the count, it's very fast:
  #       my $count = 1 + $sieve =~ tr/0//;
  my @primes = (2, 3, 5);
  ($s, $n) = (3, 7-2);
  while ( (my $nexts = 1 + index($sieve, "0", $s)) > 0 ) {
    $n += 2 * ($nexts - $s);
    $s = $nexts;
    push @primes, $n;
  }
  @primes;
}

#
# SieveIt
#
# Run all the Sieve Routines
#
# Arguments: $end - Number of Iterations
#
# Returns: Not Much
#
sub SieveIt
{
   my ($Iterations, $Sieves) = @_;

   #
   # Run each Sieve of Eratosthenes routine
   #
   foreach my $Sieve (keys(%$Sieves))
      {
      my $StartingTime = [gettimeofday()];
      my @Primes = $Sieves->{$Sieve}->{'Sub'}->($Iterations);
      my $ElapsedTime = tv_interval($StartingTime);
      $Sieves->{$Sieve}->{'Time'} = $ElapsedTime;
      Print(sprintf("%s:%.6f\n", $Sieve, $ElapsedTime) . PrintPrimes(\
+@Primes, 80, $Iterations));
      }

   Print("Times:\n");
   foreach my $Sieve (sort({$Sieves->{$a}->{'Time'} <=> $Sieves->{$b}-
+>{'Time'}} keys(%$Sieves)))
      {
      Print(sprintf("%16s:%.6f\n", $Sieve, $Sieves->{$Sieve}->{'Time'}
+));
      }
}

#
# Main
#
if($ARGV[0] !~ /^\d+$/)
   {
   Print("Usage: Sieve NumberOfIterations\n");
   exit(1);
   }

my $Sieves;
%$Sieves =
   (
     'Classic' =>
         {
           'Sub'  => \&Classic
         , 'Time' => 0
         }
   ,
     'OddsOnly' =>
         {
           'Sub'  => \&OddsOnly
         , 'Time' => 0
         }
   ,
   'OddsOnlyVectors' =>
       {
         'Sub'  => \&OddsOnlyVectors
       , 'Time' => 0
       }
 ,
   'OddsOnlyStrings' =>
       {
         'Sub'  => \&OddsOnlyStrings
       , 'Time' => 0
       }
 ,
   )
;

SieveIt($ARGV[0], $Sieves);
__END__

[download]

Replies are listed 'Best First'.
Re: sprintf not acting like I expect
by SuicideJunkie (Vicar) on Dec 03, 2014 at 19:00 UTC

    First, show a small sample of the output you don't like, and a sample of how you want it to look like.

    Next, trim down the code to a minimum that still shows the problem. In this case, it would probably be a short array of primes, and a loop doing sprintf from that array.

    Now, my question would be why do you think the number of iterations would be directly proportional to the printed length of the prime numbers?

    I'd expect the value of the largest prime to be proportional to the number of iterations. And the printed length of that to be log base 10 of that.

    PS: surely there aren't *that* many prime numbers you're collecting. Why not save them all to an array, then check the actual length of the last one and use that to decide how much space you need?

[reply]
[d/l]
      Ok, consider me properly chastised. I don't post too often and I thought it was clear that the numbers were not lining up. Anyway here's the current output:

         2,    3,    5,    7,   11,   13,   17,   19,   23,   29,   31,   37
+,   41,
43,   47,   53,   59,   61,   67,   71,   73,   79,   83,   89,   97, 
+ 101,
103,  107,  109,  113,  127,  131,  137,  139,  149,  151,  157,  163,
+  167,
173,  179,  181,  191,  193,  197,  199,  211,  223,  227,  229,  233,
+  239,
241,  251,  257,  263,  269,  271,  277,  281,  283,  293,  307,  311,
+  313,
317,  331,  337,  347,  349,  353,  359,  367,  373,  379,  383,  389,
+  397,
401,  409,  419,  421,  431,  433,  439,  443,  449,  457,  461,  463,
+  467,
479,  487,  491,  499,  503,  509,  521,  523,  541,  547,  557,  563,
+  569,
571,  577,  587,  593,  599,  601,  607,  613,  617,  619,  631,  641,
+  643,
647,  653,  659,  661,  673,  677,  683,  691,  701,  709,  719,  727,
+  733,
739,  743,  751,  757,  761,  769,  773,  787,  797,  809,  811,  821,
+  823,
827,  829,  839,  853,  857,  859,  863,  877,  881,  883,  887,  907,
+  911,
919,  929,  937,  941,  947,  953,  967,  971,  977,  983,  991,  997,

      [download]

      I would like all the columns to be lined up. Here's some pared down example code:

      use strict;
use warnings;

use Data::Dumper::Simple;

sub PrintPrimes
{
   my($Primes, $WrapAt, $Iterations) = @_;

   my $PrimeString = '';
   my $PrimeStrings;
   my $ItLength = length($Iterations);

   foreach my $Prime (@$Primes)
      {
      my $PreviousPrimeString = $PrimeString . "\n";
      $PrimeString .= sprintf("%*.0d", $ItLength, $Prime) . ', ';
      if(length($PrimeString) > $WrapAt)
         {
         push(@$PrimeStrings, $PreviousPrimeString);
         $PrimeString = $Prime . ', ';
         }
      }

   chop($PrimeString);
   $PrimeString .= "\n\n";
   push(@$PrimeStrings, $PrimeString);
   $PrimeString = '';

   foreach my $String (@$PrimeStrings)
      {
      $PrimeString .= $String;
      }

   return($PrimeString);
}


my $Primes;
@$Primes =
(
   2,    3,    5,    7,   11,   13,   17,   19,   23,   29,   31,   37
+,   41,
43,   47,   53,   59,   61,   67,   71,   73,   79,   83,   89,   97, 
+ 101,
103,  107,  109,  113,  127,  131,  137,  139,  149,  151,  157,  163,
+  167,
173,  179,  181,  191,  193,  197,  199,  211,  223,  227,  229,  233,
+  239,
);

print(PrintPrimes($Primes, 80, 1000));

      [download]
[reply]
[d/l]
[select]

        From that, I can see that you have 5 characters (incl. space) between each number. The problem is only that you're not putting the proper amount of space before the first number of each row.

        The chop and push and loop is odd. I suspect you're doing a lot of string analysis in the middle, instead of pre-calculating the important values. I'd suggest a simple:

        my $itemLength = length($iterations);
#account for comma and 1 space extra, but at least 1 number per row!
my $NumPerRow = int(80/($itemLength+2)) || 1; 
my $format = "%0${itemLength}d, ";
while (@primeNumbers)
{
  printf($format, shift @primeNumbers) for (1..$NumPerRow);
  print "\n";
}

        [download]

        There is no need to build up a big string of all the results. IO is buffered by default so many separate prints will be efficient.

[reply]
[d/l]
Re: sprintf not acting like I expect
by ww (Archbishop) on Dec 03, 2014 at 18:59 UTC
    "it's not working."

    Sorry, that's not enough info to take the trouble to try to help you.

    It's not as if you're a noob: you've been here 10 years; long enough to know what follows: Tell us 'what's not working; how it's not working (exact warning and/or error messages, if any) and how whatever is happening is at variance with your expectations, desires.'

    And, instead of posting several hundred lines of code (TL,DR), pare your code down to a runnable snippet that still fails in the same manner.



    Questions containing the words "doesn't work" (or their moral equivalent) will usually get a downvote from me unless accompanied by:
    1. code
    2. verbatim error and/or warning messages
    3. a coherent explanation of what "doesn't work actually means.
[reply]
[d/l]
Re: sprintf not acting like I expect
by davido (Cardinal) on Dec 03, 2014 at 19:19 UTC

    I'd encourage you to read the documentation for sprintf, and then explain in a follow-up in this thread how you think the line of code you wrote should work. I think as you go through the process of explaining what is supposed to happen, you'll probably discover in what way your use of sprintf doesn't match how it actually works.


    Dave

[reply]
      Never mind. It had nothing to do with sprintf except that I was initializing a string without using it to format the number. Sorry to have bothered you all.
[reply]
[d/l]
Re: sprintf not acting like I expect
by Laurent_R (Canon) on Dec 03, 2014 at 21:55 UTC
    More than 260 lines of code to implement a Sieve of Eratosthenes, especially in Perl, that seems to be totally out of proportion with the simplicity of the algorithm. Something must be wrong with your approach, but I don't feel like spending time decorticating your code to figure out, at least not right now, not enough time.

    When I was an IT student (a number of years ago), I implemented it in Pascal or perhaps Modula II (or possibly ADA or even C), I don't remember exactly, in at least 4 or 5 times less code, although these languages are much more talkative than Perl. I am fairly sure I could easily do it, neat and clear, in no more than 25 lines of straight-forward Perl code without sacrificing clarity in the slightest manner. Really, your approach of the problem must be flawed. No time now to look at your code in details, but I'll come back to it if I do not forget.

[reply]

Back to Seekers of Perl Wisdom