Re: Divisibility of a java.math.BigInteger object

In article <BigInteger-20080709161837@xxxxxxxxxxxxxxxxxxxxxxx>,
ram@xxxxxxxxxxxxxxxxxx (Stefan Ram) wrote:

| Supersedes: <BigInteger-20080709154458@xxxxxxxxxxxxxxxxxxxxxxx>

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
.

Relevant Pages

  • Re: odd bases
    ... And 1/2 would be repeating. ... It only matters if divisibility by 2 is important for whatever you are ... Anything using arithmetic modulo n is essentially using base n arithmetic. ... news (dot) post tbrauch com ...
    (sci.math)
  • Re: exam REVIEW...can anyone help me?
    ... over some review problems to prepare for the exam and this program is ... Output is in a new array with element of 1 if odd and 0 if even. ... part d has to do with divisibility, ... there is a remainder or not. ...
    (comp.lang.fortran)
  • Re: Why is 12345678, 85263147, etc. always divisible by 9?
    ... Don't know the divisibility rule fby 9? ... In general, if you have two numbers x and y, and you want to divide ... them by a third number z>0, then: if the remainder when you divide x ... the remainder of dividing x+y by z is the same as the ...
    (sci.math)
  • Re: Wrong-but-not-incorrect code
    ... Iterate as needed. ... > you the remainder for non-multiples.) ... ot 5 (divisibility by 13), ...
    (comp.lang.c)