Message40125
Logged In: YES
user_id=135050
I got 40 from testing. Basically I generated 250 random
numbers each for a series of sizes between 5 and 2990 bits
long at 15 bit intervals (i.e. the word size), and stored it
in a dictionary. Then timed 249 multiplies at each size for
a bunch of fence values and used gdchart to make a pretty
graph. It cerntainly could be optimized better per
compiler/platform, but I don't know how much gain you'ld see.
I split on the smaller number because I guessed it would be
better. My thought was that if I split on the smaller
number I'm guaranteed to reach the fence, at which point I
can use the gradeschool method at a near linear cost (since
it's O(n*m) and one of those two is at most the fence size).
If I split on the larger number, I may run into a condition
where the smaller number is less than half the larger, but I
haven't reached the fence yet, and then gradeschool could be
much more expensive.
|
|
Date |
User |
Action |
Args |
2007-08-23 15:13:24 | admin | link | issue560379 messages |
2007-08-23 15:13:24 | admin | create | |
|