• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

BigInteger exponents - how?

 
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi all, Have rattled my brain and cannot work out how to do a BigInteger a
to the power of e, where both a and e are BigIntegers.
Any help appreciated.
 
Ranch Hand
Posts: 823
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
OK, well, here is some code:

Now, that sure as hell isn't the most efficient way to do it but it will work for positive numbers. You may need to go on holiday while it does its calculation for large values of exponent but it will eventually finish ... eventually. You might want to look up a more effective mathematical formula for calculating exponents if you really need this functionality. I expect my terminology's a bit suspect too, but hey! And I haven't exactly tested it thoroughly.

How does it look?

Jules
[ August 19, 2004: Message edited by: Julian Kennedy ]
 
JulianInactive KennedyInactive
Ranch Hand
Posts: 823
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Having thought about this overnight it's quite likely that, for large exponents, the above code will not actually finish executing in our lifetime or, perhaps, ever.

Note that the time taken to execute BigInteger.pow() increases exponentially as the exponent increases (it's not linear as I thought my algorithm would theoretically be). on my box BigInteger.pow(100000) takes 1 second; pow(200000) takes 4 seconds and pow(500000), 27 seconds. My program does pow(100000) in 11 seconds and pow(200000) in 51 seconds.

It would therefore be more efficient to use BigInteger.pow(int) and use the modulus of Integer.MAX_VALUE in the above algorithm, rather than multiplying in a loop.

A really simple solution that would make sense for practical values (which, having gone through the hoops may be the answer you are looking for anyway) would be:


HTH

Jules
 
Ranch Hand
Posts: 328
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You can do it more effectively by employing an algorithm with logarithmic execution time, rather than linear.



It could be rewritten as a non-recursive one, of course.
[ August 30, 2004: Message edited by: Dmitry Melnik ]
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic