Skip to content

Instantly share code, notes, and snippets.

@scruss
Last active September 29, 2022 20:28
Show Gist options
  • Save scruss/f7af59d59efd6af2c7964cb8f771c828 to your computer and use it in GitHub Desktop.
Save scruss/f7af59d59efd6af2c7964cb8f771c828 to your computer and use it in GitHub Desktop.
there's something badly wrong with raku ...
#!/usr/bin/env perl
# collatz-memo.pl
# run time: appx 7 s
# output: max: 8400511 steps: 685
use v5.20;
use strict;
use warnings;
my ( $maxsteps, $maxval, $n, $steps, $x ) = qw/0 0 0 0 1/;
my @s;
$s[$x] = 0;
foreach $x ( 1 .. 10000000 ) {
$steps = 0;
$n = $x;
while ( ( $n > 1 ) && ( $n >= $x ) ) {
$n = ( $n & 1 ) ? 3 * $n + 1 : $n >> 1;
$steps++;
}
$steps += $s[$n];
$s[$x] = $steps;
( $maxsteps, $maxval ) = ( $steps, $x ) if ( $steps > $maxsteps );
}
say 'max: ', $maxval, ' steps: ', $maxsteps;
exit;
#!/usr/bin/env raku
# collatz-memo - uses over 10 GB and fails to complete in 5+ minutes
# raku version v2022.07
# equivalent Perl5 completes in 7 s and minimal memory
my ( $maxsteps, $maxval, $n, $steps, $x ) = qw/0 0 0 0 1/;
my @s;
@s[$x] = 0;
# Perl 5 used
# foreach $x ( 1 .. 10000000 ) {
loop ($x=1; $x <= 10000000; $x++) {
$steps = 0;
$n = $x;
while ( ( $n > 1 ) && ( $n >= $x ) ) {
$n = ( $n & 1 ) ?? 3 * $n + 1 !! $n +> 1;
$steps++;
}
$steps += @s[$n];
@s[$x] = $steps;
( $maxsteps, $maxval ) = ( $steps, $x ) if ( $steps > $maxsteps );
}
say 'max: ', $maxval, ' steps: ', $maxsteps;
exit;
@lizmat
Copy link

lizmat commented Sep 29, 2022

Your Raku code is incorrect.

You're using $n & 1, when you should have been using $n +& 1. The former creates a Junction in which all of the elements must be true, which in this case would be false only if $n were zero. After correcting this, your Raku version runs in about 35 seconds:

% time raku collatz-memo.raku
max: 8400511 steps: 685
real	34.68s
user	34.45s
sys	0.27

whereas your Perl version runs in just over 6 seconds:

% time perl collatz-memo.pl 
max: 8400511 steps: 685
real	6.35s
user	6.23s
sys	0.10s

So Perl comes out 5.5x faster. Still a sizeable amount. However, Raku uses bigints by default, and Perl uses native ints by default. If we change the Raku program to use native integers (and some other Raku-fication such as removing unnecessary parens) becomes:

my int $maxsteps;
my int $maxval;
my int $n;
my int $steps;
my int @s;

for 1..10_000_000 -> int $x {
    $steps = 0;
    $n     = $x;
    while $n > 1 && $n >= $x {
        $n = $n +& 1 ?? 3 * $n + 1 !! $n +> 1;
        ++$steps;
    }
    $steps += @s[$n];
    @s[$x] = $steps;
    ($maxsteps, $maxval) = ($steps, $x) if $steps > $maxsteps;
}

say "max: $maxval, steps: $maxsteps";

And this runs at just over 8 seconds:

% time raku collatz-memo-native.raku
max: 8400511, steps: 685
real	8.32s
user	8.27s
sys	0.09s

which makes Perl only 1.3x as fast (30% faster) than Raku for this job.

@scruss
Copy link
Author

scruss commented Sep 29, 2022

You're using $n & 1, when you should have been using $n +& 1

Ah, thanks. The interpreter didn't complain and these language changes are non-obvious

@lizmat
Copy link

lizmat commented Sep 29, 2022

It didn't complain because it was syntacticly valid code. Semantically pretty non-sensical in that context, but there you go.

Oddly enough, you did notice that the bit-shift right operator is +> . Anyways, all of those bitty operators start with a +, so at least that is consistent. So the bitwise OR is +|.

But yeah, I guess you could call & a false friend coming from Perl. I'll give you that :-)

@scruss
Copy link
Author

scruss commented Sep 29, 2022

I'm pretty amazed that I managed to pick up the +> thing from Perl to Raku guide - in a nutshell: I think the interpreter complained so I read up on it. It's a shame that Raku doesn't switch from int to bigints automatically like Python does: it's a huge speed increase

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment