ruby-core

Issue #8700 has been updated by akr (Akira Tanaka).

File bitlength.patch added

akr (Akira Tanaka) wrote:

> 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 look out more.

* Go has BitLen.
  http://golang.org/pkg/math/big/#Int.BitLen

* OpenSSL has BN_num_bits.
  http://www.openssl.org/docs/crypto/BN_num_bytes.html

* LibTomMath has mp_count_bits.
  http://libtom.org/

* gcrypt has gcry_mpi_get_nbits.
  http://www.gnupg.org/documentation/manuals/gcrypt/Bit-manipulations.html

* Scala has bitLength.
  http://www.scala-lang.org/api/current/index.html#scala.math.BigInt

* CommonLisp has integer-length.
  http://www.lispworks.com/documentation/HyperSpec/Body/f_intege.htm

* CLN has integer_length.
  http://www.ginac.de/CLN/cln.html#Exact-numbers

They behaves on negative values for absolute value or two's complement as follows.

absolute value, ceil(log2(abs(n)+1)):
  Python (bit_length)
  Go (BitLen)
  GMP (mpz_sizeinbase)
  OpenSSL (BN_num_bits)
  LibTomMath (mp_count_bits)
  gcrypt (gcry_mpi_get_nbits)

two's complement, ceil(log2(n < 0 ? -n : n+1)):
  Java (bitLength)
  Scala (bitLength)
  Mathematica (BitLength)
  CommonLisp (integer-length)
  CLN (integer_length)

It seems "bit length" is more common than other names.
So I changed the method name to "bitlength".

Both absolute value and two's complement are common.
I think it's difficult to say one is better.
(My patch's bitlength is absolute value.)

How do you think, matz?

----------------------------------------
Feature #8700: Integer#bitsize (actually Fixnum#bitsize and Bignum#bitsize)
https://bugs.ruby-lang.org/issues/8700#change-40795

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/

Thread

Prev Next

In This Thread

Prev Next

[#56298] [ruby-trunk - Bug #8715][Open] openssl mkmf.log filled with other data — "mpapis (Michal Papis)" <mpapis@...>

[#56316] [ruby-trunk - Bug #8717][Open] Negation of a rational/imaginary number literal isn't working — "takuto_h (Takuto Hayashi)" <redmine@...>

[#56317] [ruby-trunk - Bug #8718][Open] unary minus with literal suffix of Rational/Complex — "no6v (Nobuhiro IMAI)" <nov@...>

[#56323] [ruby-trunk - Bug #8720][Open] ECB mode seems to be broken — "netjunki (Ben Lau)" <benjamin.a.lau@...>

[#56326] [ruby-trunk - Bug #8721][Open] require digest.so on OSX — "mpapis (Michal Papis)" <mpapis@...>

[#56329] [ruby-trunk - Bug #8722][Assigned] Refinements remain active beyond the end of an evaled string — "charliesome (Charlie Somerville)" <charliesome@...>

[#56333] [CommonRuby - Feature #8723][Open] Array.any? predicate returns true for empty array. — "nurettin (Nurettin Onur TUGCU)" <onurtugcu@...>

[#56341] [ruby-trunk - Bug #8724][Open] MinGW: ConverterNotFoundError test failure — "luislavena (Luis Lavena)" <luislavena@...>

[#56342] [ruby-trunk - Feature #8725][Open] Possibility to get a signal handler without changing it — "bdimych (Dmitry Bolshakov)" <bdimych@...>

[#56364] ANN: Developer Meeting — Aaron Patterson <tenderlove@...>

[#56365] [ruby-trunk - Bug #8728][Open] strio_substr can put invalid pointer into substring — "headius (Charles Nutter)" <headius@...>

[#56367] [ruby-trunk - Bug #8729][Open] Fix character literals in documentation — "henrikhodne (Henrik Hodne)" <me@...>

[#56368] [ruby-trunk - Bug #8730][Open] "rescue Exception" rescues Timeout::ExitException — "takiuchi (Genki Takiuchi)" <[email protected]>

[#56375] [ruby-trunk - Bug #8732][Open] Docs for rss/0.9.rb — "steveklabnik (Steve Klabnik)" <steve@...>

[#56383] [ruby-trunk - Bug #8735][Open] Enumerator::Lazy#zip behaves differently from Enumerable#zip when yield with non-single argument — "kachick (Kenichi Kamiya)" <kachick1@...>

[#56384] [Archive91 - Backport #8736][Open] [BUG] Bus Error — "nijikon (Tomasz Pajor)" <nikon@...>

[#56387] [ruby-trunk - Bug #8737][Open] [BUG] Bus Error — "nijikon (Tomasz Pajor)" <nikon@...>

[#56389] [ruby-trunk - Feature #8738][Open] Integer#single_bit? (Actually Fixnum#single_bit? and Bignum#single_bit?) — "akr (Akira Tanaka)" <akr@...>

[#56392] [ruby-trunk - Bug #8740][Open] Documentation for RSS 1.0 and 2.0 — "steveklabnik (Steve Klabnik)" <steve@...>

[#56407] [ruby-trunk - misc #8741][Open] email notification on bugs.ruby-lang.org is broken — "rits (First Last)" <redmine@...>

[#56414] [ruby-trunk - Bug #8745][Open] Add documentation for RSS::Utils — "steveklabnik (Steve Klabnik)" <steve@...>

[#56423] [ruby-trunk - Bug #5772] Segmentation Fault on Mac (crash) — "naruse (Yui NARUSE)" <naruse@...>

[#56433] [ruby-trunk - Feature #8748][Open] Integer#popcount (Fixnum#popcount and Bignum#popcount) — "akr (Akira Tanaka)" <akr@...>

[#56437] [ruby-trunk - Bug #8750][Open] unit test fix for CVE-2013-4073 seems to be incomplete — "terceiro (Antonio Terceiro)" <terceiro@...>

[#56439] [ruby-trunk - Bug #8742] JSON.parse can not handle tab in string — "jacknagel (Jack Nagel)" <redmine@...>

[#56440] [ruby-trunk - Bug #8742] JSON.parse can not handle tab in string — "henrikhodne (Henrik Hodne)" <me@...>

[#56443] [ruby-trunk - Bug #8742][Rejected] JSON.parse can not handle tab in string — "naruse (Yui NARUSE)" <naruse@...>

[#56447] Reminder: Developer Meeting August 9th, 23:00 UTC — Aaron Patterson <tenderlove@...>

[#56449] [CommonRuby - Feature #8751][Open] Add offsets to method#source_location — "tenderlovemaking (Aaron Patterson)" <tenderlove@...>

[#56454] [ruby-trunk - Bug #8754][Open] Stop checking for old REXML versions — "steveklabnik (Steve Klabnik)" <steve@...>

[#56456] [ruby-trunk - Bug #8755][Open] 'Document' RSS::Trackback — "steveklabnik (Steve Klabnik)" <steve@...>

[#56467] [ruby-trunk - Bug #8759][Open] Error compiling miniruby — "spastorino (Santiago Pastorino)" <santiago@...>

[#56470] [ruby-trunk - Bug #8760][Open] irb automatically exists after opening — "spastorino (Santiago Pastorino)" <santiago@...>

[#56471] [ruby-trunk - Feature #8761][Open] Binding#local_variable_get, set, defined? — "ko1 (Koichi Sasada)" <redmine@...>

[#56478] [ruby-trunk - Bug #8762][Open] CFLAGS and LDFLAGS are not set properly in Makefile when they are already set as environment variables — "charliesome (Charlie Somerville)" <charliesome@...>

[#56480] [ruby-trunk - Bug #8753] __FILE__.encoding is wrong — "ko1 (Koichi Sasada)" <redmine@...>

[#56489] [ruby-trunk - Bug #8753] __FILE__.encoding is wrong — "nobu (Nobuyoshi Nakada)" <nobu@...>

[#56493] [ruby-trunk - Bug #8756] SEGFAULT caused by `p Struct.new(:q?).instance_methods` — "phasis68 (Heesob Park)" <phasis@...>

[#56494] [ruby-trunk - Bug #8763][Open] Error in improve the docs webpage — "markijbema (Mark IJbema)" <markijbema@...>

[#56497] [ruby-trunk - Bug #8756][Assigned] SEGFAULT caused by `p Struct.new(:q?).instance_methods` — "Glass_saga (Masaki Matsushita)" <glass.saga@...>

[#56498] [ruby-trunk - Bug #8764][Assigned] Test failure introduced by r42468 — "luislavena (Luis Lavena)" <luislavena@...>

[#56513] [ruby-trunk - Feature #8765][Open] Literal for symbol with interpolation — "sawa (Tsuyoshi Sawada)" <sawadatsuyoshi@...>

[#56514] [ruby-trunk - Bug #8766][Open] RDoc documentation bug: Symbol literal — "sawa (Tsuyoshi Sawada)" <sawadatsuyoshi@...>

[#56517] Re: [ruby-cvs:49638] zzak:r42496 (trunk): * lib/time.rb: [DOC] Document constants by @markijbema [Fixes GH-377] — Tanaka Akira <akr@...>

[#56518] [ruby-trunk - Bug #8767][Open] IO.copy_stream should write in binary mode. — "godfat (Lin Jen-Shin)" <godfat@...>

[#56521] [ruby-trunk - Bug #8768][Open] [PATCH] tempfile: undefine finalizer on unlink — "normalperson (Eric Wong)" <normalperson@...>

[#56523] [ruby-trunk - Bug #8769][Open] [PATCH] process.c (rb_fork_internal): remove cloexec setting — "normalperson (Eric Wong)" <normalperson@...>

[#56524] [ruby-trunk - Bug #8770][Open] [PATCH] process.c: avoid EINTR from Process.spawn — "normalperson (Eric Wong)" <normalperson@...>

[#56525] [ruby-trunk - Bug #8771][Open] Start does not use proxy configuration form ENV variables — "sjltaylor (Sam Taylor)" <sjltaylor@...>

[#56532] Re: [ruby-cvs:49642] charliesome:r42500 (trunk): * doc/syntax/literals.rdoc: Use single quotes instead of double quotes — Zachary Scott <e@...>

[#56536] [ruby-trunk - Feature #8772][Open] Hash alias #| merge, and the case for Hash and Array polymorphism — "trans (Thomas Sawyer)" <redmine@...>

[#56539] Developers Meeting Summary for 2013-08-09 — Aaron Patterson <tenderlove@...>

[#56541] Next developer's meeting — Aaron Patterson <tenderlove@...>

[#56543] [ruby-trunk - Bug #8773][Open] Binding#local_variables should work like #local_variable_set and #local_variable_get — "jackdanger (Jack Danger)" <ruby@...>

[#56544] [ruby-trunk - Bug #8774][Open] rb_file_dirname return wrong encoding string when dir is "." — jiayp@... (贾 延平) <jiayp@...>

[#56545] [ruby-trunk - Bug #8775][Open] Dir.getwd's encoding is wrong — jiayp@... (贾 延平) <jiayp@...>

[#56547] [ruby-trunk - Bug #8776][Open] script_name's encoding is wrong — jiayp@... (贾 延平) <jiayp@...>

[#56551] [CommonRuby - Feature #8777][Open] Process.mach_absolute_time — "tenderlovemaking (Aaron Patterson)" <tenderlove@...>

[#56557] Re: Welcome to our (ruby-core ML) You are added automatically — tiansheng li <lts123124@...>

[#56562] [ruby-trunk - Bug #8778][Assigned] lib/test/ documentation is too weak — "zzak (Zachary Scott)" <e@...>

[#56567] [ruby-trunk - Feature #8780][Assigned] DBM#to_h alias for #to_hash — "zzak (Zachary Scott)" <e@...>

[#56569] [ruby-trunk - Feature #8781][Open] Use require_relative() instead of require() if possible — "ko1 (Koichi Sasada)" <redmine@...>

[#56586] [ruby-trunk - Bug #8758][Assigned] Add initial documentation for SSLServer — "zzak (Zachary Scott)" <e@...>

[#56588] [ruby-trunk - Bug #8758] Add initial documentation for SSLServer — "zzak (Zachary Scott)" <e@...>

[#56590] [ruby-trunk - Bug #8783][Open] ruby 1.9/2.0 crash on exit on FreeBSD/powerpc64 — "chmeee (Justin Hibbits)" <chmeeedalf+ruby@...>

[#56609] [ruby-trunk - Bug #8784][Open] CSV - Empty fields are discarded when col_sep is a space — "grim7reaper (Sylvain Laperche)" <sylvain.laperche@...>

[#56633] [Backport 200 - Backport #8787][Open] Backport RubyGems 2.0.7 — "drbrain (Eric Hodel)" <[email protected]>

[#56634] [ruby-trunk - Feature #8788][Open] use eventfd on newer Linux instead of pipe for timer thread — "normalperson (Eric Wong)" <normalperson@...>

[#56640] [ruby-trunk - Bug #8789][Open] File.expand_path(File.dirname(__FILE__)) return wrong encoded result — jiayp@... (贾 延平) <yanping_jia@...>

[#56642] [Backport93 - Backport #8791][Assigned] Please backport r36620 — "ktsj (Kazuki Tsujimoto)" <kazuki@...>

[#56644] [ruby-trunk - Bug #8792][Open] HP-UX needs sys/pstat.h for missing/setproctitle.c — "michal@... (Michal Rokos)" <michal@...>

[#56645] [ruby-trunk - Feature #8793][Open] Ruby 2.0 and Threads under HPUX — "michal@... (Michal Rokos)" <michal@...>

[#56646] [ruby-trunk - Bug #8794][Open] Ruby on Rails — "xiongxoy (Xiong Zhou)" <xiong.xoy@...>

[#56648] [ruby-trunk - Bug #8795][Open] "Null byte in string error" on Marshal.load — "mml (McClain Looney)" <m@...>

[#56658] [ruby-trunk - Feature #8796][Open] Use GMP to accelerate Bignum operations — "akr (Akira Tanaka)" <akr@...>

[#56661] Re: [ruby-cvs:49733] eregon:r42591 (trunk): * process.c (rb_clock_gettime): document CLOCK_REALTIME and — Zachary Scott <e@...>

[#56672] Re: [ruby-cvs:49733] eregon:r42591 (trunk): * process.c (rb_clock_gettime): document CLOCK_REALTIME and — Tanaka Akira <akr@...>

[#56701] [ruby-trunk - Bug #8797][Open] Intermittent Segfault on 2.0.0-p247 when running 'bundle install' — "joevandyk (Joe Van Dyk)" <joe@...>

[#56705] [ruby-trunk - Bug #8798][Open] Document all constants in lib/rss/rss.rb — "steveklabnik (Steve Klabnik)" <steve@...>

[#56707] [ruby-trunk - Bug #8800][Open] Nodoc legacy constant — "steveklabnik (Steve Klabnik)" <steve@...>

[#56480] [ruby-trunk - Bug #8753] FILE.encoding is wrong — "ko1 (Koichi Sasada)" <redmine@...>

[#56489] [ruby-trunk - Bug #8753] FILE.encoding is wrong — "nobu (Nobuyoshi Nakada)" <nobu@...>

[#56544] [ruby-trunk - Bug #8774][Open] rb_file_dirname return wrong encoding string when dir is "." — jiayp@... (贾延平) <jiayp@...>

[#56545] [ruby-trunk - Bug #8775][Open] Dir.getwd's encoding is wrong — jiayp@... (贾延平) <jiayp@...>

[#56547] [ruby-trunk - Bug #8776][Open] script_name's encoding is wrong — jiayp@... (贾延平) <jiayp@...>

[#56640] [ruby-trunk - Bug #8789][Open] File.expand_path(File.dirname(FILE)) return wrong encoded result — jiayp@... (贾延平) <yanping_jia@...>