Renaming of bigint.divisible_2exp_p() and bigint.congruent_2exp_p()

Hello,

I would like to rename the bigint.divisible_2exp_p() function to bigint.isDivisibleByPowerOf2() / bigint.isDivisibleBy2exp() and similarly for congruent_2exp_p.
These function return Boolean values.

Issue Link: [Library Stabilization] Should these BigInteger methods return booleans?

I need some developers and users to share their opinion on the same and help us decide the best name for these methods.

Thanks,
-Yash

Initially, I liked the idea of isDivisibleByPowerOf2(), but after reading the documentation, isDivisibleBy2exp() makes more sense to me since it is checking whether or not it is divisible by 2^b, so that would be my vote.

That being said, I would be open to other name proposals, this one just seems particularly obfuscated and difficult to come up with a good, descriptive name. Either way, isDivisibleBy2exp() is definitely an upgrade from divisible_2exp_p() to me.

2 Likes

At first, I liked the "isDivisibleByPowerof2" because it seemed more readable, but that was based on an assumption that it was answering the question "is it divisible by some power of 2". Reading the GMP page, I think I'm understanding it to take k as an argument and to answer the question "is it divisible by 2**k" (?).

With that understanding, I think that myBigInt.isDivisibleBy2exp(k) reads slightly nicer, though I don't think we use exp in this way in other places that I can think of (since ** would be the infix operator and 2 is embedded in the method name). So another alternative would be myBigInt.isDivisibleBy2pow(k) which reads slightly cleaner to me.

However, that has the downside of not working as nicely for congruent_2exp_p I think because another argument would come between the ( and the k?

This is a case where I'd look at other languages that provide a pretty interface to GMP via a bigint type to see whether they've come up with something clever that I'm not thinking of.

-Brad

[edit: PS — "jinx" Ben! :smiley: ]

1 Like

No strong opinions here. But if we were to go with "2exp" names, shouldn't it be capitalized as "2Exp" ?

I had the same reaction to isDivisibleByPowerOf2 as Ben and Brad (that is being a better name) until I read their responses are realized the function takes an argument.

Looks like in the math libraries we go with exp over pow (e.g. exp2) so I think I'd stay with that precedent.

I'm not an expert in these math libraries but I wonder why we have need that method in the first place. I assume we (or rather GMP) is doing some kind of magic in BigInteger's implementation to make that calculation more efficient compared to whatever we generate for:

myBigInt % exp2(k) == 0

But that seems like it would be the sort of thing that would be simple enough to write a peephole optimization for.

I'm getting off track here though. Whatever you end up coming up with is definitely an improvement over divisible_2exp_p.

If I were to argue against this, I might say that since exp is a prefix operation and this "reads" like an infix term given the 2 in the name and argument, that it's OK to differ from it. That said, I don't know how much I believe my argument in that, in reviewing the Math module if you were to say "let's rename exp to pow", I'd probably also be a big fan (though I think the routine is redundant with **? In which case, I might be even more inclined to just get rid of it to avoid having two ways of saying the same thing).

I assume we (or rather GMP) is doing some kind of magic in BigInteger's implementation to make that calculation more efficient compared to whatever we generate for:

I tend not to second-guess GMP, so giving it the benefit of the doubt: My assumption is that it does something like "check that all the bits beneath the one representing 2**k are 0" which is much faster than a general mod operation. In order to peephole it in %, I think you'd have to scan k at execution time to see whether it contained just a single 1 bit, right? And if the k itself can be stored using a bigint, that could be a very expensive operation? (and since % is already painfully expensive, maybe nobody wants to add overhead to it?) Or, maybe I'm wrong and GMP has already peepholed it but keeps this around for old-timers who got burnt by mod or don't trust optimizations that they can't see?

-Brad

in reviewing the Math module if you were to say "let's rename exp to pow", I'd probably also be a big fan

I'd be for that as well.

I just googled for exp() in Python, C++, C#, and Java and it looks like the precedent is that exp() is used exclusively for computing something raised to e, like: e^x; where pow is the general method for computing x^y. So by that argument maybe its best to stay way from the term exp unless it has something to do with Euler's constant or natural logarithms.

its best to stay way from the term exp unless it has something to do with Euler's constant or natural logarithms.

That's my intuition as well, and why I said I'd support the renaming, but ... oh wait, that's what our exp() does as well. Who got us off onto this wrong path?

Oh, I see, you were only talking about exp2 not exp. So we'd want to use divisibleByExp2 rather than divisibleBy2Exp if anything. But divisibleBy2pow (or ...Pow) sounds better to most of us anyway, so maybe we should do that?

And then correcting my earlier statement, exp() isn't redundant with **, but pow() would be if we supported it, but we don't (probably for this reason).

Whew,
-Brad

1 Like

Oh, I see, you were only talking about exp2 not exp.

Yeah that's what I was focused on; although in my comment I compared it against a non-existent pow so I guess that's where we got off track.

Looking at the doc I see exp2 and ldexp (returns x * 2**n) are the two places we use exp in a manner that doesn't use 'e'.

Funny enough we do have a couple overloads of a function logBasePow2 so the term pow does show up there: Math — Chapel Documentation 1.25

But I suppose these are conversations to have when we do the module review for Math.

One thing to note is that the current plan is for the argument to the
function to be named exp (which matches names we chose for other
argument renames in the module). Should we change the name of those
arguments to match? Or does it make sense to leave the arguments named
exp and change the method name in this way?

Thanks,
Lydia

That's an interesting question. My gut reaction is "What is this thing?" "Well, it's the exponent." "OK, so then exp seems like a reasonable abbreviation for that. But is there an even more technical mathy term for the k in x**k that we could consider instead?

Others may not have seen it, but on your math review module issue, I proposed that maybe we could/should replace exp2() with simply requiring the user to write 2**k, which I believe should be similarly optimized for that case since we can cue off of the param-ness of 2. We could take that one step further and remove exp(), replacing it with e**k, where the implementation would call C exp() (noting in the docs that "this is how one does the equivalent of exp() in other languages in Chapel").

-Brad

PS — I also have no problem with supporting a routine like we do named exp() and a named argument named exp, so the above are more trying to think of ways of avoiding it rather than anything I'm deeply worried about personally.

The k in a n**k expression is mathematically referred as the Exponent (exp).
So, using exp in the method name and for the argument would lead to any inaccurate representation of the method and its argument.
On the other hand, using pow as @bradcray had earlier mentioned would also not lead to any improper representation.
Both seem to be pretty strong candidates, but since we had already named the argument exp, I would incline towards isDivisibleBy2exp.

Thanks,
-Yash

I feel differently and would call the argument exp but lean more on pow in the method name itself. Specifically, in English, I might say "is divisible by 2 to the power of (k)" or "...2 to the (k)" but would never say "2 to the exponent of (k)". For that reason, I lean more towards isDivisibleBy2pow(exp=k) (where I'm never sure whether I prefer a capital Pow or lowercase pow after a numeral. I know that @stonea has discussed the tensions here before, and assume Engin prefers Pow above, but can never remember the degree to which we've agreed upon a convention vs. are continuing to dither about it).

-Brad

I guess in that case, if we follow the camelCase convention, then Pow seems like the better choice.