Dearest Monks,
My mind has been amused with Collatz conjecture. See 1nickt's post about obtaining the top 20 sequences. Below is code for obtaining the longest progression. Here I try a GCC compiler intrinsic to further increase performance. That went well and so updated my prior post adding collatz_count_c2 there.
use strict;
use warnings;
use feature 'say';
use MCE::Flow;
use Inline C => Config =>
CCFLAGSEX => '-O2 -fomit-frame-pointer', clean_after_build => 0;
use Inline C => <<'END_OF_C_CODE';
#include <stdlib.h>
#include <stdint.h>
#if defined(_WIN32)
#define strtoull _strtoui64
#endif
void collatz_longest_c1( SV* _beg_n, SV* _end_n )
{
uint64_t beg_n, end_n, i, n, steps;
uint64_t number = 0, highest = 0;
Inline_Stack_Vars;
#ifdef __LP64__
beg_n = SvUV( _beg_n );
end_n = SvUV( _end_n );
#else
beg_n = strtoull( SvPV_nolen( _beg_n ), NULL, 10 );
end_n = strtoull( SvPV_nolen( _end_n ), NULL, 10 );
#endif
for ( i = end_n; i >= beg_n; i-- ) {
n = i, steps = 0;
/* count using the T(x) notation */
do {
n % 2 ? ( steps += 2, n = (3 * n + 1) >> 1 )
: ( steps += 1, n = n >> 1 );
} while ( n != 1 );
if ( steps >= highest ) {
number = i, highest = steps;
}
}
Inline_Stack_Reset;
Inline_Stack_Push( sv_2mortal( newSVuv(number ) ) );
Inline_Stack_Push( sv_2mortal( newSVuv(highest) ) );
Inline_Stack_Done;
}
void collatz_longest_c2( SV* _beg_n, SV* _end_n )
{
uint64_t beg_n, end_n, i, n, steps;
uint64_t number = 0, highest = 0;
Inline_Stack_Vars;
#ifdef __LP64__
beg_n = SvUV( _beg_n );
end_n = SvUV( _end_n );
#else
beg_n = strtoull( SvPV_nolen( _beg_n ), NULL, 10 );
end_n = strtoull( SvPV_nolen( _end_n ), NULL, 10 );
#endif
/* based on GCC compiler intrinsics demonstration by Alex Shirley
+*/
/* https://stackoverflow.com/questions/38114205/c-collatz-conjectu
+re-optimization */
/* https://www.go4expert.com/articles/builtin-gcc-functions-builti
+nclz-t29238 */
for ( i = beg_n; i <= end_n; i++ ) {
n = i, steps = 0;
if ( n % 2 == 0 ) {
steps += __builtin_ctz(n); /* account for all evens */
n >>= __builtin_ctz(n); /* always returns an odd */
}
/* when we enter we're always working on an odd number */
do {
n = 3 * n + 1;
steps += __builtin_ctz(n) + 1; /* account for odd and even
+ */
n >>= __builtin_ctz(n); /* always returns an odd */
} while ( n != 1 );
if ( steps > highest ) {
number = i, highest = steps;
}
}
Inline_Stack_Reset;
Inline_Stack_Push( sv_2mortal( newSVuv(number ) ) );
Inline_Stack_Push( sv_2mortal( newSVuv(highest) ) );
Inline_Stack_Done;
}
END_OF_C_CODE
sub collatz_longest {
my ( $beg_n, $end_n ) = @_;
my ( $number, $highest ) = ( 0, 0 );
my ( $i, $n, $steps );
for ( $i = $end_n; $i >= $beg_n; $i-- ) {
$n = $i, $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;
$number = $i, $highest = $steps
if ( $steps >= $highest );
}
return ( $number, $highest );
}
no warnings 'once';
#*collatz = \&collatz_longest; # choose collatz here
#*collatz = \&collatz_longest_c1; # using T(x) notation
*collatz = \&collatz_longest_c2; # using compiler intrinsics
my $m = shift || '1e7';
my ( @sizes, $chunk_size );
$chunk_size = int( $m / 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,
gather => \@sizes,
bounds_only => 1,
}, sub {
MCE->gather([ collatz( @{ $_[1] } ) ]);
}, 1, $m;
MCE::Flow->finish;
# Output the longest progression for the initial starting number.
# https://en.wikipedia.org/wiki/Collatz_conjecture
my $highest = ( sort { $b->[1] <=> $a->[1] } @sizes )[ 0 ]->[ 1 ];
say "Longest Collatz (index and value)";
say "@$_"
for ( sort { $a->[0] <=> $b->[0] }
grep { $_->[1] == $highest } @sizes )[ 0..0 ];
Output
The times include launching Perl, loading modules, spawning workers, reaping workers, and output (~ 0.100 seconds).
This outputs the longest progression for the number of steps to reach 1.
These numbers are the lowest ones with the indicated step count.
1e7 : 8400511 685
1 core
collatz_longest 1m16.034s
collatz_longest_c1 0m01.868s
collatz_longest_c2 0m00.778s
2 cores
collatz_longest 0m37.912s
collatz_longest_c1 0m00.965s
collatz_longest_c2 0m00.422s
4 cores
collatz_longest 0m19.799s
collatz_longest_c1 0m00.516s
collatz_longest_c2 0m00.239s
8 cores
collatz_longest 0m10.042s
collatz_longest_c1 0m00.285s
collatz_longest_c2 0m00.147s
16 cores
collatz_longest 0m05.196s
collatz_longest_c1 0m00.178s
collatz_longest_c2 0m00.109s
32 cores
collatz_longest 0m02.717s
collatz_longest_c1 0m00.137s
collatz_longest_c2 0m00.105s
collatz_longest_c1 (Inline C), collatz_longest (Perl)
32 cores
1e8 : 63728127 949 Inline C 0m00.738s Perl 0m30.554s
1e9 : 670617279 986 Inline C 0m07.198s Perl 5m51.938s
1e10 : 9780657630 1132 Inline C 1m17.059s
1e11 : 75128138247 1228 Inline C 13m51.122s
collatz_longest_c2 (Inline C)
32 cores
1e8 : 63728127 949 Inline C 0m00.340s
1e9 : 670617279 986 Inline C 0m03.023s
1e10 : 9780657630 1132 Inline C 0m33.152s
1e11 : 75128138247 1228 Inline C 6m10.355s
I can now sleep knowing that MCE can handle this. Just be sure to use sequence generation in MCE (i.e. mce_flow_s) with the bounds_only option.
Regards, Mario
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.