Granny's Programming Pearls "inside of every large program is a small program struggling to get out" JavaRanch.com/granny.jsp
programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# BigInteger Peformance

Mark Udstrand
Greenhorn
Posts: 4
I am calculating h/g^x1 in Zp. I have java code that generates the correct value, but it run exponentially slower as the numbers get bigger, and I am not sure why I am seeing such a dramatic slow down. The code is as follows;

How can this be changed to make the performance linear instead of exponential?

Campbell Ritchie
Marshal
Posts: 56545
172
Welcome to the Ranch , even though you resisted posting for the best part of five years!

How do you know it is running in exponential time? What sort of performance figures do you have?
Your base enlarges continually; it has something like 200 digits in (too long for the screen, and you can see from above how to split such lines), so its length would increase by 200 digits every iteration.

Mike Simmons
Ranch Hand
Posts: 3090
14
I did a quick timing test and it looks to me like the run time per iteration is increasing linearly - which would make the overall runtime quadratic (n^2, where n is the number of iterations). Which is about what we would expect if the number of digits in the base is increasing linearly with each iteration, and all the major operations here take time linearly proportional to the number of digits. Is there some particular reason to expect it to be better?

You might want to look at other arbitrary-precision mathematical libraries, like GMP. There are some faster arithmetic algorithms out there than what BigInteger uses. (E.g. see this list of multiplication algorithms used by GMP. I'm not very familiar with the various libraries you might use, however, so I can't say much more than that.

Winston Gutkowski
Bartender
Posts: 10575
66
Mark Udstrand wrote:How can this be changed to make the performance linear instead of exponential?

Well, you have a few things in play here:
1. Mike is right: there are probably faster "big" value classes out there; especially in projects dedicated to Maths. I think of Java's as a "general purpose" big integer, and the performance is generally adequate for an app guy like me.

2. BigIntegers are immutable, which means that the result of any calculation has to be copied to a new instance. In a highly specialized environment like a maths library, it's quite possible that you don't have to worry about niceties like Thread-safety and can make all numbers mutable.

3. I suspect the real problem is your division. The pow() method does use repeated squaring (to be honest I have no idea if there are any faster methods now), but division seems to be pretty much as you'd expect.

4. Java doesn't have unsigned integers (except for char), which means that there's quite a lot of conversion and masking of ints to and from longs. It seems to me that they might have been able to gain some speed by using chars and ints instead; but maybe it's outweighed by the fact that you'd then have extra operations. It's also possible that they work a bit quicker on 64-bit JVMs, but I honestly don't know.

HIH

Winston

Mark Udstrand
Greenhorn
Posts: 4
Okay, I have a much better solution now so I thought I would share.

This code takes the running time down from an estimated 4 days, to somewhere around 10 seconds. It was not the code that needed to be optimized, it was the math. ;-)

Thanks!

Campbell Ritchie
Marshal
Posts: 56545
172
Well done

I have optimised your code with a few new lines, so we can actually read how good it is now.

Winston Gutkowski
Bartender
Posts: 10575
66
Mark Udstrand wrote:Okay, I have a much better solution now so I thought I would share.

As Campbell says: well done.

One tiny point: new Hashtable<BigInteger, Integer>(1048577) will create a Hashtable that doesn't need to be rehashed while it's being filled. Also: HashMap is usually preferred these days.

I was also wondering why it's Hashtable<BigInteger, Integer> rather than Hashtable<Integer, BigInteger>? The latter would seem more likely to me; but I'm not exactly sure how you're using hgMod.

Winston

Mark Udstrand
Greenhorn
Posts: 4

One tiny point: new Hashtable<BigInteger, Integer>(1048577) will create a Hashtable that doesn't need to be rehashed while it's being filled. Also: HashMap is usually preferred these days.

I had it scaled in a earlier code revision and simply forgot to carry it forward. I was so concentrated on the math that I overlooked this clear optimization, thanks!

I was also wondering why it's Hashtable<BigInteger, Integer> rather than Hashtable<Integer, BigInteger>? The latter would seem more likely to me; but I'm not exactly sure how you're using hgMod.

It is this way to aid in the fastest search possible. I am doing a meet in the middle cipher attack (for a cryptography class) and the second part of the algorithm calculates BigInteger values that are then used to search the hash. Since there are potentially 1M+ searches into this hash, the fastest search possible is desirable. With a hashmap that happens to be the containsKey() method.