What fields do we need?

[effectfully]

We use the Rational field for tests, but this is mostly for historical reasons. Rationals are not very efficient and we're not going to use them in production, so maybe we should just ditch them entirely.

On the other hand the Jubjub field is much less efficient for some reason (I guess, inversion is expensive?). And in our tests Rational is faster than even F17.

But maybe this is because we generate way too many tests involving stuff like asInteger (1/2) that just fails immediately?

This needs to be investigated.

Also F17 is too small. We should have some bigger field, like F97 just so that we can fit more tests into it (some tests in the compiler repo are disabled, because F17 is too small) while still testing overflows.

And probably we need a field of around 10^6/10^7 elements so that we can test some big expressions while retaining the efficiency of F17.

[kwxm]

Did we not add a field library at some point? If I recall correctly that would give you F97 (or ℤ/pℤ for any other prime p) for almost no work.

[effectfully]

Yes, but it doesn't seem efficient. I have an idea on how to use the library, but get optimized operations.

[kwxm]

It should be pretty easy to implement prime fields efficiently. You just want the integers modulo p with the usual addition, subtraction and multiplication. The tricky part is calculating inverses, which you do with the (very fast) extended Euclidean algorithm: https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm .

Given a prime p and an integer a such that p doesn't divide a (ie a ≠ 0 modulo p), the EEA gives you integers m and n with am + pn = 1, and then modulo p you've got am = 1, so m is the inverse of a modulo p (and you might want to reduce m to get 0 ≤ m ≤ p-1). That will give you an implementation of 𝔽_p which should be pretty much optimal.

It would be interesting to know why the galois-field package is inefficient: I imagine that's what it's doing underneath, for prime fields anyway. I'll have a look.

[kwxm]

Data.Galois.Field.Prime seems to be inheriting most of its operations from Data.Mod, which in turn uses GHC.Integer.GMP.Internals, which does most of its work using the GMP library (https://gmplib.org/). For example, inverses are calculated using recipModInteger, which uses a GMP function via the FFI to do the hard work. It's hard to see why any of this would be particularly inefficient, except that there's a lot of type-level stuff and you have to go through quite a few typeclasses. You'd think that GHC would be able to compile that pretty efficiently though.

[effectfully]

Data.Galois.Field.Prime seems to be inheriting most of its operations from Data.Mod, which in turn uses GHC.Integer.GMP.Internals, which does most of its work using the GMP library (https://gmplib.org/). For example, inverses are calculated using recipModInteger, which uses a GMP function via the FFI to do the hard work. It's hard to see why any of this would be particularly inefficient, except that there's a lot of type-level stuff and you have to go through quite a few typeclasses. You'd think that GHC would be able to compile that pretty efficiently though.

• recipModInteger is O(log n), right? Given that -1 is 52435875175126190479447740508185965837690552500527637822603658699938581184512 in Jubjub.F, it might cause slowdowns
• if dictionaries do not get inlined, that also can easily result in much less efficient code
• FFI calls are unsafe there, so they should be very cheap indeed

Given that Jubjub.F is around an order of magnitude slower than F17, I don't think it's something too surprising.

[jakzale]

Actually, I was thinking about `-1`. Since all these fields are circular, can we have an optimisation step that tries to remove negative numbers?

…

On Fri, Apr 10, 2020 at 5:06 PM effectfully ***@***.***> wrote: Data.Galois.Field.Prime seems to be inheriting most of its operations from Data.Mod, which in turn uses GHC.Integer.GMP.Internals, which does most of its work using the GMP library (https://gmplib.org/). For example, inverses are calculated using recipModInteger, which uses a GMP function via the FFI to do the hard work. It's hard to see why any of this would be particularly inefficient, except that there's a lot of type-level stuff and you have to go through quite a few typeclasses. You'd think that GHC would be able to compile that pretty efficiently though. - recipModInteger is O(log n), right? Given that -1 is 52435875175126190479447740508185965837690552500527637822603658699938581184512 in Jubjub.F, it might cause slowdowns - if dictionaries do not get inlined, that also can easily result in much less efficient code - FFI calls are unsafe there, so they should be very cheap indeed Given that Jubjub.F is around an order of magnitude slower than F17, I don't think it's something too surprising. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#67 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AASOTJN4NVDZCM3MND7V6GDRL4YWFANCNFSM4ME4OJYA> .

-- *Jakub Zalewski* FUNCTIONAL COMPILERS ENGINEER | POZNAN, POLAND Website: www.iohk.io <https://iohk.io/> Skype: jakubz.pl Twitter: @jakzale PGP Key ID: B7E7CE31 <https://pgp.mit.edu/pks/lookup?op=get&search=0x33D0FF67B7E7CE31> [image: Input Output] <http://iohk.io/> [image: Twitter] <https://twitter.com/InputOutputHK> [image: Github] <https://github.com/input-output-hk> [image: LinkedIn] <https://www.linkedin.com/company/input-output-global> [image: YouTube] <https://www.youtube.com/channel/UCBJ0p9aCW-W82TwNM-z3V2w> [image: Facebook] <https://www.facebook.com/iohk.io/> [image: Reddit] <https://www.reddit.com/r/cardano/> [image: Meetup] <https://www.meetup.com/pro/cardano/> [image: CardanoAnnouncements] <https://t.me/CardanoAnnouncements>

[effectfully]

Actually, I was thinking about -1. Since all these fields are circular,
can we have an optimisation step that tries to remove negative numbers?

Fields are circular, but at least currently field elements represent integers. This is going to be important once #69 is implemented, and we already use the "integer" semantics of field elements in stuff like xs [ i ].

And UX of that would be pretty terrible. Your program works, you change something benign, the optimization no longer fires, the program breaks.