Win a copy of The Java Performance Companion this week in the Performance forum!

Power function

Luigi Plinge
Ranch Hand
Posts: 441
Just trying out scala, trying to implement the following
An efficient way of computing a power x^n (where n is a nonnegative integer) is given by the recursion

x^n = y^2 if n is even and positive, where y = x^(n / 2)

x^n = x· x^(n - 1) if n is odd

x^0 = 1

Write a Scala function pow(x : Double, n : Int) : Int that implements this algorithm. What is the code of your function?

Here's my code:

but this seems to go into an infinite loop when I try for example pow2(2,2). What's wrong with it?

Also, is there a keyboard or something you can use to break out of a scala command? I'm using Windows PowerShell and the only key combo that seems to do anything is Ctrl+Break which gives me a thread dump from Hotspot and doesn't let me continue with my session.

Luigi Plinge
Ranch Hand
Posts: 441
OK I worked it out, the infinite loop occurs when n=2 because to return an answer it has to work out y^2. If I replace the third line with
it works.

Is there a way to define a temporary variable like y in this case within a function?

Samuel Cox
Ranch Hand
Posts: 96
First, when you run 'scala' in your shell (Powershell), you are running Scala's REPL (interpreter). To exit it, just run 'exit' in the interpreter.

Regarding your question about a y variable, this sounds like homework, so I'll be general.

Luigi Plinge
Ranch Hand
Posts: 441
Not homework - I'm just learning for my own interest and came across some helpful lecture notes that I'm going through.

seems to work, although using "val y = ..." results in stack overflow error.

When I was asking about breaking out, I meant if you go into an infinite loop, as with the first version here (or if you replace y*y with pow(y,2) above). I can't find how to get back to the scala prompt, let alone the shell prompt, and I have to shut down the window and start a new one.

Also, does anyone know if there's a way of editing multi-line commands in REPL? Say I've typed in the above and want to change something, it's a lot of copy and pasting or up-arrow pressing until I get to the right line, for each line...

Jesper de Jong
Java Cowboy
Saloon Keeper
Posts: 15356
39
As far as I know there's no convenient way to edit multi-line code in the REPL. You can do arrow up to scroll to the lines that you've entered before, but if you want to change something, you have to do: up, up, up, up, enter, up, up, up, enter, up, up, edit something, enter, up, enter etc...

Can't you stop the program with Ctrl-C when it goes into an infinite loop? Does it maybe have to do with you using PowerShell instead of the old-fashioned command prompt window?

It goes into an infinite loop when you do pow2(2, 2) because in line 3 it's again going to compute pow2(2, 2), which is again going to compute pow2(2, 2) etc.

Ofcourse you can define a temporary variable inside a method:

Samuel Cox
Ranch Hand
Posts: 96
You might also be curious as to why using:

while

did not. The reason is because the former creates a function (no evaluation), whereas the latter tries to evaluate the function, pow(x, n/2), and assign the value to y. As Jesper pointed out, this evaluation causes the infinite loop. In the former, you are basically doing what you are trying to avoid, which is computing the same value twice. Scala is nice, but it's no Haskell;) Jesper's solution is what I was suggesting.

I don't know about breaking out of infinite loops. I CTRL-C and start over... If that kind of thing was happening a lot, I would put my Scala script in a file or do the normal app thing (def main...).

Luigi Plinge
Ranch Hand
Posts: 441
Jesper de Jong wrote:
Can't you stop the program with Ctrl-C when it goes into an infinite loop? Does it maybe have to do with you using PowerShell instead of the old-fashioned command prompt window?

I tried on command prompt as well and it's the same. So does Ctrl-C work for you guys? Not a big issue as I hope not to be going into infinite loops too frequently, but it could be a hassle if you have a lot of functions and variables and imports defined in your session that you lose.

Samuel Cox wrote:The reason is because the former creates a function (no evaluation), whereas the latter tries to evaluate the function, pow(x, n/2), and assign the value to y. As Jesper pointed out, this evaluation causes the infinite loop. In the former, you are basically doing what you are trying to avoid, which is computing the same value twice. Scala is nice, but it's no Haskell;) Jesper's solution is what I was suggesting.

OK, thanks for the explanation!

Jesper de Jong
Java Cowboy
Saloon Keeper
Posts: 15356
39
Samuel Cox wrote:did not. The reason is because the former creates a function (no evaluation), whereas the latter tries to evaluate the function, pow(x, n/2), and assign the value to y. As Jesper pointed out, this evaluation causes the infinite loop. In the former, you are basically doing what you are trying to avoid, which is computing the same value twice. Scala is nice, but it's no Haskell;) Jesper's solution is what I was suggesting.

In Haskell, everything is lazy - things only get evaluated when the value is actually needed (for example, to print it on the screen). In Scala, vals are by default not lazy, but you can make them so:

x will be initialized the first time you access it; not immediately when you define it.