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-conjecture-optimization */
    /* https://www.go4expert.com/articles/builtin-gcc-functions-builtinclz-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 ];