#!/usr/bin/env perl
use strict;
use warnings;
use File::Map qw/map_anonymous unmap/;
my $size = shift || 1e6;
$size = 1e6 if $size < 1e6; # minimum
$size = 1e9 if $size > 1e9; # maximum
map_anonymous my $cache, $size * 2, 'shared';
# init cache with -1's, then set 0, 1, 2
substr($cache, 0, $size * 2, ( my $neg1 = pack('s', -1) ) x $size);
substr($cache, $_ * 2, 2, pack('s', $_)) for 0..2;
my @seqs;
sub collatz_seq {
my ( $seq_beg, $seq_end ) = @_;
my ( $n, $steps, $tmp );
for my $input ( $seq_beg..$seq_end ) {
$n = $input, $steps = 0;
while ( $n != 1 ) {
$steps += unpack('s', $tmp), last
if ($n < $size && ($tmp = substr($cache, $n * 2, 2)) ne $neg1);
$n % 2 ? ( $steps += 2, $n = (3 * $n + 1) >> 1 )
: ( $steps += 1, $n = $n >> 1 );
}
substr($cache, $input * 2, 2, pack('s', $steps)) if $input < $size;
push @seqs, [ $input, $steps ] if $steps > 400;
}
}
collatz_seq(2, $size); unmap $cache;
@seqs = ( sort { $b->[1] <=> $a->[1]} @seqs )[ 0..19 ];
printf "Collatz(%5d) has sequence length of %3d steps\n", @$_
for @seqs;
####
#!/usr/bin/env perl
use strict;
use warnings;
use File::Map qw/map_anonymous unmap/;
use MCE::Flow;
use MCE::Candy;
my $size = shift || 1e6;
$size = 1e6 if $size < 1e6; # minimum
$size = 1e9 if $size > 1e9; # maximum
map_anonymous my $cache, $size * 2, 'shared';
# init cache with -1's, then set 0, 1, 2
substr($cache, 0, $size * 2, ( my $neg1 = pack('s', -1) ) x $size);
substr($cache, $_ * 2, 2, pack('s', $_)) for 0..2;
# local to workers and the manager process
my @seqs;
sub collatz_seq {
my ( $seq_beg, $seq_end ) = @_;
my ( $n, $steps, $tmp );
for my $input ( $seq_beg..$seq_end ) {
$n = $input, $steps = 0;
while ( $n != 1 ) {
$steps += unpack('s', $tmp), last
if ($n < $size && ($tmp = substr($cache, $n * 2, 2)) ne $neg1);
$n % 2 ? ( $steps += 2, $n = (3 * $n + 1) >> 1 )
: ( $steps += 1, $n = $n >> 1 );
}
substr($cache, $input * 2, 2, pack('s', $steps)) if $input < $size;
push @seqs, [ $input, $steps ] if $steps > 400;
}
}
my $chunk_size;
$chunk_size = int( $size / MCE::Util::get_ncpu() / 80 + 1 );
$chunk_size += 1 if $chunk_size % 2;
mce_flow_s {
max_workers => MCE::Util::get_ncpu(),
chunk_size => $chunk_size,
bounds_only => 1,
gather => MCE::Candy::out_iter_array(\@seqs),
}, sub {
my ($mce, $chunk_ref, $chunk_id) = @_;
collatz_seq(@{ $chunk_ref });
@seqs > 20
? MCE->gather($chunk_id, ( sort { $b->[1] <=> $a->[1] } @seqs )[ 0..19 ])
: MCE->gather($chunk_id, @seqs);
@seqs = ();
}, 2, $size;
MCE::Flow->finish; unmap $cache;
@seqs = ( sort { $b->[1] <=> $a->[1]} @seqs )[ 0..19 ];
printf "Collatz(%5d) has sequence length of %3d steps\n", @$_
for @seqs;
##
##
$ time perl collatz3_a.pl 1e7
AMD 3970x, Docker Container, Ubuntu + Perlbrew Perl 5.30.1
collatz3_a.pl 1e7 13.130s (a) original, accepts argument
collatz3_b.pl 1e7 12.394s (b) a + replaced division with >> 1
collatz3_c.pl 1e7 12.261s (c) b + removed 1 level of branching
collatz3_d.pl 1e7 9.170s (d) c + reduced loop iterations
collatz3_e.pl 1e7 7.681s (e) d + less caching
collatz3_filemap 8.889s 1 core
collatz3_parallel 8.982s 1 core
collatz3_parallel 4.548s 2 cores
collatz3_parallel 2.378s 4 cores
collatz3_parallel 1.233s 8 cores
collatz3_parallel 0.661s 16 cores
collatz3_parallel 0.408s 32 cores
Collatz(8400511) has sequence length of 686 steps
Collatz(8865705) has sequence length of 668 steps
Collatz(6649279) has sequence length of 665 steps
Collatz(9973919) has sequence length of 663 steps
Collatz(6674175) has sequence length of 621 steps
Collatz(7332399) has sequence length of 616 steps
Collatz(7532665) has sequence length of 616 steps
Collatz(5649499) has sequence length of 613 steps
Collatz(8474249) has sequence length of 611 steps
Collatz(6355687) has sequence length of 608 steps
Collatz(8847225) has sequence length of 606 steps
Collatz(9533531) has sequence length of 606 steps
Collatz(6635419) has sequence length of 603 steps
Collatz(9953129) has sequence length of 601 steps
Collatz(7464846) has sequence length of 598 steps
Collatz(7464847) has sequence length of 598 steps
Collatz(3732423) has sequence length of 597 steps
Collatz(5598635) has sequence length of 595 steps
Collatz(8397953) has sequence length of 593 steps
Collatz(6298465) has sequence length of 590 steps