Big Integer Multiplication with CUDA FFT (cuFFT) Library
Department of Computer Systems and Informatics, State Engineering University of Armenia, Yerevan, Armenia
International Journal of Innovative Research in Computer and Communication Engineering, Vol. 2, Issue 11, 2014
@article{bantikyan2014big,
title={Big Integer Multiplication with CUDA FFT (cuFFT) Library},
author={Bantikyan, Hovhannes},
journal={world},
volume={2},
number={11},
year={2014}
}
It is well recognized in the computer algebra theory and systems communities that the Fast Fourier Transform (FFT) can be used for multiplying polynomials. Theory predicts that it is fast for "large enough" polynomials. The basic idea is to use fast polynomial multiplication to perform fast integer multiplication. We can achieve really fast FFT multiplication on GPU with parallel FFT implementation, in this case with cuFFT. Here we provide cuFFT multiplication and its comparison with well known fast big integer arithmetic libraries (.net BigInteger, GMP, IntX). We also compare our results with results of other papers in this area. Experiments showed, that cuFFT multiplication is becoming faster than all other tested methods, when we deal with about 2^15 digit integers.
December 7, 2014 by hgpu
