The new `invmod(n, T)` function and even arguments

General Usage
1

I was reading about new features in Julia 1.11 and happened upon this new invmod capability: invmod(n::BitInteger): efficient native modular inverses by StefanKarpinski · Pull Request #52180 · JuliaLang/julia · GitHub .

As someone more accustomed to math than bit-twiddling, I didn’t realize at first that this is doing modular inverses in base 2^N (determined by the max values of the type T) and thus the argument must be odd to have a well-defined inverse. It would be great to add that requirement to the docs, and document what happens when the argument is even (a DomainError exception appears to be the result).

Also, for consistency with other ares where an inverse doesn’t exist (e.g. computing 1/0 and getting Inf), I wonder whether throwing an exception might not be the best option. Is there a suitable non-value in Julia for this situation? That might help callers who’d want to do invmod.(array) on a bunch of values at once, for example.

Finally, I noticed that the unit tests don’t seem to limit themselves to odd values, but they don’t seem to worry about catching the DomainError exception either - how does this work?

2 Likes
2

A documentation PR to clarify this would be welcome, I suspect. The documentation for invmod(n) is here, and you can click the edit button to edit it and submit a PR directly from the browser.

Note that the invmod(n, m) docs explicitly say that an error is thrown if the multiplicative inverse \mod m doesn’t exist, so it would make sense invmod(n) to have a documentation comment in a similar form.

Not if you want to return a machine integers, and returning a different type of value (e.g. Inf or nothing) would not be type-stable.

Yes they do. The loop for a = typemin(T)+true:T(2):typemax(T) goes in steps of 2, so it only covers odd integers. The randomized tests use a = rand(T) | true, where the bitwise or | with true == 1 sets the last bit of a, making it odd.

4 Likes
3

Ah! I was wondering what that | true was doing in there, I overlooked the fact that it was a bitwise operator and not a logical check.

I’ve created a PR here (Add behavior for even values to docs for new invmod(n, T) functions by kenahoo · Pull Request #55531 · JuliaLang/julia · GitHub), thanks for the advice.

4 Likes