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

Can a light typing discipline be compatible with an efficient implementation of finite fields inversion?

PEDICINI, MARCO;
2014-01-01

Abstract

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.
2014
978-331912465-0
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].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/172140
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact