Title | ||
---|---|---|
Can a Light Typing Discipline Be Compatible with an Efficient Implementation of Finite Fields Inversion? |
Abstract | ||
---|---|---|
We focus on the fragment TFA of lambda-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. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1007/978-3-319-12466-7_3 | Lecture Notes in Computer Science |
Field | DocType | Volume |
ARM architecture,Lambda calculus,Finite field,Normalization (statistics),Multiplicative inverse,Algorithm,Time complexity,Mathematics,UltraSPARC,Binary number | Conference | 8552 |
ISSN | Citations | PageRank |
0302-9743 | 1 | 0.36 |
References | Authors | |
6 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Daniele Canavese | 1 | 18 | 4.03 |
Emanuele Cesena | 2 | 37 | 5.28 |
Rachid Ouchary | 3 | 1 | 0.70 |
Marco Pedicini | 4 | 60 | 10.43 |
Luca Roversi | 5 | 183 | 21.03 |