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"; ##```## 1e7 : 8400511 685 1 core collatz_longest 1m16.034s MCE Perl code collatz_longest_pdl 0m13.691s Consumes 39 MiB collatz_longest_filemap 0m06.615s Consumes 59 MiB collatz_longest_scalar 0m06.148s Consumes 39 MiB collatz_longest_array 0m04.986s Consumes 330 MiB collatz_longest_c1 0m01.868s Inline C code collatz_longest_c2 0m00.778s Inline C code ```