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);
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);
Replacing the multiplies with adds (and reducing the number of redundant adds) gave a 22X speedup.
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.