java - Finding A power B using BigInteger and using recursion -


this piece of code in java.

import java.util.scanner;  import java.math.*;  class power1 {  public static void main(string[] args) {      scanner in=new scanner(system.in);     long a=in.nextlong();     biginteger b=in.nextbiginteger();     long res=power(a,b);     system.out.println(res); }  public static long power(long x,biginteger n) {      int b=(int)(math.pow(10,9)+7);     long m;     if (n.compareto(biginteger.zero)==0)         return 1;     if(n.compareto(biginteger.one)==0)         return x;     if ((n.mod(biginteger.valueof(2)).compareto(biginteger.zero)==0))     {         m = power(x,n.divide(biginteger.valueof(2)));         return (m * m)%b;     }      else return (x * power(x,n.subtract(biginteger.valueof(1)))%b);  }  }

this should work value of b considering biginteger. when enter large value of b ,i errors as

exception in thread "main" java.lang.stackoverflowerror     @ java.math.mutablebiginteger.divideknuth(unknown source)     @ java.math.mutablebiginteger.divideknuth(unknown source)     @ java.math.biginteger.remainderknuth(unknown source)     @ java.math.biginteger.remainder(unknown source)     @ java.math.biginteger.mod(unknown source)

is there way fix it?

you should implement following algorithm:

recursivepower(base, exp):     if (exp == 0)          return 1;     if (exp == 1)         return base;     if (exp%2 == 0) {         temp = recursivepower(base, exp/2);         return temp*temp;     temp = recursivepower(base, (exp-1)/2);     return temp*temp*base;

this drastically reduce number of calls you're using. thing enlarging size of stack. run application java test -xss2048k - try different sizes.

and last not least use biginteger time.

public static biginteger recursivepower (biginteger base, biginteger exp) {     if (exp.compareto(biginteger.zero) == 0)          return biginteger.one;     if (exp.compareto(biginteger.one) == 0)         return base;     if (exp.mod(biginteger.valueof(2)).compareto(biginteger.zero) == 0) {         biginteger temp = recursivepower(base, exp.divide(biginteger.valueof(2)));         return temp.multiply(temp);     }     biginteger temp = recursivepower(base, (exp.subtract(biginteger.valueof(1)).divide(biginteger.valueof(2))));     return temp.multiply(temp).multiply(base); }  public static void main(string []args){     system.out.println(recursivepower(biginteger.valueof(2), biginteger.valueof(80)).tostring());  }

Comments

Post a Comment

Popular posts from this blog

asynchronous - C# WinSCP .NET assembly: How to upload multiple files asynchronously -

i using winscp .net assembly uploading files. want upload multiple files asynchronous way. have created method works single upload. public class uploadingdata { private sessionoptions _sessionoptions; private session _session; //connection etc private void onconnected() { foreach (var fileinfo in localfileslist) { var task = task.factory.startnew(() => uploadfilesasync(fileinfo)); } } private async task uploadfilesasync(string file) { string remotefilepath = _session.translatelocalpathtoremote(file, @"/", "/test_data_upload"); var uploading = _session.putfiles(file, remotefilepath, false); //when done await task.run(() => thread.sleep(1000)); } } please suggest me correct way. thanks you can use backgroundworker class this: string[] images = new string[50]; foreach (var path in images) { backgroundworker
Read more

aws api gateway - SerializationException in posting new Records via Dynamodb Proxy Service in API -

i getting "__type": "com.amazon.coral.service#serializationexception" as reply in postman & in test console in api gateway trying post record directly dynamodb using api proxy services.. referring aws article - https://aws.amazon.com/blogs/compute/using-amazon-api-gateway-as-a-proxy-for-dynamodb/ here's mapping { "tablename": "tablenamegoeshere", "item": { "id" : "$context.requestid" "eventname" : "$input.path('$.eventname')", "timestamp" : $input.path('$.timestamp'), "answers": "$util.parsejson($input.path('$.answers'))" } } update: did asked ... , worked if try add array of json objects gives me above same error - here's trying now. please - couldnt find on google well #set($inputroot = $input.path('$')) { "tablename": "answer", "item": {
Read more

asp.net - Problems sending emails from forum -

i have been redesigning site has message board, has been written guy looked after site. it has few problems , written in .asp , uses .mdb files database. you can see whole thing here . feel free post if helps, test thing have set using original files , new database. the basic problem when posts message, supposed email sent them, have posted it. when replies, originator supposed message, replier has been posted. i’d have thought @ point in process there should script/file in postmessage.asp? the postmessage.asp page below. <% option explicit %> <!-- #include virtual="common/adovbs.inc" --> <html> <head> <meta http-equiv="content-type" content="text/html; charset=windows-1252"> <meta name="generator" content="microsoft frontpage 4.0"> <meta name="progid" content="frontpage.editor.document"> <title>new page 2</title> <base target="_self"
Read more