I implemented simple (dumb) algorithm for finding the largest Collatz trajectory (see Collatz conjecture) for all numbers < 100,000,000 in Python, Rust and Elixir.
I benchmarked them with time
command, assuming boot time is negligible
(Python and Elixir need ~1 sec to boot before the calculation loop starts but their runtime is in hundreds of seconds anyway.
Rust program boots in couple of milliseconds.)
Results:
Python (mem usage gradually grows up to ~1 GB):
174.02 real 173.34 user 0.60 sys
Rust (mem usage of 191 MB):
1.27 real 1.21 user 0.05 sys
Elixir (max mem usage 7.2 GB of RAM, but mostly between 3-4 GB):
305.90 real 275.36 user 35.41 sys
If we take Rust (shortest runtime) as baseline then:
lang | times slower | times memory |
---|---|---|
Rust | 1 | 1 |
Python | 137 | 5.2 |
Elixir | 241 | 18.3 (mostly) / 37.6 (max) |
#!/usr/bin/env python3
# benchmarked with:
# time python3 collatz.py
SIZE = 100000000 # 100M
# SIZE = 1000000
results = []
longest_number = 0
longest_steps = 0
for number in range(SIZE):
n = number
steps = 0
while n > 1:
if n < number:
steps += results[n]
break
steps += 1
if n % 2 == 0:
n = n // 2
else:
n = 3 * n + 1
results.append(steps)
if steps > longest_steps:
longest_steps = steps
longest_number = number
print(f'{longest_number} - {longest_steps} steps')
// benchmarked with:
// cargo build --release; time target/release/collatz
const SIZE: usize = 100_000_000;
// const SIZE: usize = 1_000_000_000;
fn main() {
let mut results: Vec<u16> = vec![0; SIZE];
let mut longest_number = 0;
let mut longest_steps = 0;
for number in 0..SIZE {
let mut n = number;
let mut steps = 0;
while n > 1 {
if n < number {
steps += results[n];
break;
}
steps += 1;
if n % 2 == 0 {
n = n / 2;
} else {
n = 3 * n + 1;
}
}
results[number] = steps;
if steps > longest_steps {
longest_steps = steps;
longest_number = number;
}
}
println!("{} - {} steps", longest_number, longest_steps);
}
# benchmarked with:
# time elixir collatz.ex
defmodule Collatz do
@size 100_000_000
def run do
run(0, %{}, 0, 0)
end
def run(number, results, longest_number, longest_steps) when number < @size do
steps = count_steps(number, number, 0, results)
results = Map.put(results, number, steps)
if steps > longest_steps do
run(number + 1, results, number, steps)
else
run(number + 1, results, longest_number, longest_steps)
end
end
def run(_number, _results, longest_number, longest_steps) do
IO.puts("#{longest_number} - #{longest_steps} steps")
end
defp count_steps(n, number, steps, results) when n > 1 do
if n < number do
steps + results[n]
else
n =
if rem(n, 2) == 0 do
div(n, 2)
else
3 * n + 1
end
count_steps(n, number, steps + 1, results)
end
end
defp count_steps(_n, _number, steps, _results), do: steps
end
Collatz.run()