[ruby-core:57338] Re: [ruby-trunk - Feature #8700] Integer#bitsize (actually Fixnum#bitsize and Bignum#bitsize)

I like it. Pretty neat for low level bit brushing stuff.

-- 
Fuad Saud
Sent with Sparrow (http://www.sparrowmailapp.com/?sig)


On Saturday, August 31, 2013 at 3:47 AM, matz (Yukihiro Matsumoto) wrote:

> 
> Issue #8700 has been updated by matz (Yukihiro Matsumoto).
> 
> 
> Accepted. It should be work as 2's complement for negative numbers.
> 
> Matz.
> 
> ----------------------------------------
> Feature #8700: Integer#bitsize (actually Fixnum#bitsize and Bignum#bitsize)
> https://bugs.ruby-lang.org/issues/8700#change-41474
> 
> Author: akr (Akira Tanaka)
> Status: Open
> Priority: Normal
> Assignee: 
> Category: 
> Target version: 
> 
> 
> How about adding Integer#bitsize (actually Fixnum#bitsize and Bignum#bitsize)?
> 
> Integer#bitsize returns the position of the most significant bit in the absolute value.
> (The position of the least significant bit is 1.)
> It returns 0 if no bit set (i.e. the value 0).
> 
> Mathematically, n.bitsize is ceil(log2(abs(n)+1)).
> 
> Sometimes we want to know the size of a integer.
> 
> * Determine the size of an integer in some format.
> Although there are various formats, bitsize is a key property to determine the result size.
> Several examples:
> * If a format is 4 bytes for absolute value, it overflows if 32 <= n.bitsize.
> * If a format is 4 bytes for sign bit with absolute value, it overflows if 31 <= n.bitsize.
> * If a format is 4 bytes for 2's complement format, it overflow if 31 <= n.bitsize && n != -2**31.
> * BER-compressed integer needs (n.bitsize+6)/7 bytes when n > 0.
> BER-compressed integer is an example of VLQ.
> http://en.wikipedia.org/wiki/Variable-length_quantity
> * Elias gamma coding needs 2*n.bitsize-1 bits.
> https://en.wikipedia.org/wiki/Elias_gamma_coding
> * Elias delta coding needs 2*n.bitsize.bitsize+n.bitsize-2 bits.
> https://en.wikipedia.org/wiki/Elias_delta_coding
> 
> * bitsize may be used to estimate the time or space cost of an algorithm.
> For example, the result size of integer multiplication, x*y, is x.bitsize + y.bitsize.
> The number of comparisons of binary search is sorted_array.length.bitsize, etc.
> This is because n.bitsize is an approximation of log2(abs(n)).
> So Math.log2 can be used for this purpose too.
> However bitsize may be preferable if floating point error is not desirable.
> 
> There are several software which has similar feature.
> 
> * Python 3.1 has int.bit_length().
> http://docs.python.org/dev/library/stdtypes.html
> http://docs.python.org/3.1/whatsnew/3.1.html
> http://bugs.python.org/issue3439
> 
> * Java java.math.BigInteger has bitLength() method.
> http://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html#bitLength()
> 
> * Mathematica has BitLength.
> http://reference.wolfram.com/mathematica/ref/BitLength.html
> 
> * GMP has mpz_sizeinbase(n, base).
> http://gmplib.org/manual/Miscellaneous-Integer-Functions.html
> 
> * NetBSD 5.0 has ilog2().
> http://netbsd.gw.com/cgi-bin/man-cgi?ilog2++NetBSD-6.0
> 
> I think there are two concerns for this issue.
> * method name
> * behavior for zero and negative number
> 
> I named the method as bitsize, mainly because
> there is Fixnum#size and Bignum#size.
> However I'm open for other names such as:
> * bitlength
> * numbits
> * ilog2
> * maxbit
> Some names may suggest different behavior, though.
> 
> The behavior for zero and negative number is not trivial.
> 
> Python adopts ceil(log2(abs(n)+1)) but
> Java and Mathematica adopts ceil(log2(n < 0 ? -n : n+1)).
> The difference is absolute number v.s. 2's complement number.
> 
> Some people may prefer ilog2, which name suggests ilog2(0) raise an error.
> 
> I choose ceil(log2(abs(n)+1)). (i.e. absolute number, same as Python).
> I think absolute number is easier to understand than 2's complement for many people.
> 
> I attached the implementation as bitsize.patch.
> The patch implements both Bignum#bitsize and Fixnum#bitsize in bignum.c.
> It is because Fixnum#bitsize uses bitsize macro and it is defined in bignum.c.
> Maybe, the macro should be moved to internal.h and the implementation of
> Fixnum#bitsize should be moved to numeric.c.
> 
> Any comments?
> 
> 
> 
> -- 
> http://bugs.ruby-lang.org/
> 
>