*
The moose likes Beginning Java and the fly likes Is my prof trolling me? (factorials, loops) Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Is my prof trolling me? (factorials, loops)" Watch "Is my prof trolling me? (factorials, loops)" New topic
Author

Is my prof trolling me? (factorials, loops)

john medici
Greenhorn

Joined: Nov 12, 2011
Posts: 2
hey guys so i have this assignment due tommorow and don't see what im doing wrong.

You can approximate e by using the following series

1+ 1/1!+1/2!+1/3!+1/4!+⋯

Write a program that find out how many TERMS of this series you need to use before you first get 2.71828183.

So what I have is: (ignore comments its just me testing)



This code will run forever because the 'answer' starts looping at the 18th increment. and it never goes higher.
I also decided to make my variables absolutes because if not then on the 17th iteration "bottom" becomes negative, so at first i thought this was the problem.

The solution is probably simple but I can't figure it out atm?
Tim Moores
Rancher

Joined: Sep 21, 2011
Posts: 2408
For starters, why does does loop terminate at "(answer != 2.71828183)" when that is not the correct answer? You'll note that the answer doesn't change after step 18, when the limit of precision that a double offers is reached. So you should terminate the loop when the answer does not change between two steps.

The actual digits are 2.71828182845904523, so the code is not far off.

If you want more accuracy, use the java.math.BigDecimal class instead of doubles.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7699
    
  20

john malkovich wrote:Write a program that find out how many TERMS of this series you need to use before you first get 2.71828183.

Tim is absolutely right; the answer will never be 2.71828183. In fact, if I was your prof and you pointed that out, you'd get a gold star.
And if the question asks (or you write a solution to) 'find out how many terms of this series you need to use before you get to an answer that rounds to 2.71828183' you'd get two.
And, as he also said, you'd be much better off using BigDecimal for your calculation. Have a look at MathContext too.

The solution is probably simple but I can't figure it out atm?

Well, I did think of one alternative that may be simpler, but it takes a bit of lateral thinking. Have a look at each term of the series. What is it, and how does it affect the overall result? I warn you though that the proof that it works may be a little harder.

Winston


Isn't it funny how there's always time and money enough to do it WRONG?
Articles by Winston can be found here
john medici
Greenhorn

Joined: Nov 12, 2011
Posts: 2
Tim Moores wrote:For starters, why does does loop terminate at "(answer != 2.71828183)" when that is not the correct answer? You'll note that the answer doesn't change after step 18, when the limit of precision that a double offers is reached. So you should terminate the loop when the answer does not change between two steps.

The actual digits are 2.71828182845904523, so the code is not far off.

If you want more accuracy, use the java.math.BigDecimal class instead of doubles.


thanks tim. regarding the terminate at"(answer != 2.71828183)" it keeps running until the answer doesn't equal that value. As in when the answer is finally what the prof wants it to be the loop will stop running. I don't see why this is wrong?
Also with regards to the double variable type i now see what you mean for some reason it only outputs 16digits past the decimal point even though the value held in memory is larger(read:more digits)?

Another thing guys is my prof is saying we aren't allowed to import any api's we haven't studied in an intro course yet... (so that rules out bigdecimal)

So im basically going to submit the homework as is stating that the desired output will never be reached. I guess I will see what he says.
ps. also dziekuje winston!

Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18759
    
  40

john medici wrote:
thanks tim. regarding the terminate at"(answer != 2.71828183)" it keeps running until the answer doesn't equal that value. As in when the answer is finally what the prof wants it to be the loop will stop running. I don't see why this is wrong?
Also with regards to the double variable type i now see what you mean for some reason it only outputs 16digits past the decimal point even though the value held in memory is larger(read:more digits)?


As many have already mentioned, this is a case of following the letter of the assignment, but not the intent of the assignment.

Your professor wants you to get to "e"; that is the intent. However, your professor accidentally told you that e = 2.71828183 (which is an approximation), and you are following his/her instructions to the letter. Your program found a value of e which is more accurate than the approximation that was given, but that doesn't work since you need the exact approximation.

Henry


Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18759
    
  40

john medici wrote:
So im basically going to submit the homework as is stating that the desired output will never be reached. I guess I will see what he says.


If I was the professor, I would be torn. Part of me would like that the student is very diligent, and worked hard to get to the exact answer. Another part of me would question a student who doesn't know what the value of "e" is, and the fact that it is an irrational number.

Henry
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19679
    
  18

What's with the Math.abs(0) and Math.abs(1) calls? Why not just write their equivalents 0 and 1?


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7699
    
  20

john medici wrote:So im basically going to submit the homework as is stating that the desired output will never be reached. I guess I will see what he says.
ps. also dziekuje winston!

Prosze bardzo.

However, I suspect you will get more brownie points if, as Henry says, you submit your homework that delivers the intent; and that is very simple (you've already written most of it). Simply stop when the result is near enough to 2.71828183. All you have to work out is what "near enough" is.

Winston
Harsha Smith
Ranch Hand

Joined: Jul 18, 2011
Posts: 287
declare a variables something like



now keep on calculating the sum while sum less than Math.E. something like this



Add a static method factorial that takes double as argument and returns double. use recursion to get factorial of a number

Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7699
    
  20

Harsha Smith wrote:...use recursion to get factorial of a number.

Actually, don't. Factorial is a function that is often used to demonstrate recursion, because it is easily understood; but it is a very bad use of it as a technique.
@john: Recursion (if and when you need it) is generally used in "divide and conquer" situations.

Winston
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3615
    
  14

To be fair, I don't think it's that bad to use it. It just depends on the language. As of Java 7, recursion is very weak and it's definitely better to prefer iteration.

However, I learned that Java 9 may be incorporating tail calls, which will make recursion excellent for something like a factorial.
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19679
    
  18

Stephan van Hulst wrote:As of Java 7, recursion is very weak and it's definitely better to prefer iteration.

Got a source?
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7699
    
  20

Stephan van Hulst wrote:However, I learned that Java 9 may be incorporating tail calls, which will make recursion excellent for something like a factorial.

'Fraid I can't believe that. For starters, the classic recursive method will eventually throw a stack exception; and if you restrict the answer to some maximum, I can't believe that simple iteration isn't still the fastest. But I would be interested to know how you think that tail calls might make a difference ... and also what the timeline is for Java 9 .

Winston
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4371
    
    8

Winston Gutkowski wrote:
'Fraid I can't believe that. For starters, the classic recursive method will eventually throw a stack exception; and if you restrict the answer to some maximum, I can't believe that simple iteration isn't still the fastest. But I would be interested to know how you think that tail calls might make a difference ... and also what the timeline is for Java 9 .

I've no idea what the plan is for Java, but if tail recursion is done properly the stack is "unwound" - the method just jumps back to the starting point with different values. Effectively there's recursion in the source code, but not in the compiled code. So there's precisely zero performance hit, and no chance of a stack overflow. It's how a functional language would deal with it.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7699
    
  20

Winston Gutkowski wrote:For starters, the classic recursive method will eventually throw a stack exception...

Actually, you know what: I take that back. It might not; but I can't be bothered to work out what the maximum factorial that will fit into a BigInteger is.

Winston
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38481
    
  23
Harsha Smith wrote: . . . now keep on calculating the sum while sum less than Math.E. something like this

. . .
That is not going to work, is it? And you ought not to work out the factorial every time.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7699
    
  20

Matthew Brown wrote:...but if tail recursion is done properly the stack is "unwound" - the method just jumps back to the starting point with different values. Effectively there's recursion in the source code, but not in the compiled code...

Ah, fair enough. I still don't see how it wouldn't be then equivalent to a regular loop, so I stick with my original post: good for instruction, bad for implementation.

Winston
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38481
    
  23
Winston Gutkowski wrote:. . . will eventually throw a stack exception...
. . . I can't be bothered to work out what the maximum factorial that will fit into a BigInteger is.

Winston
The size of stack probably varies from machine to machine. I once used BigInteger to work out Fibonacci numbers recursively and got overflow errors about 5000 terms.
There is no limit to the size of a BigInteger. There is a limit to the heap size, however.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7699
    
  20

Campbell Ritchie wrote:There is no limit to the size of a BigInteger. There is a limit to the heap size, however.

Ah, but there is my son: 2^36 bits (for BigInteger that is; and, for once, here I do know of which I speak, because I've yet to get Sun/Oracle to even acknowledge that there is a problem with BigInteger.bitLength() ).

Winston
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4371
    
    8

Winston Gutkowski wrote:Ah, fair enough. I still don't see how it wouldn't be then equivalent to a regular loop, so I stick with my original post: good for instruction, bad for implementation.


Well, then it comes down to readability. People that use functional languages regularly (and I'm not one of them, but I'm teaching myself Scala at the moment so I'm trying to get into thinking like that) reckon that style is easier to read. Your mileage may vary. It's certainly more concise.
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3615
    
  14

Winston Gutkowski wrote:
Matthew Brown wrote:...but if tail recursion is done properly the stack is "unwound" - the method just jumps back to the starting point with different values. Effectively there's recursion in the source code, but not in the compiled code...

Ah, fair enough. I still don't see how it wouldn't be then equivalent to a regular loop, so I stick with my original post: good for instruction, bad for implementation.

Winston

Well in that case you might argue that functional languages are bad for implementation, because in the end everything is equivalent to processor opcodes.
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3615
    
  14

Rob Spoor wrote:
Stephan van Hulst wrote:As of Java 7, recursion is very weak and it's definitely better to prefer iteration.

Got a source?

I'm sorry, I don't have sources, this is just my impression. I avoid recursion for the reason Winston states. It's much harder to make guarantees about what problems your code may solve without crashing.

My point was more that recursion is not by definition bad. Whether to use recursion or not depends on several factors. With tail calls, I would personally prefer the recursive way because it makes code much more readable.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7699
    
  20

@john: BTW, excuse this off-topic discussion. It often happen when geeks collide .

Winston
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7699
    
  20

Stephan van Hulst wrote:Well in that case you might argue that functional languages are bad for implementation...

I dont think I've said anything against functional languages - in fact I'd say my approach to Java is more functional than most - but I do believe in clarity of code.
And replacing a simple for loop with a recursive function fails right there for me; especially if I have to wait until version 9 for it to be anywhere close to as fast.

Winsaton
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38481
    
  23
I have tried a factorial program with BigInteger; it has gone beyond 480000! without crashing,
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4371
    
    8

Winston Gutkowski wrote:I dont think I've said anything against functional languages - in fact I'd say my approach to Java is more functional than most - but I do believe in clarity of code. And replacing a simple for loop with a recursive function fails right there for me;

Even if the recursive function is even simpler?
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7699
    
  20

Campbell Ritchie wrote:I have tried a factorial program with BigInteger; it has gone beyond 480000! without crashing,

Blimey, you must have a fair old box. I'd probably be having cups of tea in between results on mine after it got to 50,000 or so. I was actually wondering what the formula would be - an arithmetic series of logs I suspect - but do tell if you hit the limit.

Winston
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7699
    
  20

Matthew Brown wrote:Even if the recursive function is even simpler?

Simplicity is in the eye of the beholder:
return n < 2 ? 1 : n * factorial(n-1);
may be concise; but I'd argue that it's far from simple.

If you don't believe me, check out the C implementation for getchar() - incredibly clever (and probably blisteringly fast too), and done in half a line of code - but it took me about three quarters of an hour to work out what it was doing. That's not clarity as far as I'm concerned.

Winston
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38481
    
  23
2^36? That must be 2^5 bits per digit and 2^31 digits. I think I shall run out of heap space before I reach that many. And bitLength()? You can fit 2^36 into a int, surely
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7699
    
  20

Campbell Ritchie wrote:I think I shall run out of heap space before I reach that many...

Which I'm quite sure is why they (Sun/Oracle) don't have it high on their list of priorities; but I am surprised that they've never acknowledged it as a potential problem. Maybe I'm not the first to report it and they're waiting for JVM128 or quantum processors... .

Winston
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3615
    
  14

You're right, usually clarity is in the eye of the beholder. Personally I don't really find either version of the function more difficult than the other. I would argue most mathematicians would find the recursive function more simple.

Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7699
    
  20

Stephan van Hulst wrote:You're right, usually clarity is in the eye of the beholder. Personally I don't really find either version of the function more difficult than the other. I would argue most mathematicians would find the recursive function more simple.

Really? Practise I suppose. I always found recursion quite tough, and still do when it's non-trivial, so I tend to use it only when I know it makes sense (oddly, I'm actually writing one at the moment - Sod's Law ). And I'd still take some convincing to use it for factorials.

Winston
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4371
    
    8

Winston Gutkowski wrote:Really? Practise I suppose. I always found recursion quite tough, and still do when it's non-trivial, so I tend to use it only when I know it makes sense (oddly, I'm actually writing one at the moment - Sod's Law ). And I'd still take some convincing to use it for factorials.

I think Stephan's right. My background is in mathematics, and (possibly due to having proof-by-induction rammed into me over and over again), I think of the very definition of factorial as being recursive. Which is why in this case I prefer it - it's the approach that most closely represents the semantics of the function as I understand it. But I can understand people thinking differently.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38481
    
  23
I never knew Sod’s Law was recursive.
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4371
    
    8

Campbell Ritchie wrote:I never knew Sod’s Law was recursive.

If anything can go wrong, it can go wrong?
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38481
    
  23
That looks like a recursive tautology And it’s transitively closed. Should I move this thread to diversions or MD?
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7699
    
  20

Campbell Ritchie wrote:I never knew Sod’s Law was recursive.

Sorry, bad grammer. It seemed to me that while arguing that I don't use recursive functions if I can avoid them, having to admit that I'm currently writing one(*) was an example of Sod's Law - although it seems quite reasonable to me that it would be (and certainly Sod's Law for someone like me).

Winston

(*) not factorial().
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: Is my prof trolling me? (factorials, loops)