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
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
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?
Nov 02 2016
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 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; }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?
Nov 02 2016
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: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 14:05:50 UTC, pineapple wrote: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; }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?
Nov 02 2016
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