Re: Divisibility of a java.math.BigInteger object

Discussion in 'Java' started by John B. Matthews, Jul 9, 2008.

  1. In article <-berlin.de>,
    -berlin.de (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?


    If BigIntegers are stored in two's-complement form (they are only
    required to behave that way) then getLowestSetBit() might be a faster
    test for divisibility by powers of two.

    Using toString(int radix), you can examine any glyph in a BigInteger's
    representation in any base up to Character.MAX_RADIX. The conversion
    will likely be slower than a remainder, but you only have to do it once
    to check a number of divisibility shortcuts for small integers. Sadly,
    the conversion itself is usually done with a series of divisions, so I
    don't see a net gain.

    Sorry, I lost track of the larger goal.

    > (This is not premature optimization. I already have a program
    > that is too slow, and a profiler showed that it spends a
    > significant amount of time in java.math.BigInteger.remainder:
    > [...]
    > Because the profiler also includes program startup and other
    > phases of the process, the percentage of the
    > java.math.BigInteger.remainder operation is larger then shown
    > above when put in relation to the actual calculation phase.)


    Some Java profilers (NetBeans, Eclispe, others?) let you focus on
    subsets of the code for a clearer picture.

    --
    John B. Matthews
    trashgod at gmail dot com
    home dot woh dot rr dot com slash jbmatthews
     
    John B. Matthews, Jul 9, 2008
    #1
    1. Advertising

  2. John B. Matthews

    Stefan Ram Guest

    "John B. Matthews" <> writes:
    >Some Java profilers (NetBeans, Eclispe, others?) let you focus on
    >subsets of the code for a clearer picture.


    The »Performance Analysis« program by Sun Microsystems, Inc.
    has a panel named »by Caller«. Often a subset of the code can
    by identified by its callers. So one also can use this
    »standard tool« (where »standard« means »by Sun Microsystems,
    Inc.«) for some queries.

    http://java.sun.com/developer/technicalArticles/Programming/perfanal/
     
    Stefan Ram, Jul 9, 2008
    #2
    1. Advertising

  3. In article <-berlin.de>,
    -berlin.de (Stefan Ram) wrote:

    > "John B. Matthews" <> writes:
    > >Some Java profilers (NetBeans, Eclispe, others?) let you focus on
    > >subsets of the code for a clearer picture.

    >
    > The »Performance Analysis« program by Sun Microsystems, Inc.
    > has a panel named »by Caller«. Often a subset of the code can
    > by identified by its callers. So one also can use this
    > »standard tool« (where »standard« means »by Sun Microsystems,
    > Inc.«) for some queries.
    >
    > http://java.sun.com/developer/technicalArticles/Programming/perfanal/


    Thank you for the informative link. I see that Sun's NetBeans' profiler
    uses the hprof format, bit I was surprised that some of the Eclipse
    plugins do not mention it explicitly.

    --
    John B. Matthews
    trashgod at gmail dot com
    home dot woh dot rr dot com slash jbmatthews
     
    John B. Matthews, 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:
    915
  2. nick
    Replies:
    1
    Views:
    31,914
    Eric Sosman
    Oct 26, 2004
  3. Stefan Ram
    Replies:
    0
    Views:
    397
    Stefan Ram
    Jul 9, 2008
  4. Patricia Shanahan
    Replies:
    2
    Views:
    487
    Patricia Shanahan
    Jul 9, 2008
  5. VK
    Replies:
    15
    Views:
    1,238
    Dr J R Stockton
    May 2, 2010
Loading...

Share This Page