Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses
 
PerlMonks  

Re: bigint == horrible performance?

by HAL9000 (Initiate)
on Jun 12, 2017 at 04:50 UTC ( [id://1192558]=note: print w/replies, xml ) Need Help??


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.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://1192558]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others avoiding work at the Monastery: (6)
As of 2024-04-25 15:44 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found