Re: Divisibility of a java.math.BigInteger object

Discussion in 'Java' started by Patricia Shanahan, Jul 9, 2008.

  1. Stefan Ram wrote:
    > | Supersedes: <-berlin.de>
    >
    > Calculating the remainder of a java.math.BigInteger object
    > | seems to be slow. To test divisibility by 100, for a number
    > | larger than 100, it would be sufficient and possibly faster to
    > just extract the two least significant digits and compare them
    > with »00«. But I can not directly access the internal
    > representation of a java.math.BigInteger object. Does anyone
    > see a possibility to accelerate such a divisibility test for a
    > java.math.BigInteger object using the same tricks one uses
    > when testing this by mental arithmetic?


    The magnitude of the BigInteger is stored is stored in binary, not
    decimal. If "number" references a BigInteger, number.testBit(0) and
    number.testBit(1) report on the values of the least significant digits
    of its internal representation.

    If at least one of those two least significant bits is one, the number
    is not divisible by four, and therefore is not divisible by 100. If both
    bits are zero, you still need to test for divisibility by 25.

    Alternatively, you could test the last couple of characters of the
    toString result, which is in decimal, so it may be worth measuring which
    is faster, division by 100 or toString. I would guess divisibility, but
    I'm often wrong when I guess at benchmark results.

    Patricia
     
    Patricia Shanahan, Jul 9, 2008
    #1
    1. Advertising

  2. Patricia Shanahan

    Stefan Ram Guest

    Patricia Shanahan <> writes:
    >The magnitude of the BigInteger is stored is stored in binary, not


    Thanks (to both of you, Patricia and rossum).

    I had confused »BigInteger« with »BigDecimal« when I thought
    that it would internally hold a decimal representation.

    >If at least one of those two least significant bits is one, the number
    >is not divisible by four, and therefore is not divisible by 100. If both
    >bits are zero, you still need to test for divisibility by 25.


    I will try this.
     
    Stefan Ram, Jul 9, 2008
    #2
    1. Advertising

  3. Stefan Ram wrote:
    > Patricia Shanahan <> writes:
    >> The magnitude of the BigInteger is stored is stored in binary, not

    >
    > Thanks (to both of you, Patricia and rossum).
    >
    > I had confused »BigInteger« with »BigDecimal« when I thought
    > that it would internally hold a decimal representation.


    Even BigDecimal stores the unscaled magnitude as a BigInteger.

    Patricia
     
    Patricia Shanahan, Jul 9, 2008
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. nick
    Replies:
    0
    Views:
    938
  2. nick
    Replies:
    1
    Views:
    32,098
    Eric Sosman
    Oct 26, 2004
  3. Stefan Ram
    Replies:
    0
    Views:
    404
    Stefan Ram
    Jul 9, 2008
  4. John B. Matthews
    Replies:
    2
    Views:
    558
    John B. Matthews
    Jul 9, 2008
  5. VK
    Replies:
    15
    Views:
    1,332
    Dr J R Stockton
    May 2, 2010
Loading...

Share This Page