N(N+1)/2= 0.5 N^2 + 0.5 N, which is just O(N^2)
For O() notation it doesn't matter whether it is 10*N^2 or 0.0001*N^2, it's stil O(N^2)

Why? Because for sizes large enough A*N^2 will always be larger than B*N and smaller than C*N^3, no matter what A, B and C are.

I'd like to suggest working in a residual number system (RNS) because it is very parrallel in nature. It is costly to transfer between number systems, but often that only needs to be done at beginning and end of problem. Which means it is not a solution at the single operation level.

http://www.math.utah.edu/~pa/MDS/residual.html

...and it is easy to understand/implement at the code/instruction level.

@vid: your algorithm is just a nice and clean rearangement of the usual multiplication algorithm. But in case most of your factors are only a few times bigger than the word size of 32..64bit(maybe say up to 256..4096bits), your algorithm will suretainly outperform the others.

I can't say much more about this subject right now because I'm not into it, but if someone is interested in it, I found this interesting paper about a FFT-based big number multiply:
http://citeseer.ist.psu.edu/yap00quickmul.html

I dug into FFT a while ago when I wanted to perform A*B and A^B (powers not xor ) with big numbers. http://board.flatassembler.net/topic.php?t=4882 There are code samples about the primitive method, but they are not very good. I couldn't get the hang of FFT so I didn't convert it to using it.

I have written multiply algorithms same way as you calculate with pen and paper. First code was written 1985-86 with 8bit 6502 assembly.

Later I have realize, that algorithm is very slow, better use already written librarys. Like GMP or something. They are over 10x faster.

I believe that most of us have trouble comprehending it!!! I know I do. It may be just sukoshi easier to understand, if one begins instead with the DFT (discrete Fourier transform), because the FFT is fast, only because of eliminating the many redundant multiplications found in the traditional DFT. The fastest FFT uses a "split radix", i.e. Radix 2 mixed with radix 4. Again, this is not necessary to study, in order to make (a little) progress on the DFT itself. The main point of Fourier's brilliant discovery is this:
Any time varying signal can be expressed as a sum of a series of sinusoids.
http://www.relisoft.com/Science/Physics/sound.html
http://www.dspguru.com/info/faqs/fftfaq2.htm
http://www.gweep.net/~shifty/portfolio/fftmulspreadsheet/index.html
http://www.dataq.com/applicat/articles/an11.htm
http://ccrma.stanford.edu/~lantz/fourier.html
http://www.eeglossary.com/fft.htm

The concept around the (fast) Fourier transformation and even the discret cosinus transformation are quiet clear for me, but the thing I don't understand is how to use the FFT for things that are no functions.

Usually you apply the FFT to a function like for example f: t -> E (t being time and E being energy) to get a FFT-function of it: f_FFT: t -> E, this is what tom tobias basically said

You can generalize this to any kind of function f: x -> y where x and y are any kind of value. (This is a 1-dimensional FFT, and of course FFTs can be any higher dimensions.)
now, if you don't have those 2 values, but just 1 value, like it is the case for one big number, how do you make a FFT out of that? for me there is some value missing.

(The DCT is a special case of the FFT, where the function is discretized and thus the integrals become sums. Also the evaluation points of the function are even spaced and their number is a power of 2 for 1 period).

Imagine the number is a time variant signal - each bit is in fact multiple particles moving through the circuitry! Either way (parallel or serial) we look at it the bits don't arrive at the same time.

Interesting and instructive article vid.

Hi guys, sorry if my question sounds silly..

I have a big integer decimal string, how to know how many dwords i need to store this number in memory to binary value.
Dividing the length of string by 10?

Good observation thimis, 2^32 is 10 digits long so 1 dword, then 2^64 is 20 digits long so 2 dwords, that immediately convinced me but unfortunately I found that 2^128 is 39 digits long... Rounding up would solve the problem but will round up always work? 2^256 is 78 digits long, 2^512 is 155 digits long... 2^65536 is 19768 digits long, here the error is severe, dividing by four gives only 1976.8 dwords but 2048 are needed.

Don't know how to precalculate the space needed but seems it is not that easy

NumberOfBits * Log10(2) = NumberOfDecimalDigits, for your examples you need add 1.
btw, 2^65536 is only 19729 digits

That was a very helpful tip, there was a magic number after all
jack2 & LocoDelAssembly thanks a lot guys.

jack2, it was so simple... Thanks for the tip. Now another problem though, up to which string length the calculation will not deviate from the real result? (using plain FPU)

FLDLG2 is one of the FPU constants.
(Will be accurate to 2^64 bits I presume.)

vid, sorry for any off-topic

Is this how to set round mode 10b?. I'm an FPU beginner.

That looks good unless the round mode starts as 01b or 11b. An instruction which clears the first bit of the round mode is needed. FWAIT hasn't been needed since 386/486 days, iirc. It's customary to preserve the control word and restore it at the end of the program (or long calculation) - with regard to speed: don't want to be changing it for only a couple instructions.

Raymond Filiatreault's tutorial should get you up to speed fairly quickly, imho.