Variable length integer multiplication

[awsdert]

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:

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/

[Stewbond]

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?

[awsdert]

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.

[Duthomhas]

@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.

[awsdert]

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.

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.

[Duthomhas]

Eight bytes is very small.
How big do you expect your numbers go actually get?


[edit] 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.

[awsdert]

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.