Re: any suggestion to improve the following code?
Fei Liu wrote:
To summarize,
1. Use iteration instead of recursion to avoid function call
2. Drop boost::filesystem, use simpler fstream interface
3. I like the idea of using an bitarray to represent known/unknown result
4. Prefer unordered_map to hash_map
5. Body of main is too long, split up to smaller pieces
6. Optimize the algorithm
7. Expect numerical problems and solve them
Why? I wrote a simple prototype (in Perl) to check
my hypothesis (see below). Already at low numbers
(below 10,000,000), you'll run into very large
temporary numbers, which means, your code part:
unsigned int compute_steps(int n){
...
if(steps[n])
return steps[n];
if(n == 1) return 1;
if(n%2)
n = 3*n+1; // <=== here be dragons
else
n = n/2;
...
will fail dependent of your integer representation.
Already a number like (e.g.) 7,006,663 will iterate/recurse
478 times in your algorithm, leading to a fancy temporary
"n" of 9,586,432,619 - which requires proper 64-bit int handling.
You won't notice because there is "something" in
your number hash (which is garbage) ...
Regards
M.
Addendum:
na=ve collatz algorithm prototype, Perl
version (uses gmp)
usage: $> perl collatz.pl 1000 1000000
==>
use strict;
use warnings;
use Math::BigInt lib => 'GMP';
my ($fr, $to, $fn) = @ARGV;
printf "lmin:%d(n:%d,b:%s), lmax:%d(n:%d,b:%s)\n",
map @$_, chk_collatz_range($fr .. $to);
sub chk_collatz_range
{
my @stepcache;
while( my $nextnum = shift ) {
my ($lstr, $nstep, $bnum) = (0, 0, Math::BigInt->new($nextnum));
while( not $bnum->is_one() ) {
my $tmp = $bnum->bstr();
$lstr = $tmp if length $lstr < length $tmp && $lstr lt $tmp;
$bnum->is_odd() ? $bnum->bmuladd(3, 1) : $bnum->brsft(1);
++$nstep
}
push @stepcache, [$nstep, $nextnum, $lstr]
}
return ( sort { $a->[0] <=> $b->[0] } @stepcache )[0, -1]
}
<==