Bill Shirley - bshirley - frazerbilt.com
if (Posts < 30) you.read( JavaRanchFAQ);
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Originally posted by Campbell Ritchie:
Welcome to JavaRanch
Please confirm that is your real name; you know about our naming policy.
Apart from using what looks like 21 when you probably mean 2L (please don't use a small l in long literals) I can't see anything wrong with your method. I think you are seeing normal behaviour. It is hardly surprising if it runs slowly; you try calculating 98765198951987984698749187619849516198795 to the power of 548787548794654979845987654694 quickly!
Originally posted by Bill Shirley:
Use Code Tags
Use Code Tags
Use Code Tags
Originally posted by Mike Simmons:
Here's what I've done in the past. Should be fairly fast.
Originally posted by Mike Simmons:
[fred]: Why wouldn't BigInteger's modpow() method work? just pass a 1 for the mod value.
I don't think mod 1 would work - that always returns 0. However you could use mod n where n is any number larger than the number you're modding.
However, SA: there's a big problem with the very idea of taking a BigInteger to a BigInteger power: memory. If you actually need a BigInteger for both those values (as opposed to a long), then the result is going to be very big indeed, and will require a huge amount of memory. (And also a fair amount of time to calculate all the digits, no matter how fast your algorithm.)
However, for the cryptography applications I'm aware of, you don't actually need to calculate the complete result - you just want a certain mod of the result. Basically, you usually want to retain a certain number of lower-order bits, and can afford to omit the higher ones. That allows you so save considerably on both time and memory. And that's exactly what modpow() does, efficiently. You could also modify mo own algorithm above to do this, modding results along the way. But I bet the modpow() version has already been written to be quite efficient. There's an excellent chance that modpow() does exactly what you really need here.
[ November 14, 2008: Message edited by: Mike Simmons ]
I am afraid initials are not acceptable. I shall have to ask you to go to "my profile" and alter your displayed name to match the naming policy.Originally posted by SA AL:
My apologies, I didn't know about the nameing policy. but Yes, those are my initials.
no, its "2l". in small letters.
Originally posted by Mike Simmons:
[fred]: Why wouldn't BigInteger's modpow() method work? just pass a 1 for the mod value.
I don't think mod 1 would work - that always returns 0. However you could use mod n where n is any number larger than the number you're modding.
However, SA: there's a big problem with the very idea of taking a BigInteger to a BigInteger power: memory. If you actually need a BigInteger for both those values (as opposed to a long), then the result is going to be very big indeed, and will require a huge amount of memory. (And also a fair amount of time to calculate all the digits, no matter how fast your algorithm.)
However, for the cryptography applications I'm aware of, you don't actually need to calculate the complete result - you just want a certain mod of the result. Basically, you usually want to retain a certain number of lower-order bits, and can afford to omit the higher ones. That allows you so save considerably on both time and memory. And that's exactly what modpow() does, efficiently. You could also modify mo own algorithm above to do this, modding results along the way. But I bet the modpow() version has already been written to be quite efficient. There's an excellent chance that modpow() does exactly what you really need here.
[ November 14, 2008: Message edited by: Mike Simmons ]
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime. |