Win a copy of OCP Java SE 8 Programmer II Exam Study Guide this week in the OCP forum!
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 all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# BigInterger math and conversions

Greenhorn
Posts: 5
I have a lab where I ask the user for a number(x) then ask them for a power(p). I need to return (x^p) as a BigInteger but I am having some trouble doing this. I have working code for a Int but the number gets to large and I need to use a BigInteger. Any insight would be greatly appreciated. Thanks.

Ranch Hand
Posts: 1183
I suppose that your exponent will never exceed 2147483647 (max value of int).

Check the code below...

Jon Moore
Greenhorn
Posts: 5
can't use pow().

I have something like this for code:

x = 3; // number entered by user
p= 5; // the number of the exponent entered by the user
result = x;

for(int i = 0; i < p-1; i++)
{
result *= x;
}

print(result);

Sebastian Janisch
Ranch Hand
Posts: 1183
Uhm, why can't you just use pow ?

Marshal
Posts: 58319
178
I presume you are not using the BigInteger#pow(int) method?

There is a standard recursive method for returning powers.
• Base Case 1: If your exponent is 0, return 1.
• Base Case 2: If exponent is 1 return argument unchanged.
• Base Case 3: If exponent < 0 can't calculate fractions, so throw Exception (or return 0 on spec).
• Base Case 4: If argument is 1 result = 1.
• Base Case 5: If argument is 0, result = 0.
• Recursion: a^i = a * a^(i - 1)

• There is a much more efficient recursive technique using a square algorithm, but try that one first.

Note the existence of static final BigIntegers, ONE, TEN and ZERO.

Campbell Ritchie
Marshal
Posts: 58319
178

Sebastian Janisch wrote:Uhm, why can't you just use pow ?

Because it is a lab exercise and they have to work out their own algorithm.

Sheriff
Posts: 21288
87
1) Why can't use you pow()?
2) What's wrong with BigInteger.multiply()?

Sebastian Janisch
Ranch Hand
Posts: 1183
I have just implemented a recursive pow function.

It seems more elegant to me than looping, but why exactly is it a better implementation. In case I have a big exponent I could run into a StackOverflowError, which won't happen using a loop.

Campbell Ritchie
Marshal
Posts: 58319
178
It is better to use recursion because he will get more marks for it. The idea behind these things is to demonstrate they know algorithms and techniques. I have a recursive method, too, which (of course) has to use BigInteger.multiply.

java BigIntegerPowerDemo 123456789 654
123456 * 234567 + 10 = 28958703562
123456789^654 = 709243017246277593746637276708964869890859321836280203450556538966218427581312503205888435200
712415993007060452287447719423554994106252407261181376217608933440896766173823435092958776390871710243389642
519155272741211261758165236935536477804640579284149651882585025541033059194056000040927922022696307281198419
444599487039218668717852862658414982036787621975155162892683722683056092387663021781584797864753594213846657
971903078992865854600684416745962773699318837373318156750999851155938327618524306663873487895767618962490573
306527587719800575408435883562252715253609369621244509582926127761937519143103020151516953495748683954891419
309741666671245157992949018807135100800264725426056591798417906051219148023913759320030621947472733431517851
140051610561944678120742486344329085999745893785806744834462971870416753532588266123142983890993624119451809
953889131167496392640923808436639979150630052816710310170812505678234997950919228257072479087143217513464091
441609023983635727493486831667881548651625702944438024991497411676161721548925809038208276825306272149393095
099087520400584836535979450531766415402748411581100165421920798476418983400649070570739481294321426068331205
091506245678548786284920453057034888958571435403070125786147531135173831546520234158978502756638196969276224
747872361990156844570068594938049466921783528864328601783127040282917763395856981868094592266682204809885839
598597694736152843278473542270970113929045122380600263335661920628352830105331356284759523612591386356550880
771272077302974143223673291613693410108628698507828965142715390619502334184220695119993390473400634914314515
170725823773690576612732138039836783892389025538443265267815665203640227210314336085707687574746320146709471
311756578611760066822962296671885974907974643022900776212687204709733467419062742454618485434938167990862191
216576794173044128460010904077148111417053013288881427469502686052075618463209601330763444893928520226330230
510726233470036202306885004437591076114023445111650091474063515640193947544383851505432267261859857274076746
636965700379352084084863917648046744302885450313019752437417792551430386452765983606463980301638012699622031
603246857714543984087411473339444157937517587660953246804309087802124635596860334012644011057202920572243334
222950976447998862354309020408560960074484301770359004583877433147726983524270191796644854673942105217558042
798831011581021859625440312270625304989785646994636080387634113642958546004814347338296338329677543829660950
621602598985121504760996898249705657714761277207542382399349737651768526934898289524764062539907581411175218
256850314521566346830890438976527290327810457065142663586615499836885666972896130660167642507699201847818848
776072699344211212371195120705304753008301729461691309173822230622606529326265516126026906611180165620018736
093276527567186913133379424613464152685316650606390581347033917833823528992378220960821393986184477872581980
649317286985232722147130601285557272716241746013688657378890431900344420605206105628167968688625782740712504
374555388047289148353665036587780538053644223177071826330112590850117253525424884583530827698215802719307339
280606852142223360925781396390941399828158690943008600431810455930480797249812733320772430643401267483710314
468083238384218945569422851287979069229116109810800508434983940330038639833882398512657282978117486382436723
346299936652082575862828576331991310139512202729968177175409218580124742993597594463680518129051629165304587
692477806736714881562003975021291880357088132469496687807691934842968852582167064973655134180224863374113674
719616484582848840074475527982749465655713698945246329067374379072640894556739769769863988767192142802786181
966228456560649688072695898724983298980187424041831396795643060936959018204708445049089586639640413280871788
795957888776792058652937727995019544276092843896826465455702505177254470167150147287482469413371302820220894
356953723534732838903356854583750299409983879515211911152063560440587437364823084788566309833595012862439863
845923597100895495059094973443753400057362693479100675401017743081136902544728746727223354945684543278149816
016906802710164878584148177703988777298235508293702739330907832097549835855235778146814417630287973206041880
330175862587925334704987440872004930504307145860021877302357578784311960782458510923125834155001969576552674
876743160717356330388579142091624316049553490175645430089144797062377350609352966288655882824019590446785722
690619448905801756226062850566445230518690723544678839587961990273033619992227886990369345311480695554940315
964986678041492308715852552433074760068013455795464506376831665882054783987104646654268327460831687560497002
169745032313263611863557230417281918643751458602732706166478432146529023715353832613210650820684222220693582
647115905150769527786385046075562468824916863046422653490634302181797732554481123691982673597092765444594846
694099568065545471811113385915547182764031592363643537149797633269231447406076340497460317451168529519339813
835142604103312183956085598037285282692905640881736552196426403368894538863941795344011970372003722619983683
541739307269888901796158974722787398208278961231662943996443810926353684541992340236320931429296351359093745
685088857594553267929109727092437367202854377538862075105817745664948197934955272827116999025669124323682041
499629953690441

I haven't checked whether it is correct.
Last time I tried this sort of thing, I could get up to about exponent = 5000 before getting a StackOverflowError.

Sebastian Janisch
Ranch Hand
Posts: 1183
So the reason behind using recursion over the loop is because your tutor, professor whatever will like it better ?
great

Campbell Ritchie
Marshal
Posts: 58319
178

Sebastian Janisch wrote:So the reason behind using recursion over the loop is because your tutor, professor whatever will like it better ?
great

Exactly

Rob Spoor
Sheriff
Posts: 21288
87
Then again, he might wonder why you're using recursion and risking a StackOverflowError when a simple loop would suffice

Just write both versions, to show you master both techniques.

Campbell Ritchie
Marshal
Posts: 58319
178

Rob Prime wrote:Just write both versions, to show you master both techniques.

Then write the recursive version which uses a square(...) method and runs in logarithmic time for an extra mark

Ranch Hand
Posts: 710

Campbell Ritchie wrote:

Rob Prime wrote:Just write both versions, to show you master both techniques.

Then write the recursive version which uses a square(...) method and runs in logarithmic time for an extra mark

While you are at it, why don't you make a UI so the user can choose either a loop or recursion to execute!

 Did you see how Paul cut 87% off of his electric heat bill with 82 watts of micro heaters?