This week's giveaway is in the Android forum.
We're giving away four copies of Android Security Essentials Live Lessons and have Godfrey Nolan on-line!
See this thread for details.
The moose likes Beginning Java and the fly likes BigInterger math and conversions Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Android Security Essentials Live Lessons this week in the Android forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "BigInterger math and conversions" Watch "BigInterger math and conversions" New topic
Author

BigInterger math and conversions

Jon Moore
Greenhorn

Joined: Jul 08, 2009
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.
Sebastian Janisch
Ranch Hand

Joined: Feb 23, 2009
Posts: 1183
I suppose that your exponent will never exceed 2147483647 (max value of int).

Check the code below...



JDBCSupport - An easy to use, light-weight JDBC framework -
Jon Moore
Greenhorn

Joined: Jul 08, 2009
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

Joined: Feb 23, 2009
Posts: 1183
Uhm, why can't you just use pow ?
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38040
    
  22
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
    Sheriff

    Joined: Oct 13, 2005
    Posts: 38040
        
      22
    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.
    Rob Spoor
    Sheriff

    Joined: Oct 27, 2005
    Posts: 19654
        
      18

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


    SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
    How To Ask Questions How To Answer Questions
    Sebastian Janisch
    Ranch Hand

    Joined: Feb 23, 2009
    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
    Sheriff

    Joined: Oct 13, 2005
    Posts: 38040
        
      22
    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

    Joined: Feb 23, 2009
    Posts: 1183
    So the reason behind using recursion over the loop is because your tutor, professor whatever will like it better ?
    great
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 38040
        
      22
    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

    Joined: Oct 27, 2005
    Posts: 19654
        
      18

    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
    Sheriff

    Joined: Oct 13, 2005
    Posts: 38040
        
      22
    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
    W. Joe Smith
    Ranch Hand

    Joined: Feb 10, 2009
    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!


    SCJA
    When I die, I want people to look at me and say "Yeah, he might have been crazy, but that was one zarkin frood that knew where his towel was."
     
    It is sorta covered in the JavaRanch Style Guide.
     
    subject: BigInterger math and conversions
     
    Similar Threads
    reverse an integer
    Exception occurred during event dispatching
    BigInteger Raised to the power of BigInteger
    convert BigInteger to integer
    BigInteger Operations