in reply to bigint == horrible performance?

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.