collatz

competition.rb

# 0.53 s, 31424 kb
$memo = {}

def collatz(n)
    return $memo[n] if $memo[n]
	$memo[n] = case
        when n == 1  then 1
        when n.even? then 1 + collatz(n.div 2)
        else              1 + collatz(3 * n + 1)
        end
end

(1..100_000).each { |n| puts "#{n} #{collatz n}" }

initial.raku

# 21.89 s, 197740 kb
use experimental :cached;

sub Collatz ($n) is cached {
	given ($n) {
		when (1)         { 1 };
		when ($n  %% 2 ) { 1 + Collatz($n / 2) };
		when ($n !%% 2 ) { 1 + Collatz(3 * $n + 1) };
	}
}

(1 .. 1E5).map: -> $n {
	say join ' ', $n,  Collatz $n;
}

manual.raku

# 4.40 s, 157024 kb
sub collatz ($n) {
    state %memo;
    return %memo{$n} if %memo{$n}:exists;
	%memo{$n} = do given $n {
		when 1       { 1 };
		when $n %% 2 { 1 + collatz($n div 2) };
		default      { 1 + collatz(3 * $n + 1) };
	}
}

say $_, ' ', collatz $_ for 1..100_000;

modified.raku

# 12.00 s, 175020 kb
use experimental :cached;

sub collatz ($n) is cached {
	given $n {
		when 1       { 1 };
		when $n %% 2 { 1 + collatz($n div 2) };
		default      { 1 + collatz(3 * $n + 1) };
	}
}

say $_, ' ', collatz $_ for 1..100_000;

# japhb: 1.63 s, 145748 kb
my %memo;
sub collatz (int $n) {
    %memo{$n} //= ($n == 1 ?? 1 !!
                   $n %% 2 ?? 1 + collatz($n div 2) !!
                              1 + collatz(3 * $n + 1))
}

say $_, ' ', collatz $_ for 1..100_000;