Mixed int/BigInt foreach interval

Christophe travert at phare.normalesup.org
Thu Sep 29 01:43:32 PDT 2011


bearophile , dans le message (digitalmars.D:145640), a écrit :
> Timon Gehr:
> 
>> I mean, eg. the following is hardly useful:
>> 
>> foreach(i;0..BigInt("10000000000000000000000000"){}
> 
> I'd like a function template like this to work even if T is BigInt:
> 
> T binomial(T)(T n, T k) {
>     if (k > n/2)
>         k = n - k;
>     T bc = n - k + 1;
>     foreach (i; 2 .. k+1)
>         bc = (bc * (n - k + i)) / i;
>     return bc;
> }
> 
> 
> Current workaround: use this instead of the foreach:
> for (T i = 2; i <= k; i++)

That seems to be a very reasonable workarround.
Does
foreach(i; (cast(T) 2) .. k+1) work ?

> Christophe:
> 
>> The copy on write behavior of BigInt makes it very poorly efficient
>> to iterate on. In addition, I guess the compiler won't be able to
>> optimize anything. Someone could say this is a good reason to make the
>> .. syntax on BigInt harder to use.
> 
> I'd like to use BigInts often in D. So some compiler optimizations are welcome here.

BigInt is in the library, not in the language. I hardly see a way the 
compiler could optimize this. At the best, it could recognise that the 
BigInt is wasted at the end of each iteration and destroy/reuse it's 
content right away. Reusing can be hard, since the size of the BigInt 
can get bigger.

The best way to optimize this is at the library level.
Eventually, since iota and BigInt are in the same library, iota could 
provided an overload for BigInt that uses a kind of mutable BigInt. 

BigInt reused the Python idiom of immutable data and copy-on-write. I am 
not sure this is such a good idea in D, where the garbage collector is 
different, types are not all supposed to be immutable, and the 
performance expectations are higher, and optimization opportunities are 
different.

-- 
Christophe



More information about the Digitalmars-d mailing list