Feature #8553

Bignum#size (and Fixnum#size)

Added by Akira Tanaka 10 months ago. Updated 9 months ago.

[ruby-core:55578]
Status:Closed
Priority:Normal
Assignee:-
Category:core
Target version:2.1.0

Description

How about changing Bignum#size to a well defined behavior?

Recently I changed Bignum implementation to use 128 bit integer type
if the type is available. (r41379)

After that, rubyspec fails with Bignum#size as follows:

| 1)
| Bignum#size returns the number of bytes in the machine representation in multiples of four FAILED
| Expected 16
| to equal 12
|
http://a.mrkn.jp/~mrkn/chkbuild/mavericks/ruby-trunk-m64-o3/log/20130620T231101Z.log.html.gz

I think this failure itself is not a problem.
This is just an over-specification of rubyspec.
Actually the test also fails before r41379 on platforms which doesn't support 64 bit integer type.

It is because the Bignum#size returns multiples of sizeof(BDIGIT), not 4.
sizeof(BDIGIT) can be 2 or 4 before r41379 or 8 since r41379.
The test only considers platforms sizeof(BDIGIT) is 4.

However this test failure reminds me that I always felt that current
Bignum#size (and Fixnum#size) behavior is not useful.

I guess almost all people doesn't interest sizeof(BDIGIT).

So I'd like to change Bignum#size to return number of bytes.
It means val.size returns n if val is a Bignum and
256n <= abs(val) < 256(n+1).

One exception is that val.size returns 0 if val is Bignum zero.

My considerations:

  • The above Bignum#size behavior is based on absolute values, abs(n).
    This is compatible to current behavior and easy to understand.
    There are other possibilities: exception on negative values and
    definition on 2's complement value.
    I think exception is too different from current behavior.
    A definition based on 2's complement is difficult to treat sign bits.

  • Bignum#size returns number of bytes, not bits.
    I think some method which returns number of bits may be useful but
    it is different from current Bignum#size.
    It is better to name another one, such as bitsize and it is not this issue.

  • Fixnum#size is difficult to change.
    Currently Fixnum#size returns sizeof(long).
    Some programs, mspec for example, uses it to obtain a word size.
    So it is difficult to change because compatibility.
    However I doubt such use is correct.
    If a program want to detect 64bit platform, Fixnum#size should not be used
    because it returns 4 on LLP64 platforms (64bit Windows).
    It is better to use [0].pack("l!").size for sizof(long) and
    [nil].pack("p").size for sizeof(char *).

    However some people may hope Fixnum and Bignum consistent.
    For that purpose, Fixnum#size should also be changed same way.
    It will breaks some applications, though.

Any opinion?

bignum-size-abs-bytewise.patch Magnifier (364 Bytes) Akira Tanaka, 06/24/2013 01:28 PM


Related issues

Related to CommonRuby - Feature #8568: Introduce RbConfig value for native word size, to avoid F... Closed 06/25/2013

Associated revisions

Revision 42204
Added by Akira Tanaka 9 months ago

  • bignum.c (rbbigsize): Return the bignum "bytewise" size. [Feature #8553] This is accepted by matz on DevelopersMeeting20130727Japan.

History

#1 Updated by Charles Nutter 10 months ago

In JRuby, Bignum#size is implemented using Java's BigInteger.bitLength().

bitLength doco:

public int bitLength()
Returns the number of bits in the minimal two's-complement representation of this BigInteger, excluding a sign bit. For positive BigIntegers, this is equivalent to the number of bits in the ordinary binary representation. (Computes (ceil(log2(this < 0 ? -this : this+1))).

Implementation in JRuby:

@JRubyMethod(name = "size")
public IRubyObject size() {
    return getRuntime().newFixnum((value.bitLength() + 7) / 8);
}

This leads to the deviation you see in RubySpec, where JRuby and Rubinius differ from MRI on various Bignum sizes.

Perhaps the least impact and most value would be to reimplement MRI's Bignum#size in terms of actual 2's complement bit length, the same way as JRuby (and apparently Rubinius)?

RE: Fixnum#size... I think Ruby should introduce a new constant for native word size, and encourage people to use it.

#2 Updated by Akira Tanaka 10 months ago

In JRuby, Bignum#size is implemented using Java's BigInteger.bitLength().
...
Returns the number of bits in the minimal two's-complement representation of this BigInteger, excluding a sign bit. For positive BigIntegers, this is equivalent to the number of bits in the ordinary binary representation. (Computes (ceil(log2(this < 0 ? -this : this+1))).

I think two's complement representation excluding a sign bit is not familiar for most people.

Especially Bignum#size is bytewise, unlike Java's BigInteger.bitLength().
So it is not useful for calculating required number of bytes as two's complement signed integers.

This leads to the deviation you see in RubySpec, where JRuby and Rubinius differ from MRI on various Bignum sizes.

We should ignore RubySpec.

Perhaps the least impact and most value would be to reimplement MRI's Bignum#size in terms of actual 2's complement bit length, the same way as JRuby (and apparently Rubinius)?

It seems Rubinius uses absolute value.

% bin/rbx -ve '
1.upto(200) {|n|
v = (1<<n)
a = [(-v-1).size, (-v).size, (-v+1).size, (v-1).size, v.size, (v+1).size]
p [n, a] if a.uniq.length != 1
}'
rubinius 2.0.0.rc1 (1.8.7 854aef25 yyyy-mm-dd JI) [x86_64-unknown-linux-gnu]
[64, [9, 9, 8, 8, 9, 9]]
[72, [10, 10, 9, 9, 10, 10]]
[80, [11, 11, 10, 10, 11, 11]]
[88, [12, 12, 11, 11, 12, 12]]
[96, [13, 13, 12, 12, 13, 13]]
[104, [14, 14, 13, 13, 14, 14]]
[112, [15, 15, 14, 14, 15, 15]]
[120, [16, 16, 15, 15, 16, 16]]
[128, [17, 17, 16, 16, 17, 17]]
[136, [18, 18, 17, 17, 18, 18]]
[144, [19, 19, 18, 18, 19, 19]]
[152, [20, 20, 19, 19, 20, 20]]
[160, [21, 21, 20, 20, 21, 21]]
[168, [22, 22, 21, 21, 22, 22]]
[176, [23, 23, 22, 22, 23, 23]]
[184, [24, 24, 23, 23, 24, 24]]
[192, [25, 25, 24, 24, 25, 25]]
[200, [26, 26, 25, 25, 26, 26]]

It seems (-(1 << n)).size == (1 << n).size for all n.

I implemented a patch as my first proposal (absolute value).

How do you think, matz or nurse?

RE: Fixnum#size... I think Ruby should introduce a new constant for native word size, and encourage people to use it.

It is another issue.
However I guess several developers may oppose new Fixnum dependent features
as https://bugs.ruby-lang.org/issues/7517

#3 Updated by Charles Nutter 10 months ago

akr (Akira Tanaka) wrote:

I think two's complement representation excluding a sign bit is not familiar for most people.

Especially Bignum#size is bytewise, unlike Java's BigInteger.bitLength().
So it is not useful for calculating required number of bytes as two's complement signed integers.

I guess the question is: what should Bignum#size actually mean? The minimal representation? The actual byte size being used in a given Bignum object? bitLength goes along with minimal representation here.

We should ignore RubySpec.

I have no opinion here, but the Bignum#size spec does not appear to be particularly useful. That may simply be because Bignum#size is not particularly useful :-)

It seems Rubinius uses absolute value.

% bin/rbx -ve '
1.upto(200) {|n|
v = (1<<n)
a = [(-v-1).size, (-v).size, (-v+1).size, (v-1).size, v.size, (v+1).size]
p [n, a] if a.uniq.length != 1
}'
rubinius 2.0.0.rc1 (1.8.7 854aef25 yyyy-mm-dd JI) [x86_64-unknown-linux-gnu]
[64, [9, 9, 8, 8, 9, 9]]
[72, [10, 10, 9, 9, 10, 10]]
[80, [11, 11, 10, 10, 11, 11]]
[88, [12, 12, 11, 11, 12, 12]]
[96, [13, 13, 12, 12, 13, 13]]
[104, [14, 14, 13, 13, 14, 14]]
[112, [15, 15, 14, 14, 15, 15]]
[120, [16, 16, 15, 15, 16, 16]]
[128, [17, 17, 16, 16, 17, 17]]
[136, [18, 18, 17, 17, 18, 18]]
[144, [19, 19, 18, 18, 19, 19]]
[152, [20, 20, 19, 19, 20, 20]]
[160, [21, 21, 20, 20, 21, 21]]
[168, [22, 22, 21, 21, 22, 22]]
[176, [23, 23, 22, 22, 23, 23]]
[184, [24, 24, 23, 23, 24, 24]]
[192, [25, 25, 24, 24, 25, 25]]
[200, [26, 26, 25, 25, 26, 26]]

It seems (-(1 << n)).size == (1 << n).size for all n.

JRuby is the same result as Rubinius except for (-(1<<n)).size, which probably reflects the JVM excluding the sign bit (?).

jruby 1.7.5.dev (1.9.3p392) 2013-06-23 0356e58 on OpenJDK 64-Bit Server VM 1.8.0-b72-20130124 +indy [darwin-x86_64]
[64, [9, 8, 8, 8, 9, 9]]
[72, [10, 9, 9, 9, 10, 10]]
[80, [11, 10, 10, 10, 11, 11]]
[88, [12, 11, 11, 11, 12, 12]]
[96, [13, 12, 12, 12, 13, 13]]
[104, [14, 13, 13, 13, 14, 14]]
[112, [15, 14, 14, 14, 15, 15]]
[120, [16, 15, 15, 15, 16, 16]]
[128, [17, 16, 16, 16, 17, 17]]
[136, [18, 17, 17, 17, 18, 18]]
[144, [19, 18, 18, 18, 19, 19]]
[152, [20, 19, 19, 19, 20, 20]]
[160, [21, 20, 20, 20, 21, 21]]
[168, [22, 21, 21, 21, 22, 22]]
[176, [23, 22, 22, 22, 23, 23]]
[184, [24, 23, 23, 23, 24, 24]]
[192, [25, 24, 24, 24, 25, 25]]
[200, [26, 25, 25, 25, 26, 26]]

So then, JRuby and Rubinius mostly agree on Bignum#size being an absolute value.

RE: Fixnum#size... I think Ruby should introduce a new constant for native word size, and encourage people to use it.

It is another issue.
However I guess several developers may oppose new Fixnum dependent features
as https://bugs.ruby-lang.org/issues/7517

Definitely a separate issue. I will file it as such. I don't see it being Fixnum-related at all...it's really to get people to stop using Fixnum#size to determine the native word size, and have something official for that.

#4 Updated by Akira Tanaka 10 months ago

2013/6/25 headius (Charles Nutter) headius@headius.com:

Issue #8553 has been updated by headius (Charles Nutter).

I guess the question is: what should Bignum#size actually mean? The minimal representation? The actual byte size being used in a given Bignum object? bitLength goes along with minimal representation here.

The answer for the question is not clear.
However, I think no one expects multiples of sizeof(BDIGIT).

JRuby is the same result as Rubinius except for (-(1<<n)).size, which probably reflects the JVM excluding the sign bit (?).

It is the difference between absolute value and two's complements.
--
Tanaka Akira

#5 Updated by Yui NARUSE 10 months ago

  • Due date set to 08/31/2013
  • Category set to core
  • Target version set to 2.1.0

#6 Updated by Akira Tanaka 9 months ago

  • Status changed from Open to Closed
  • % Done changed from 0 to 100

This issue was solved with changeset r42204.
Akira, thank you for reporting this issue.
Your contribution to Ruby is greatly appreciated.
May Ruby be with you.


  • bignum.c (rbbigsize): Return the bignum "bytewise" size. [Feature #8553] This is accepted by matz on DevelopersMeeting20130727Japan.

Also available in: Atom PDF