Massive Multiplication

[Xerpher]

I've searched through these boards and many others but only got some vague answers, so here's my request for help.

I'm doing alot of multiplication within a for loop and I was hoping I might be able to speed it up a bit. At the moment the multiplication is averaging approx 64 times a digitsum of greater than 1000.

At the moment I'm using a long interger class that stores all the digits in a char array but realise this may not be the best method. As well, a friend suggested I use a bit shifting method.

I've also looked into the GNU Multiple Precision Arithmetic Library which seems good and all, but all I want is the basic functions to be optimized, I don't think I need nor do I want that whole library. I have an unexplicable desire to code it mostly by myself =)

Any ideas on how to optimize multiplication (as well as division and modulus if time permits) would be extremely appreciated.

[wayside]

If you want to speed up multiplications, one way is to use the specialized instructions (SSE) for doing parallel multiplies.

Check out this thread, which has some good pointers on SSE.

http://www.codeguru.com/forum/showth...hreadid=290560

If you go to the search page and search for "SSE" you can get some other pages that might be helpful.

[Yves M]

Well, first of all, you need to have a good algorithm to do the multiplication. A few good ones are described in the GMP manual. Using a char array for data representation on a 32 bit machine is wasteful, since you can use arrays of 32 bit numbers and work directly with those. Leave any assembler optimisations until you have a good algorithm and a good datastructure, otherwise you'll just waste time.