in reply to bigint == horrible performance?

Instead of using bigint, use Math::NumSeq::CollatzSteps and Google. I googled #14 and found the answer: 837799. Double-check it: 
#!/usr/bin/perl -slw

use strict;
use warnings;
use Math::NumSeq::CollatzSteps;

my $seq = Math::NumSeq::CollatzSteps->new(
          step_type => 'both'
);
my $i = 837799;
my $value = $seq->ith($i);
print $value;

[download]
Returns 524 steps.

Replies are listed 'Best First'.
Re^2: bigint == horrible performance?
by BrowserUk (Patriarch) on Nov 06, 2011 at 11:02 UTC

    It's not a hard problem to solve: 

    #! perl -slw
use strict;
use Time::HiRes qw[ time ];

my $start = time;

my @res;
for ( 1 .. 1e6 ) {
    my $c = 0;
    my $n = $_;
    while( $n > 1 ) {
        ++$c;
        $n = $n&1 ? 3*$n+1 : $n/2;
        if( defined $res[ $n ] ) {
            $c += $res[ $n ];
            last;
        }
    }
    $res[ $_ ] = $c;
}

printf "Took %.6f seconds\n", time() - $start;

my( $n, $i ) = 0;
$n < $res[ $_ ] and ( $n, $i ) = ( $res[ $_ ], $_ )
    for 1 .. $#res;

print "longest sequence is $n steps starting with $i";

__END__
c:\test>collatz.pl
Took 2.000000 seconds
longest sequence is 524 steps starting with 837799

    [download]

    And the OP gave a link to his own 3 second solution, though I'm not sure why he pastebin'd it rather than posting it here.

    The intriguing thing is why the OP felt the need for bigint in the first place given that using Perl's native scalars he could calculate this(*) for numbers up to 2,251,799,813,685,248 before running into precision problems.

    (*)Assuming of course he had 400+ years and the exabytes of ram required to store the hash :)

    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
[d/l]
      So I've bumped into some stuff lately. XS extensions with no particular expectation of whether you're on an actual 64-bit bus or not. Perl itself actually recommends that it be compiled into 32-bit mode even when on a 64-bit architecture because the docs suppose <it will rarely be actually required>. (those are semi-quotes)

      So now, in the XS world, I've found myself facing a couple of things: 64 bit stuff and ipv6 (128 bits).

      In the XS world, Math::Int64 works quite nicely. However, I get way too many explosions with Math::128 at this point. So, I end up using packed arrays and timely casting, while hopefully not misplacing network byte-order.

      32-bit (and I guess 64-bit?) perl has unsigned, int, 'double', and 'string'. (e.g. UV, IV, NV, and PV). There is no native perl guarantee for 64-bit or 128-bit other than a string.

      I understand the perils of assuming too much about the data types. But in the world of XS, <whimper>

      Cheers,
      Matt

[reply]

        salva produces great code and enthusiastically maintains and extends his modules at the drop of a hat.

        Indeed, Math::Int128 came about because I asked a simple question here, and he offered to write one.

        And lo, two days later it was so.

        If the module is giving you problems, help him to help you. You will not regret the effort.

        With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority".
        In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
        I am really interested in knowing the details of any "explosions" related to Math::Int128. Report them through the CPAN bugtracker, please!
[reply]

      Ok .. to clear things up .. I am _not_ interested in better libraries or algorithms for that problem. I used bigint because I was not sure whether one of the Collatz chains would produce an intermediate number exceeding the int scope (probably my take on pessimation). Only after reading on the projecteuler forum that everyones solution was running in 1-5sec and mine taking 10min - while using the same algorithm as many others - made me suspicious. So I removed "use bigint" .. lo, and behold! It runs .. fast. Googling "perl bigint performance" didn't turn up anything useful, that's why I asked here.

      PS. I used pastebin because I wasn't sure about the "post code" conventions ;-)
[reply]
        So I removed "use bigint" .. lo, and behold! It runs .. fast.

        Arbitrary precision math is, regardless of the language in which it is written, much, much slower than fixed precision. It is the nature of the beast. If you know how arbitrary precision math works it will not come as any surprise.

        It therefore falls to the developer to understand that and only use arbitrary precision when it is actually required.

        I have a tendency to get somewhat exasperated when I see people offering Math::Big* as a solution to problems where there is a perception of a "precision problem", when 95% of them have far simpler and more efficient solutions.

        With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority".
        In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]

In Section Seekers of Perl Wisdom