“Implementation of residue number systems on GPUs” by Payne and Hitz

  • ©Bryson R. Payne and Markus A. Hitz




    Implementation of residue number systems on GPUs



    In recent years, the processing power of graphics processing units (GPUs) has greatly exceeded that of desktop central processing  units (CPUs). The current NVidia 7800 series GPU boasts a to- tal throughput of over 300 GFLOPs at peak performance. Further- more, the rate of increase in processing power in GPUs is roughly  double that of Moore’s Law for CPUs. Recent research has exam- ined the use of this computational power for other applications from  signal processing to bioinformatics and beyond. Residue number systems (RNS) are an alternate way of encoding long integers. Performing addition, subtraction, and multiplication  can be done component-wise, naturally leading to efficient imple- mentation on SIMD architectures. We examine a basic implementa- tion of arbitrary-precision arithmetic on a dual-GPU platform. We  compare our results to similar operations on super-computer vector processing hardware from just over a decade ago, as well as a GMP (Gnu Multi-Precision) library version on CPU only.  


    1. Hitz, M. A., and Kaltofen, E. 1995. Integer division in residue number systems. IEEE Trans. Comp. 44, 8, 983–989.
    2. Knuth, D. E. 1997. The Art of Computer Programming, vol. 2. Addison-Wesley.
    3. Payne, B. R., Owen, G. S., and Belkasim, S. O. 2005. Accelerated 2D image processing on GPUs. In Proceedings of the International Conference on Computational Science, Springer-Verlag, LNCS 3515, ICCS 2005, 256–264.

ACM Digital Library Publication:

Overview Page: