BigInterger math and conversions

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.

I suppose that your exponent will never exceed 2147483647 (max value of int).

Check the code below...

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);

Uhm, why can't you just use pow ?

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.

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.

1) Why can't use you pow()?
2) What's wrong with BigInteger.multiply()?

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.

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.

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

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

Exactly

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.

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

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!