We focus on the fragment TFA of λ-calculus. It contains terms which normalize in polynomial time only. Inside TFA we translated BEA, a well known, imperative and fast algorithm which calculates the multiplicative inverse of binary finite fields. The translation suggests how to categorize the operations of BEA in sets which drive the design of a variant that we called DCEA. On several common architectures we show that these two algorithms have comparable performances, while on UltraSPARC and ARM architectures the variant we synthesized from a purely functional source can go considerably faster than BEA.
Canavese, D., Cesena, E., Ouchary, R., Pedicini, M., Roversi, L. (2014). Can a light typing discipline be compatible with an efficient implementation of finite fields inversion?. In 3rd International Workshop on Foundational and Practical Aspects of Resource Analysis, FOPARA 2013; Bertinoro; Italy; 29 August 2013 through 31 August 2013 (pp. 38-57). BERLIN HEIDELBERG : Springer-Verlag [10.1007/978-3-319-12466-7_3].