• Register
Welcome to Kodlogs Q&A, where you can ask programming questions and receive answers from other members of the community. For programmers, by programmers Kodlogs is an open community for anyone that does coding. We help you get answers to your toughest coding questions, share knowledge with your coworkers in private, and find your next IT dream job.

Most popular tags

java program python php javascript c# android python-3 spring r c arrays mysql html spring-boot numpy string exception tomcat macos python-2 eclipse ssl sockets 7 x ssl-certificate entity-framework sql-server matlab redirect code program pip hibernate math security jquery cryptography windows asp list loop int net class https heap-memory garbage-collection quirks-mode internet-explorer-9 internet-explorer machine-learning indentation-error android-studio jupyter-notebook winforms visual-studio-2010 webpack keytool numpy-ndarray aspnet dataframe pandas minecraft jdbc jpa servlet indentation ios typeerror scanner sum deployment loops css util cmd recursion tcp syntax csv float sql number import x509certificate ibm-bpm fatal-error websphere-7 file-permissions file-io accesscontrolexception grizzly atmosphere slick2d lwjgl struts informetica java-applet intellij-idea twitter-bootstrap-3 jax-rs resteasy spring-mvc spring-security-kerberos spring-security kerberos long-integer mapnik pytorch git-review runtime-error vpython continuation homebrew xgboost conda visual-studio android-asynctask stack-trace user-interface jaxws-maven-plugin maven-3 maven-2 browser-notsupportedexception google-maps-api-3 google-maps visual-studio-code truststore apache-spark pyspark firebase-authentication aws-organizations amazon-web-services php-7 string-formatting cplusplus visual-studio-2015 net-core net-mvc msbuild extension-methods foreign-keys sql-server-2005 windows-services react-redux reactjs inputstream facebook-graph-api for-loop entity-framework-4 reportingservices-2005 reporting-services mips linear-regression scikit-learn anova deep-learning keras block-device melt reshape2 floating-point webpack-dev-server javascrip 0-lollipop android-5 statsmodels avx eclipseide javafx-2 php-not-recognized laravel command-line unit-testing tinyurl atom-editor android-emulator android-sdk-tools ionic2 cordova foobar2k tcplistener net-2 net-4 ole-db-provider windows-10 vagrantfile ggplot2 glmnet jvm-arguments global-variables orm virtualenv atom xls oledb redux webclient nio prediction headless hyperlink outlook jackson keystore pipeline illegalstateexception iis jstl encryption perfect-square objective-c carthage xcode8 compiler-errors standard-deviation xampp connector apple mdf destructor vagrant gettime gmail ioexception heuristics milliseconds reporting cpu npm modx-revolution goldsky modx prevnext javascript-dictionary stack-smashing device-monitor radio-button android-actionbaractivity android-activity android-fragments java-long unqualified-id ora-12154 javc c++ java nullpointerexception runtime-error drjava awt-eventqueue dsx math-pow ajquery nosuchelementexception appcompatactivity jtextfield jpanel inputmismatchexception nullpointerexception deque jupyter javafx lvalue junit tensorflow maven simulation ibm factorial javax apache boot opengl virtualbox jvm margins 2147483647 mongodb xcode ubuntu cloud firebase plot processor automation socketexception git crash card certificate pointers concatenation debugging oracle devices module testing color arraylist sequence search date caching expected response directory algorithms release collections facebook figure url expression integer microsoft sorting sort datetime httpwebrequest rest json ajax exe dictionary message required variable time size dll system files runtime function random code file map html5 http version 2
0 votes
8 views
How to use math.pow in java? What does math.pow do in java?
by (8.9k points)  
reshown by

1 Answer

0 votes
In this lesson, we will try to solve another problem using recursion and the problem is

that given two positive numbers - X and N, we want to calculate x to the power n and

x to the power n is nothing but n times x multiplied to itself.

So, there are n Xs, lets say in this expression and to calculate x to the power n, we perform,

if we simply keep on multiplying with x all the time, exactly n -1 multiplications.

And if we want to write a program to calculate x to the power n , the simplest thing that

comes to our mind is that we can start with a variable, say we want to start with a variable

result, initialize it to 1 and then we can simply run a loop from 1 to n and keep multiplying

result with x.

So, result becomes result*x.

In this case you are performing n multiplications because you are initiating the variable to

1 instead of x, but it also takes care of the condition when n is equal to 0 and as

we know x to the power 0 or any number to the power 0 is 1.

And as we can see for an input n, we are running the loop, we are running just one loop n times,

so it should be pretty evident that the time taken here in this particular case would be

proportional to n or we can also say that the time complexity of this algorithm would

be O(n).

Now, Albert and Pinto and two students of MyCodeSchool and they have been given the

assignment to calculate x to the power n using recursion.

So, once again Albert and Pinto come up with two different solutions and let us see what

their solutions are.

To solve a problem using recursion, we first need to define a recurrence relation or a

recursive definition.

So, Albert says that hey, x to the power n can be written as x*x^(n-1) and this is true

for all n greater than 0.

For n = 0, x to the power 0 is simply equal to 1.

So, x to the power n being equal to x into x to the power n-1 is a recurrence relation

because x^n is expressed in the form of x^(n-1) and this second condition is our base condition.

So, let us see what Albert's implementation is.

Albert writes a function Pow that takes two arguments - x and n and we are only writing

pseudo-code here and the function goes like - if n is 0, then simply return 1, else return

x into and we make a recursive call here to calculate x to the power n minus one.

So, we pass arguments x and n-1.

And this is Albert's implementation.

And this will work fine for all n greater than or equal to 0.

So, using this algorithm, if you want to calculate say x to the power 8, we make a recursive

call first to calculate x^7, and then x^7 goes on to make a recursive call to calculate

x^6.

And we keep on making recursive calls till X^0 and X^0 simply returns 1 and at this stage

the recursion terminates.

Now, let us see Pinto's solution.

And Pinto is a little smarter.

He says that x^n can be written as x^(n/2)* x^(n/2) if n is an even number.

And X^n is equal to x*x^(n-1) if n is odd.

And X^n is equal to 1 for the simple case or the base case of n = 0.

So, we kind of have 2 different recurrence relations for two different cases.

And let us see how the program looks like.

So, Pinto also writes a method Pow that takes two arguments x and n.

And his program also goes like if n is zero, then return 1, else if n is even and we can

also say , if n modulo 2 is 0, then first calculate x^(n/2) and then store it in a variable.

So let's say we have a variable y in which we store x^(n/2) by making a recursive call

to calculate x^(n/2).

So, this is a recursive call.

And we return y*y.

Now, instead of writing these 2 statements here, we could also have simply written that

return pow(x,n/2)* pow(x,n/2) but that would have been very bad because in that case, we

would make two different calls to calculate the same value which will be unnecessary redundancy.

So, if we would want to calculate x^8, we would make 2 calls to calculate x^4 and then

multiply them.

So, we make just one call and store it and then simply multiply it to calculate the square.

And finally,. if n is odd which will be our final condition, then we simply return x*x^(n-1)

and this also works fine for all n >= 0.

So, now when we want to calculate x^8, then we make a call to x^4 , so instead of reducing

this to x^7, we reduce the problem to calculate x^4 and further x^4 recursively makes a call

to calculate x^2 and then we go on like x^1 and x^0.

So, while Albert's program goes kind of nine steps here in this structure called the recursion

tree, Pinto's program only goes 5 steps in this recursion tree and if we analyze the

recurrence relation of these 2 algorithms, then Albert's algorithm , the time taken by

it is proportional to n or it is bi-oh of n or order of n in terms of time complexity

and Pinto's program is order of log of n in terms of time complexity.

How Albert's program is order of n algorithm and how Pinto's program is order of log n

algorithm is something that we will explain in another lesson, we will try to deduce it

mathematically, but as we can see that Pinto's program which is order of log n is lot more

efficient than Albert's program.

Now couple of things here.

When we are trying to calculate exponents, then in a real program, an integer variable

which is stored in 32 bits is able to store decimal numbers of only 9-10 digits while

x^n can be really really large.

So, lets for the sake of algorithmic understanding, assume that we have a machine where all this

storage and calculations, arithmetical calculations is not a problem.

So, this was exponentiation.

In another lesson, we will try to solve a very similar problem, modular exponentiation

and we will also mathematically deduce the time complexity of these recursive algorithms.
by (8.9k points)  
...