For a program I wrote to find Euler bricks (rectangular solids where all 3 edges and all three face diagonals are integers), the run time for longest edge < 2^32 and shortest edge < 2^15.5 = 46341 was 10.8s without bigint and 549.4s with bigint. That's a 51X slowdown. However, I believe the problem is mainly in multiplication rather than addition. I noticed that the largest multiplier in my program was 3, so I tried replacing 2*a with a+a and 3*a with a+a+a. The runtime was then 24.8s, only a 2.3X slowdown. I can live with that, even if it gets somewhat worse for larger numbers, in order to guarantee correctness.

Specifically, I rewrote: 

        # Now recursively generate the ternary tree.
        # (Note that the terms are the same in each branch except for 
+sign.)

        # Branch 1 (+-+):
        $i =   $a - 2*$b + 2*$h;
        $j = 2*$a -   $b + 2*$h;
        $k = 2*$a - 2*$b + 3*$h;
        &generate($i,$j,$k);

        # Branch 2 (+++):
        $i =   $a + 2*$b + 2*$h;
        $j = 2*$a +   $b + 2*$h;
        $k = 2*$a + 2*$b + 3*$h;
        &generate($i,$j,$k);

        # Branch 3 (-++):
        $i =   -$a + 2*$b + 2*$h;
        $j = -2*$a +   $b + 2*$h;
        $k = -2*$a + 2*$b + 3*$h;
        &generate($i,$j,$k);

[download]
to be: 
        # Now recursively generate the ternary tree.
        # (Note that the terms are the same in each branch except for 
+sign.)

        # Code to test whether bigint is mainly slowed by multiplies.
        $a2 = $a + $a;
        $b2 = $b + $b;
        $h2 = $h + $h;
        $h3 = $h + $h2;

        # Branch 1 (+-+):
        $i = $a  - $b2 + $h2;
        $j = $a2 - $b  + $h2;
        $k = $a2 - $b2 + $h3;
        &generate($i,$j,$k);

        # Branch 2 (+++):
        $i = $a  + $b2 + $h2;
        $j = $a2 + $b  + $h2;
        $k = $a2 + $b2 + $h3;
        &generate($i,$j,$k);

        # Branch 3 (-++):
        $i = -$a  + $b2 + $h2;
        $j = -$a2 + $b  + $h2;
        $k = -$a2 + $b2 + $h3;
        &generate($i,$j,$k);

[download]
Replacing the multiplies with adds (and reducing the number of redundant adds) gave a 22X speedup.

In reply to Re: bigint == horrible performance? by HAL9000
in thread bigint == horrible performance? by moodywoody

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.