use strict; use warnings; use feature 'say'; use File::Map qw/map_anonymous unmap/; use PDL; # based on the caching demonstration by iM71 # https://stackoverflow.com/a/55361008 # https://stackoverflow.com/questions/38114205/c-collatz-conjecture-optimization sub collatz_longest_pdl { my ( $size ) = @_; my ( $length, $number ) = ( 0, 0 ); my ( $n, $steps, $tmp, $n2 ); my $cache = zeros( short(), $size + 1 ); for my $current ( 2 .. $size ) { $n = $current, $steps = 0; # count using the T(x) notation $n % 2 ? ( $steps += 2, $n = (3 * $n + 1) >> 1 ) : ( $steps += 1, $n = $n >> 1 ) while $n != 1 && $n >= $current; $tmp = $steps + at( $cache, $n ); set( $cache, $current, $tmp ); $length = $tmp, $number = $current if $tmp > $length; } return ( $number, $length ); } sub collatz_longest_array { my ( $size ) = @_; my ( $length, $number ) = ( 0, 0 ); my ( $n, $steps, $tmp ); my @cache; for my $current ( 2 .. $size ) { $n = $current, $steps = 0; # count using the T(x) notation $n % 2 ? ( $steps += 2, $n = (3 * $n + 1) >> 1 ) : ( $steps += 1, $n = $n >> 1 ) while $n != 1 && $n >= $current; $tmp = $steps + ( $cache[ $n ] // 0 ); $cache[ $current ] = $tmp; $length = $tmp, $number = $current if $tmp > $length; } return ( $number, $length ); } sub collatz_longest_filemap { my ( $size ) = @_; my ( $length, $number ) = ( 0, 0 ); my ( $n, $steps, $tmp ); map_anonymous my $cache, $size * 2 + 2, 'shared'; # fill cache with zero's substr($cache, 0, $size * 2 + 2, pack('s', 0) x ( $size + 1 )); for my $current ( 2 .. $size ) { $n = $current, $steps = 0; # count using the T(x) notation $n % 2 ? ( $steps += 2, $n = (3 * $n + 1) >> 1 ) : ( $steps += 1, $n = $n >> 1 ) while $n != 1 && $n >= $current; $tmp = $steps + unpack('s', substr($cache, $n * 2, 2)); substr($cache, $current * 2, 2, pack('s', $tmp)); $length = $tmp, $number = $current if $tmp > $length; } unmap $cache; return ( $number, $length ); } sub collatz_longest_scalar { my ( $size ) = @_; my ( $length, $number ) = ( 0, 0 ); my ( $n, $steps, $tmp ); # fill cache with zero's my $cache = pack('s', 0) x ( $size + 1 ); for my $current ( 2 .. $size ) { $n = $current, $steps = 0; # count using the T(x) notation $n % 2 ? ( $steps += 2, $n = (3 * $n + 1) >> 1 ) : ( $steps += 1, $n = $n >> 1 ) while $n != 1 && $n >= $current; $tmp = $steps + unpack('s', substr($cache, $n * 2, 2)); substr($cache, $current * 2, 2, pack('s', $tmp)); $length = $tmp, $number = $current if $tmp > $length; } return ( $number, $length ); } #*collatz = \&collatz_longest_pdl; # choose collatz here #*collatz = \&collatz_longest_array; #*collatz = \&collatz_longest_filemap; *collatz = \&collatz_longest_scalar; my ( $number, $length ) = collatz( shift || '1e7' ); say "Longest Collatz (index and value)"; say "$number $length";