Trying to use Newton's method to determine if given number is power of 2

wax4brains

New member
Joined
Aug 27, 2017
Messages
8
I'm a Computer Science guy who is pretty bad at math (3rd time taking calc 1 this semester). My task is to write a program which, when a number is entered, will determine if aforementioned number is a power of two. The task only asked for positive powers of two and that was very easily accomplished....but I would like to satisfy finding if it is a negative power of two.

edit: Here is the text of the assignment


  1. Lab2 – Write a method that finds out if a number is a power of two (without using bitwiseoperators). Create a tester program to test a couple of values to prove your method works.





NATURAL_LOG_OF_TWO = 0.69314718056
startingValue = -2
counter = starting value

dy/dx f(x) = 2 ^ x * NATURAL_LOG_OF_TWO

then I have my method which is occurs only when 0 < f(x) > 1

which works like
g(x) = counter - f(x) / (dy/dx(f(counter))

then it subtracts the counter by 1 and runs it again, until either g(x) > f(x) (in which cases it is not a power of two) g(x) = f(x), in which case it is a power of 2.

My program does not work so I am trying to verify that it is a programming issue and not math...
edit: my mistake, I am trying to express my program in math terms I am not very familiar with it may be better to just copy my code


private static double derivativeOfTwoToX(int number) // this calculates the derivative of 2 ^ number
{
double decimal = java.lang.Math.pow(TWO, number) * // 2 ^ number * ln 2
NATURAL_LOG_OF_TWO ;
return decimal ;
}


else if(decimal < ONE && decimal >= ZERO)
{


if(decimal == ONE_HALF) // method starts at -2, so 2^-1 has to be covered
{
return true ;
}
decimal = counter -
(decimal / derivativeOfTwoToX(counter)) ;
while(getDouble() < decimal) // where getDouble() is the number
{
counter-- ; // counter minus one
isPowerOfTwo(decimal) ; // recursive call of method which starts the method for the next x term.
return decimal == getDouble() ; // if the calculated number equals the plugged in value, then it is a negative power of two

}

}
startCounter() ; // this is used to reset the starting value for a new number
return false ; // if Newton's method is run until the number is greater than one then it is not a negative power so it is false
}
 
Last edited:
I'm a Computer Science guy who is pretty bad at math (3rd time taking calc 1 this semester). I need to use Newton's method to find negative roots of two in my program. I have....

NATURAL_LOG_OF_TWO = 0.69314718056
startingValue = -2
counter = starting value

dx/dy f(x) = 2 ^ x * NATURAL_LOG_OF_TWO

then I have my method which is occurs only when 0 > f(x) > 1

which works like
g(x) = counter - f(x) / (dx/dy (counter))

then it subtracts the counter by 1 and runs it again, until either g(x) > f(x) (in which cases it is not of root 2) or g(x) = f(x), in which case it is a root of 2.

My program does not work so I am trying to verify that it is a programming issue and not math...
What is the function (whose root you are trying to calcute)?

That is f(x) = ?
 
… I need to use Newton's method to find negative roots of two …
I'm not sure what you're thinking, when you say, "negative roots of 2". Square roots? Fourth roots? Any negative root?

We get negative roots of 2 only for radicals with an even index.

EGs:

The negative square root of 2 is about -1.4142

The negative fourth root of 2 is about -1.1892

The negative sixth root of 2 is about -1.1225

The negative eighth root of 2 is about -1.0905

et cetera …



NATURAL_LOG_OF_TWO = 0.69314718056
startingValue = -2
counter = starting value

dx/dy f(x) = 2 ^ x * NATURAL_LOG_OF_TWO

then I have my method which is occurs only when 0 > f(x) > 1
Hmmm. It now seems like you're talking about powers of 2, instead of roots of 2.

You have defined y = f(x) = 2^x, yes? This function f outputs powers of 2, none of which are zero or negative.

Also, the derivative operator is dy/dx, not dx/dy.

The inequality above is not correct because it states that y is both less than zero AND greater than 1, which is impossible.


g(x) = counter - f(x) / (dx/dy (counter))
Again, the derivative operator is dy/dx.

And, because dy/dx is an operator (not a function), you cannot use function notation to express taking a derivative.

In other words, do not write dy/dx (input variable). Write dy/dx [f(input variable)].

Lastly, your variable "counter" is a constant. If you apply the dy/dx operator to a constant (i.e., if you take the derivative of a constant), you get zero.

Hence, you may not divide f(x) by dy/dx [a constant] because that leads to division by zero.

I suspect that, while trying to do certain things, you have incorrectly described them as something else. I cannot determine the task, from what you've posted.

Please post the entire text of the exercise, as you received it, including all instructions and any other given information. Thanks. :cool:
 
I am trying to take any given number, below 1 and above 0, and use Newton's to determine if it is a negative power of two...so the function would be 2 ^ x?
There's no such thing as a "negative power of 2". All powers of 2 are positive numbers. Look at a graph of y=2^x. The entire graph lies above the x-axis.

If, instead, you are trying to determine whether the exponent is negative, for any particular power of two between 0 and 1, then I can tell you that it is because they all are!

In other words, the value of x must be negative, in order for the power 2^x to have a value between 0 and 1.

You can see this on the graph of y = 2^x. The graph lies between y=0 and y=1 only in Quadrant II. All values of x in Quadrant II are negative.

Newton's Method is not needed to determine any of this information, so I'm still not sure what you're trying to do.

Are you confusing the words "power" and "exponent"? They are not the same.
 
I am trying to take any given number, below 1 and above 0, and use Newton's to determine if it is a negative power of two...so the function would be 2 ^ x?
So, your f(x) is:

f(x) = 2^x - A (where 1>A>0)

f'(x) = ln(2) * 2^x

Starting value = xold

xnew = xold - [f(xold)/f'(xold)]
 
Well, shoot-a-darn. I just tried to post an example of how Newton's Method can be used to approximate a function's root (i.e., an x-intercept), but I got a Server 500 error when I tried to post, and now the auto-restore button yields nothing. Hence, my typing is lost.

I choose y = 3^x, but it has no root (i.e., it's always positive), so I shifted it downward seven units to get:

h(x) = 3^x - 7

This new function has a value for x that causes h(x) to equal zero. This value is called the root of function h. We can approximate it, to as many decimal places we need, using Newton's Method.

Let's approximate the root (i.e., the x-intercept) to five decimal places.

The process of iteration is described at this other site.

We need the first derivative of function h:

h'(x) = ln(3) * 3^x

Now, they started by picking an initial value for x0, such that h(x0) is positive. This yielded the (blue) tangent line that intersects the x-axis at x1.

Working symbolically, they then used the Point-Slope form of that tangent line's equation, and solved it for x1. In other words, the formula:

x1 = x0 - h(x0) / h'(x0)

gives the next approximation.

So, to find an initial guess (x0) for the root of our function h, we can solve h(x0)=1.

x0 = ln(8)/ln(3) = 1.89278926 (all decimal numbers rounded)

We substitute this value for x0 in the formula above.

x1 = 1.77900936

This approximation is only good to one decimal place. We need another iteration.

In the formula, we replace symbol x0 with x1, and we replace symbol x1 with x2:

x2 = x1 - h(x1) / h'(x1)

We now substitute 1.77900936 for x1:

x2 = 1.77127678

This approximation is better, but it's only good to three decimal places. We need another iteration.

x3 = x2 - h(x2) / h'(x2)

x3 = 1.77124375

This approximation is good to eight decimal places, so we're done.

I hope this example helps you to code Newton's Method. Just be sure that you're working with a function that actually has a root. 2^x does not. :cool:
 
Newton's Method is not needed to determine any of this information, so I'm still not sure what you're trying to do.

Are you confusing the words "power" and "exponent"? They are not the same.

I'm not having an easy time explaining this, sorry. Say I plug in a value, .0315 = 2^ (-2). I would like to test this number, with Newtons method, to find if it is indeed a power of two. If I plug in .0316 0r .1, it should say. "x is not a power of two". Basically I want to a number = (x (counts down each time that I do it) - f(x) / dx/dy (f (prime (x)... the program loops each time until the number is either greater than 1, in which case the input value is not a power of two, or equal to a power of 2, which is continually calculated by the method until one of the two cases is satisfied
 
I cannot answer this question because I still do not know what the given exercise is.

I asked you to post it verbatim; I'm waiting to see what you received.

Please also read the forum guidelines. Thank you! :cool:



  1. Lab2 – Write a method that finds out if a number is a power of two (without using bitwiseoperators). Create a tester program to test a couple of values to prove your method works.


    My output for 15 numbers (chosen by me):


    0.0315 is not a power of two. // 2 ^ -2
    2.0 is a power of two.
    16.0 is a power of two.
    7.62939453125E-6 is not a power of two. // 2 ^ -17
    3.0517578125E-5 is not a power of two. // 2 ^ -13
    1389.0 is not a power of two.
    0.015625 is not a power of two. // 2^ -6
    32.0 is a power of two.
    -4.0 is not a power of two.
    0.1 is not a power of two.
    4.0E-11 is not a power of two.
    65536.0 is a power of two.
    90000.0 is not a power of two.
    127.0 is not a power of two.
    2097152.0 is a power of two.
 
Say I plug in a value, .0315 = 2^ (-2). I would like to test this number, with Newtons method, to find if it is indeed a power of two.
In this example, you have "plugged in" two values, not one.

y = 2^x

You substituted 0.0315 for y.

You substituted -2 for x.

The equation 0.0315 = 2^(-2) is false.

Are you trying to find the correct value of x, given that y is 0.0315?

Are you trying to find the correct value of y, given that x is -2?

As I already posted, you can pick any value for y between 0 and 1 and you are guaranteed to get a negative value for x.

In other words, every Real number between 0 and 1 can be expressed as a power of 2 with some negative exponent.
 
The equation 0.0315 = 2^(-2) is false.


As I already posted, you can pick any value for y between 0 and 1 and you are guaranteed to get a negative value for x.

In other words, every Real number between 0 and 1 can be expressed as a power of 2 with some negative exponent.


I meant 2 ^ -3.... this is part of why I am terrible at math I do this all the time where I just use a wrong number and it messes everything up.

and I did not clarify that I am only looking for whole integers exponents, you are right I did not think about that.


My teacher just emailed me and I think a much easier way to go about this would be algebraically. Instead I should just use take the decimal value, take the reciprocal and calculate if that is a power of two through simple division. I think this approach is better suited so I'm going to have to rewrite the code. Anyway sorry for my ambiguity and thank you so much for the responses.
 
… Write a method that finds out if a number is a power of two …
Thank you for posting the actual wording of the exercise.

I'm now thinking that the author of this exercise does not know how to properly express what they actually want because, as written, the exercise is trivial.

All positive numbers are powers of 2, so your program needs only test the sign of the number which the user inputs as the power.

If the value input for the power is 0.0315, then it's a power of 2 (because 0.0315 is positive).

2^(-4.9885) ≈ 0.0315

If the user picks ANY number between 0 and 1, then they have picked some power of 2.

Otherwise, if the user inputs zero or a negative value, then they have not input a power of 2.
 
Last edited:
… I did not clarify that I am only looking for whole integers exponents …
Why are you thinking only about powers of 2 with Integer exponents?

The exercise statement does not say anything about Integer exponents. :?
 
I'm not having an easy time explaining this, sorry. Say I plug in a value, .0315 = 2^ (-2). I would like to test this number, with Newtons method, to find if it is indeed a power of two. If I plug in .0316 0r .1, it should say. "x is not a power of two". Basically I want to a number = (x (counts down each time that I do it) - f(x) / dx/dy (f (prime (x)... the program loops each time until the number is either greater than 1, in which case the input value is not a power of two, or equal to a power of 2, which is continually calculated by the method until one of the two cases is satisfied
We are having trouble following you because we can't figure out what your problem is.

Here is is a simple iterative process to determine whether a number between 0 and 1 is 2 exponentiated by a negative integer.

\(\displaystyle 0.0306 * 2 =0.0612 < 1.\)

\(\displaystyle 0.0612 * 2 = 0.1224 < 1.\)

\(\displaystyle 0.1224 * 2 = 0.2448 < 1.\)

\(\displaystyle 0.2448 * 2 = 0.4896 < 1.\)

\(\displaystyle 0.4896 * 2 = 0.9792 < 1.\)

\(\displaystyle 0.9792 * 2 = 1.9584 \not < 1.\)

\(\displaystyle 1.9584 \ne 1 \implies 0.0306 \text { is not equal 2 raised to a negative integer}.\)

I simply do not grasp what the relevance of Newton's method is.
 
I'm not having an easy time explaining this, sorry. Say I plug in a value, .0315 = 2^ (-2). I would like to test this number, with Newtons method, to find if it is indeed a power of two. If I plug in .0316 0r .1, it should say. "x is not a power of two". Basically I want to a number = (x (counts down each time that I do it) - f(x) / dx/dy (f (prime (x)... the program loops each time until the number is either greater than 1, in which case the input value is not a power of two, or equal to a power of 2, which is continually calculated by the method until one of the two cases is satisfied
We are having trouble helping you because we either do not understand what you are trying to do or do not understand what Newton's method has to do with it.

Here is is a simple iterative process to determine whether a number between 0 and 1 is 2 exponentiated by a negative integer.

\(\displaystyle 0.0306 * 2 =0.0612 < 1.\)

\(\displaystyle 0.0612 * 2 = 0.1224 < 1.\)

\(\displaystyle 0.1224 * 2 = 0.2448 < 1.\)

\(\displaystyle 0.2448 * 2 = 0.4896 < 1.\)

\(\displaystyle 0.4896 * 2 = 0.9792 < 1.\)

\(\displaystyle 0.9792 * 2 = 1.9584 \not < 1.\)

\(\displaystyle 1.9584 \ne 1 \implies 0.0306 \text { is not equal 2 raised to a negative integer.}\)

I simply do not grasp what the relevance of Newton's method is.
 
Last edited:
There's no such thing as a "negative power of 2". All powers of 2 are positive numbers. Look at a graph of y=2^x. The entire graph lies above the x-axis.

If, instead, you are trying to determine whether the exponent is negative, for any particular power of two between 0 and 1, then I can tell you that it is because they all are!


Are you confusing the words "power" and "exponent"? They are not the same.

Thanks so much for your help! thanks to you I was able to do much better on my homework. I got this output now:

(for whole and positive values I get x is a power of two other calculations are used by calculating log 2 / log x)
not a whole, positive exponent, but 0.125 is 2 ^ -3.0
2.0 is a power of two.
16.0 is a power of two.
Not a whole, positive exponent, but 7.62939453125E-6 is 2 ^ -17.0
Not a whole, positive exponent, but 3.0517578125E-5 is 2 ^ -15.0
Not a whole, positive exponent, but 1389.0 is 2 ^ 10.439830883981394
Not a whole, positive exponent, but 0.015625 is 2 ^ -6.0
32.0 is a power of two.
-4.0 is a negative. No negative numbers are a power (as far as I'm aware)
Not a whole, positive exponent, but 0.1 is 2 ^ -3.321928094887362
Not a whole, positive exponent, but 4.0E-11 is 2 ^ -34.541209043760986
65536.0 is a power of two.
Not a whole, positive exponent, but 90000.0 is 2 ^ 16.457637380991763
Not a whole, positive exponent, but 127.0 is 2 ^ 6.988684686772166
2097152.0 is a power of two.
 
Top