×

zbMATH — the first resource for mathematics

Recursive double-size fixed precision arithmetic. (English) Zbl 1434.65323
Greuel, Gert-Martin (ed.) et al., Mathematical software – ICMS 2016. 5th international conference, Berlin, Germany, July 11–14, 2016. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9725, 223-231 (2016).
Summary: We propose a new fixed precision arithmetic package called RecInt. It uses a recursive double-size data-structure. Contrary to arbitrary precision packages like GMP, that create vectors of words on the heap, RecInt large integers are created on the stack. The space allocated for these integers is a power of two and arithmetic is performed modulo that power. Operations are thus easily implemented recursively by a divide and conquer strategy. Among those, we show that this packages is particularly well adapted to Newton-Raphson like iterations or Montgomery reduction. Recursivity is implemented via doubling algorithms on templated data-types. The idea is to extend machine word functionality to any power of two and to use template partial specialization to adapt the implemented routines to some specific sizes and thresholds. The main target precision is for cryptographic sizes, that is up to several tens of machine words. Preliminary experiments show that good performance can be attained when comparing to the state of art GMP library: it can be several order of magnitude faster when used with very few machine words. This package is now integrated within the Givaro C++ library and has been used for efficient exact linear algebra computations.
For the entire collection see [Zbl 1342.68017].
MSC:
65Y04 Numerical algorithms for computer arithmetic, etc.
65Y15 Packaged methods for numerical algorithms
Software:
Givaro; RecInt; mpFq; gmp; GAUT; LinBox
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arazi, O., Qi, H.: On calculating multiplicative inverses modulo \[ 2^{m} \] . IEEE Trans. Comput. 57(10), 1435–1438 (2008). http://dx.org/10.1109/TC.2008.54
[2] Brent, R., Zimmermann, P.: Modern Computer Arithmetic. Cambridge University Press, New York (2010) · Zbl 1230.68014
[3] Burnikel, C., Ziegler, J.: Fast recursive division. Technical Report MPI-I-98-1-022, Max Planck Institute fr Informatik, October 1998. http://www.mpi-sb.mpg.de/ziegler/TechRep.ps.gz
[4] Coussy, P., Chavet, C., Bomel, P., Heller, D., Senn, E., Martin, E.: GAUT: a high-level synthesis tool for DSP applications. From algorithm to digital circuit. In: Coussy, P., Morawiec, A. (eds.) High-Level Synthesis, pp. 147–169. Springer, Netherlands (2008). http://dx.org/10.1007/978-1-4020-8588-8_9
[5] Dumas, J.-G.: On Newton-Raphson iteration for multiplicative inverses modulo prime powers. IEEE Trans. Comput. 63(8), 2106–2109 (2014). http://dx.org/10.1109/TC.2013.94 · Zbl 1364.11163
[6] Dumas, J.-G., Gautier, T., Giesbrecht, M., Giorgi, P., Hovinen, B., Kaltofen, E., Saunders, B.D., Turner, W.J., Villard, G.: LinBox: a generic library for exact linear algebra. In: ICMS 2002, Beijing, China, pp. 40–50, August 2002. http://ljk.imag.fr/membres/Jean-Guillaume.Dumas/Publications/icms.pdf · Zbl 1011.68182
[7] Dumas, J.-G., Giorgi, P., Pernet, C.: Dense linear algebra over prime fields. ACM Trans. Math. Softw. 35(3), 1–42 (2008). http://dx.org/10.1145/1391989.1391992 · Zbl 05517416
[8] Dumas, J.-G., Saunders, B.D., Villard, G.: On efficient sparse integer matrix Smith normal form computations. J. Symbol Comput. 32(1/2), 71–99 (2001). http://dx.org/10.1006/jsco.2001.0451 · Zbl 1050.65044
[9] Freivalds, R.: Fast probabilistic algorithms. In: Bečvář, J. (ed.) MFCS 1979. LNCS, vol. 74, pp. 57–69. Springer, Heidelberg (1979) · Zbl 0408.68035
[10] Gaudry, P., Thomé, E.: The mpFq library and implementing curve-based key exchanges. In: SPEED: Software Performance Enhancement for Encryption and Decryption, Amsterdam, Netherlands, pp. 49–64. ECRYPT Network, June 2007. http://hal.inria.fr/inria-00168429
[11] Granlund, T.: The GNU multiple precision arithmetic library, v6.1, November 2015. http://gmplib.org
[12] Kaltofen, E.L., Nehring, M., Saunders, B.D.: Quadratic-time certificates in linear algebra. In: ISSAC 2011, San Jose, USA, pp. 171–176, June 2011. http://www.math.ncsu.edu/kaltofen/bibliography/11/KNS11.pdf · Zbl 1323.68607
[13] Montgomery, P.L.: Modular multiplication without trial division. Math. Comput. 44(170), 519–521 (1985). http://dx.org/10.1090/S0025-5718-1985-0777282-X · Zbl 0559.10006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.