`Int` vs `BigInt` for `length` of combinatorial iterators

[mjrodgers]

We have some iterators in EnumerativeCombinatorics that return a BigInt as their length, and a PR review brought up the question of whether this is useful / necessary.

These numbers can get quite large, for example binomial(40,20) is ~ 2^37.

Is an Int always 64 big in Julia or is it sometimes 32 bit depending on the system? And how reasonable is it to work with these iterators? We can collect combinations(30,15) (about 2^27 objects) in about 200 seconds, but about 95% of that is garbage collection time, we can iterate over it in 3 seconds with inplace=true.

[lgoettgens]

Is an Int always 64 big in Julia or is it sometimes 32 bit depending on the system?

It is 32 bit iff you are working on a 32-bit system. And iirc we usually expect that no user of Oscar does that.

[mjrodgers]

Ah okay, in this case we should only use Int, I will make a pull request to fix these.

[lgoettgens]

I would differentiate the following two cases:

1. number_of_combinations(n,k) returns something of arbitrary size (i.e. BigInt or ZZRingElem, whatever of the two we currently have there)
2. length(combinations(n,k)) returns an Int, and will complain via an InexactError if that is not possible

[joschmitt]

I don't understand yet, why throwing an error should be preferred over getting the correct number?

[mjrodgers]

The consideration could be type stability. And also, if it is always a BigInt then doing any arithmetic with this will I think cause all the integers involved to be promoted and lead to lots of needless allocations (since an iterator with this length would be almost completely useless, Julia completely exits with a message of killed if I try to iterate over some combinations with anywhere near to this length even using inplace=true).

[thofma]

Some (hypothetical) application: Look for combinations with specific properties. Then one iterate and abort once something is found. Not sure how realistic this though. No one has complained so far.