Both of the algorithms are similarly optimised. Actually Toom 4 is slightly more optimised than Toom 7.
You may be right, and no "premature decision" has been made. However it occurs to me that Toom 7 breaks into smaller chunks, so the multiplications are cheaper. The crossover is currently 700. Toom 7 breaks into chunks of 100 and 13 multiplies are done. Toom 4 breaks into chunks of 175 and 5 multiplies are done. It seems to me to be quite possible for Toom 7 to always beat Toom 4, or nearly so purely because of this sort of thing. I'm not saying this is the case. I'm just saying it may be the case. We are working on lots of assembly code to optimise Toom 4 and Toom 7. As for managing the sign/size stuff, I haven't decided whether I want to do it this way in the long run or not. It has some advantages which the other method does not. One thing I can say for sure is that the difference in speed in the generic case is negligible. The other optimisations we are going to be doing will make a much greater difference. Bill. 2009/4/19 David Harvey <dmhar...@cims.nyu.edu>: > > > > On Apr 15, 7:11 pm, Bill Hart <goodwillh...@googlemail.com> wrote: > >> Clicking on the graph does make it bigger, but yeah, the critical >> region we are talking about is a bit compressed. > > I just took a look at the toom4 code. It looks like there is a lot of > unnecessary sign/size management and data copying. I would suggest > some serious optimisation work before making a premature decision to > dump toom4 in favour of toom7. I can't think of any earthly reason why > a toom7 would beat toom4/5/6 near the toom3-toom4 threshold. It's like > claiming that a strassen matrix multiply written in C is fast for a > 10x10 matrix because you're comparing against an n^3 algorithm written > in python. Maybe the C-python analogy is unfair, but you get my drift. > > david > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "mpir-devel" group. To post to this group, send email to mpir-devel@googlegroups.com To unsubscribe from this group, send email to mpir-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/mpir-devel?hl=en -~----------~----~----~----~------~----~------~--~---
