I'm trying to do some math stuff with std.bigint and realized there's no obvious way to calculate the ceil of log2 of a bigint. Help?

On Wednesday, 2 November 2016 at 14:05:50 UTC, pineapple wrote:
> I'm trying to do some math stuff with std.bigint and realized there's no obvious way to calculate the ceil of log2 of a bigint. Help?

How big are your bigints?

On Wednesday, 2 November 2016 at 14:24:42 UTC, Andrea Fontana wrote:
> On Wednesday, 2 November 2016 at 14:05:50 UTC, pineapple wrote:
>> I'm trying to do some math stuff with std.bigint and realized there's no obvious way to calculate the ceil of log2 of a bigint. Help?
>
> How big are your bigints?

I think they'll generally stay between 0 and 2^200

I came up with this, I guess it'll work?

   auto clog2(BigInt number) in{
        assert(number > 0);
    }body{
        uint log;
        auto n = number - 1;
        while(n > 0){
            log++; n >>= 1;
        }
        return log;
    }

On Wednesday, 2 November 2016 at 14:49:08 UTC, pineapple wrote:
> On Wednesday, 2 November 2016 at 14:24:42 UTC, Andrea Fontana wrote:
>> On Wednesday, 2 November 2016 at 14:05:50 UTC, pineapple wrote:
>>> I'm trying to do some math stuff with std.bigint and realized there's no obvious way to calculate the ceil of log2 of a bigint. Help?
>>
>> How big are your bigints?
>
> I think they'll generally stay between 0 and 2^200
>
> I came up with this, I guess it'll work?
>
>    auto clog2(BigInt number) in{
>         assert(number > 0);
>     }body{
>         uint log;
>         auto n = number - 1;
>         while(n > 0){
>             log++; n >>= 1;
>         }
>         return log;
>     }

Why don't you perform a binary search over 200 power of 2?
Something like:

BigInt powers[] = [BigInt(2), BigInt(4), BigInt(8), ...];

And I think you can reduce your search in a smaller interval. Something like:

   string number = "71459266416693160362545788781600";
   BigInt i = number;
   ulong l = number.length;

   ulong approxMin = cast(ulong)((l-1)/0.30103);
   ulong approxMax = cast(ulong)((l)/0.301029);

So you can search on powers[approxMin .. approxMax], if i'm right.

On Wednesday, 2 November 2016 at 15:15:18 UTC, Andrea Fontana wrote:
> Why don't you perform a binary search over 200 power of 2?

Something like: http://paste.ofcode.org/scMD5JbmLMZkrv3bWRmPPT

I wonder if a simple binary search on whole array is faster than search for limits as in this example

PS: If you need ceil, just use the else branch with <= instead of <.

Andrea