## digitalmars.D.learn - Best way to get ceil(log2(x)) of a BigInt?

• pineapple (3/3) Nov 02 2016 I'm trying to do some math stuff with std.bigint and realized
• Andrea Fontana (2/5) Nov 02 2016 How big are your bigints?
• pineapple (14/19) Nov 02 2016 I think they'll generally stay between 0 and 2^200
• Andrea Fontana (12/32) Nov 02 2016 Why don't you perform a binary search over 200 power of 2?
• Andrea Fontana (8/9) Nov 02 2016 Something like: http://paste.ofcode.org/scMD5JbmLMZkrv3bWRmPPT
pineapple <meapineapple gmail.com> writes:
```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?
```
Nov 02 2016
Andrea Fontana <nospam example.com> writes:
```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?

```
Nov 02 2016
pineapple <meapineapple gmail.com> writes:
```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?

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;
}
```
Nov 02 2016
Andrea Fontana <nospam example.com> writes:
```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?

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.
```
Nov 02 2016
Andrea Fontana <nospam example.com> writes:
```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
```
Nov 02 2016