On Oct 14, 2007, at 4:37 AM, Eduard de Jong wrote:
Mike,
your approach looks like an example of the general strategy to work
with immutable, value, objects.
1-- all values are represented by immutable objects
2-- Operations are specified by Mutator objects which do NOT
represent a value.
Thanks again for the reply.
This does appear to be the BigInteger strategy. I would still be
interested in some reading related to the considerations for this
strategy.
The separation between values and operations is essential to make
use of the values inherently thread safe. I think that is a
compelling reason to follow these design principles.
In some cases this could very well be compelling. Also would just be
that BigInteger has had some smart people spend some time figuring
out how to do some fairly complicated things with very large numbers.
The convenience of this being done for you is a pretty compelling
reason itself to use it.
However, just as the java collection classes started out thread safe
synchronized, performance was enough of a concern that later on not
synchronized access classes were provided.
I still have basically only one good example that I think pretty well
demonstrates what I am talking about.
One recommended speedup for the code I'm considering is actually to
change the numbers representation. Instead of the usual straight
binary you use a SDR, or signed digital representation. For multiply
if you are stepping through bit by bit to multiply then this
representation gives you fewer set 'bits' that need to be operated
on. So in theory faster.
Someone else's BigInteger version*...
/**
* Computes the Window NAF (non-adjacent Form) of an integer.
* @param width The width <code>w</code> of the Window NAF. The
width is
* defined as the minimal number <code>w</code>, such that for any
* <code>w</code> consecutive digits in the resulting
representation, at
* most one is non-zero.
* @param k The integer of which the Window NAF is computed.
* @return The Window NAF of the given width, such that the
following holds:
* <code>k = ∑<sub>i=0</sub><sup>l-1</sup> k<sub>i</
sub>2<sup>i</sup>
* </code>, where the <code>k<sub>i</sub></code> denote the
elements of the
* returned <code>byte[]</code>.
*/
public byte[] windowNaf(byte width, BigInteger k)
{
// The window NAF is at most 1 element longer than the binary
// representation of the integer k. byte can be used instead
of short or
// int unless the window width is larger than 8. For larger
width use
// short or int. However, a width of more than 8 is not
efficient for
// m = log2(q) smaller than 2305 Bits. Note: Values for m
larger than
// 1000 Bits are currently not used in practice.
byte[] wnaf = new byte[k.bitLength() + 1];
// 2^width as short and BigInteger
short pow2wB = (short)(1 << width);
BigInteger pow2wBI = BigInteger.valueOf(pow2wB);
int i = 0;
// The actual length of the WNAF
int length = 0;
// while k >= 1
while (k.signum() > 0)
{
// if k is odd
if (k.testBit(0))
{
// k mod 2^width
BigInteger remainder = k.mod(pow2wBI);
// if remainder > 2^(width - 1) - 1
if (remainder.testBit(width - 1))
{
wnaf[i] = (byte)(remainder.intValue() - pow2wB);
}
else
{
wnaf[i] = (byte)remainder.intValue();
}
// wnaf[i] is now in [-2^(width-1), 2^(width-1)-1]
// Reduce the WNAF array to its actual length
byte[] wnafShort = new byte[length];
System.arraycopy(wnaf, 0, wnafShort, 0, length);
return wnafShort;
}
There's nothing wrong with this but notice the (looped) BigInteger
immutable instantiations...
BigInteger pow2wBI = BigInteger.valueOf(pow2wB); (OK this
one isn't looped)
BigInteger remainder = k.mod(pow2wBI);
k = k.subtract(BigInteger.valueOf(wnaf[i]));
k = k.shiftRight(1);
So three instantiations each time through the loop and you loop
basically as many times as the number is big, and this is BigInteger.
(Not to mention it is basically a data type so all of this code will
be iterated over many times as the data type is used).
My version is...
private void instantiate(BigInteger bi) {
byte[] k = bi.toByteArray();
S = new byte[bi.bitLength()+1]; // "It is known length is at most
1 more"
int i = S.length - 1; // We reverse index
while (notZero(k)) {
if ((k[k.length-1] & (byte)1) != 0) { // If odd
S[i] = mods(k,wmod);
adjust(k,S[i]);
}
else S[i] = 0;
i--;
div2(k);
}
length = S.length - offset;
lenIdx = S.length - 1;
}
Nothing really better about this code but notice that it does avoid
the BigInteger creation.
byte[] k = bi.toByteArray();
gets the byte array and that is used mutably through out.
Consider as well the adjustment code,
adjust(k,S[i]);
is more or less the same as the original subtract
k = k.subtract(BigInteger.valueOf(wnaf[i]));
But I was able to make mine fairly simple and possibly even more
efficient than BigInteger's because I know the adjustment value will
always be small, definitely less than 32 bits.
So the net result appeared to be that whatever reasons figure in and
to however much an extent (I think profiling is a tricky thing to
make hard and fast cause and effect statements), that mine was both
faster and seemed to use less memory. Speed/memory -> Win/Win. I
found this somewhat compelling as well. For thread concerns a
synchronized could be added somewhere - but performance concerns for
that versus immutable I have no measurements for.
I am currently working on a different supposed optimization that I
think does enough BigInteger math as to make it prohibitively slow.
(It's optimization is that it is supposed to avoid costly modInverse
operations but to me it still even seems to require some of those so
it may prove to not be an optimization at all). If I get past the
small matter of programming of just getting it to work I will then
attempt to see if some of the BigInteger instantiations can be
eliminated and result in a more substantial sized test case and
hopefully again a example of improved Speed/memory.
*Olaf Keller's WnafMultiplier class available cvs from bouncycastle.
http://www.bouncycastle.org, java crypto.
_______________________________________________
Do not post admin requests to the list. They will be ignored.
Java-dev mailing list (email@hidden)
Help/Unsubscribe/Update your Subscription:
http://lists.apple.com/mailman/options/java-dev/email@hidden
