### Variable length integer multiplication

I already have the standard one that mimics the one taught in schools written but I've found that there is a faster formula that can be used however I not sure how to implement this. The formula is called the "Fast Fourier Transform", could someone give me a simplistic example using this function base:
 ``123456789101112`` ``````typedef unsigned int uint; typedef unsigned char uchr; uint umul( uint* src, uint val ) { uint des = *src; ... *src = des; return des; } /* if you want to do the function itself then here is what I'm relying on */ uchr* vlumulEq( uchr* src, size_t sbits, uchr* val, size_t vbits ); /* operator *= */ uchr* vlumul( uchr* src, size_t sbits, uchr* val, size_t vbits ); /* operator* */``````

Edit: If you're doing the buffer based functions then I have some pre-made functions you may need. http://www.cplusplus.com/forum/general/109259/
Last edited on
In confused regarding what you are trying to do. Your title says "Variable length integer multiplication". The FFT doesn't do this at all.

A Fourier transform takes a waveform in the time-domain and translates it into a series of sinusoids at various frequencies. The magnitudes of each sinusoid is the output of the FFT.

What is it that you're trying to achieve?
Well I read that it is the fastest multiplication algorithm there is, I had googled a related topic and stumbled across this: http://www.cs.berkeley.edu/~vazirani/algorithms/chap2.pdf and thought that I could use it to squeeze out cycles since I'm making a custom framework and would like to have it as fast as possible.
@Stewbond
A Fourier transform is a multiplication. Polynomial multiplications have a surprising number uses -- including separating waveforms into component waveforms.

@awsdert
"Fastest" is a relative term -- it depends on the size of your operands which algorithm is fastest. A DFT is for fairly large operands. There are algorithms that can outperform it though.
Oh okay, well since my vli is expected use numbers beyond 8 bytes I would like to know which would be best suited for such large integers, for now I have this based on normal multiplication.
 ``12345678910111213141516171819202122232425262728293031323334353637383940`` ``````zxuchr* zx_vluMulEq( zxuchr *src, size_t sbits, zxuchr *val, size_t vbits ) { size_t s = 0, pi = 0, I = 0, end = 0; zxumax ssize = sbits, vsize = vbits; zxuchr *des = NULL, *tmp = NULL, bit = zxLastCharBit; if ( !src || !sbits ) return src; if ( !val || !vbits ) { for ( ; s < sbits; s += CHAR_BIT, ++I ) src[ I ] = 0u; return src; } if ( zx_udiv( &ssize, 2 ) ) ++ssize; if ( zx_udiv( &vsize, 2 ) ) ++vsize; des = (zxuchr*)malloc( (size_t)ssize ); for ( ; s < sbits; s += CHAR_BIT, ++I ) des[ I ] = 0u; for ( pi = sbits, s = pi - 1, I = (size_t)(vsize - 1); s != pi; --s, --pi ) { if ( val[ I ] & bit ) { tmp = zx_vluMvl( src, sbits, s ); zx_vluAddEq( des, sbits, tmp, sbits ); free( tmp ); } bit >>= 1; if ( !bit ) { bit = zxLastCharBit; --I; } } for ( s = 0, I = 0; s < sbits; ++I, s+= CHAR_BIT ) src[ I ] = des[ I ]; free( des ); return src; }``````

Edit:Removed remnants of old code.
Last edited on
Eight bytes is very small.
How big do you expect your numbers go actually get?

 After clicking Submit I took another glance at your code. I'm not exactly sure what you are doing...

You should check out Modern Computer Arithmetic
http://www.loria.fr/~zimmerma/mca/mca-cup-0.5.9.pdf

Hope this helps.
Last edited on
I'm aware of how small 8 bytes is but the point is the program I'm making will rely on this in addition to the built in types because it is aimed at being an all-in-one general purpose hacking tool and converting to/from text requires this and various other functions.
Topic archived. No new replies allowed.