Skip to content

Instantly share code, notes, and snippets.

@SqrtNegInf
Created October 27, 2018 14:41
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save SqrtNegInf/f3e9ef2807f225946871b385aeae6826 to your computer and use it in GitHub Desktop.
Save SqrtNegInf/f3e9ef2807f225946871b385aeae6826 to your computer and use it in GitHub Desktop.
Perl - Rosettacode Prime_conspiracy task
use ntheory qw/forprimes nth_prime/;
my $upto = 100_000_000;
my @freq;
my($this_digit,$last_digit)=(2,0);
forprimes {
($last_digit,$this_digit) = ($this_digit, $_ % 10);
$freq[$last_digit . $this_digit]++;
} 3,nth_prime($upto);
print "$upto first primes. Transitions prime % 10 → next-prime % 10.\n";
for my $i (0..$#freq) {
next unless $freq[$i];
printf "%s → %s count:\t%7d\tfrequency: %4.2f %%\n",
substr($i,0,1), substr($i,1,1), $freq[$i], 100*$freq[$i]/$upto
}
@danaj
Copy link

danaj commented Oct 29, 2018

Try this:

use ntheory qw/forprimes nth_prime/;

my $upto = 100_000_000;
my @freq;
my($this_digit,$last_tens)=(2,0);

forprimes {
  $last_tens = 10*$this_digit;
  $this_digit = $_ % 10;
  $freq[$last_tens+$this_digit]++;
} 3,nth_prime($upto);
my %freq = map { $_ => $freq[$_] } grep { defined $freq[$_] } 10 .. 99;

print "$upto first primes.  Transitions prime % 10 → next-prime % 10.\n";
printf "%s → %s count:\t%7d\tfrequency: %4.2f %%\n",
  substr($_,0,1), substr($_,1,1), $freq{$_}, 100*$freq{$_}/$upto
    for sort keys %freq;

Either version of the print is fine -- it doesn't matter which is used. By doing the map/grep, only the actual work portion is changed, leaving the setup and print function unchanged from the existing code (technically not true as I renamed last_digit to last_tens).

The two performance changes from your gist are:

  1. Change from list assignment to two single assignments.
  2. Keep things integers and not integer->string->integer (i.e. use 10*last + this rather than last . this)

Timing, perl 5.27.10:

22.8 orig using hash
23.8 your gist
15.4 your gist but changing line 9 to $freq[10*$last_digit + $this_digit]++;
14.4 hash but using changes above
10.4 version above (array rather than hash, two assignments, plus instead of concatenate)

The performance changes seem to be a mix of things. The fastest one leaves everything in integer form throughout the loop.

@danaj
Copy link

danaj commented Oct 29, 2018

Would you recommend replacing the code on RC or adding it as an alternative?

@SqrtNegInf
Copy link
Author

TIL... Yup, it all works as advertised. And I'm always in favor of keeping it simple, and putting just the best version on RC, so a vote to 'replace'.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment