Forums Register Login

Is my prof trolling me? (factorials, loops)

+Pie Number of slices to send: Send
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?
+Pie Number of slices to send: Send
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.
1
+Pie Number of slices to send: Send
 

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
+Pie Number of slices to send: Send
 

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!

+Pie Number of slices to send: Send
 

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

+Pie Number of slices to send: Send
 

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
+Pie Number of slices to send: Send
What's with the Math.abs(0) and Math.abs(1) calls? Why not just write their equivalents 0 and 1?
+Pie Number of slices to send: Send
 

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
+Pie Number of slices to send: Send
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

1
+Pie Number of slices to send: Send
 

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
+Pie Number of slices to send: Send
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.
+Pie Number of slices to send: Send
 

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


Got a source?
+Pie Number of slices to send: Send
 

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
+Pie Number of slices to send: Send
 

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.
+Pie Number of slices to send: Send
 

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
+Pie Number of slices to send: Send
 

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.
+Pie Number of slices to send: Send
 

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
+Pie Number of slices to send: Send
 

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.
+Pie Number of slices to send: Send
 

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
+Pie Number of slices to send: Send
 

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.
+Pie Number of slices to send: Send
 

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.
+Pie Number of slices to send: Send
 

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.
+Pie Number of slices to send: Send
@john: BTW, excuse this off-topic discussion. It often happen when geeks collide .

Winston
+Pie Number of slices to send: Send
 

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
+Pie Number of slices to send: Send
I have tried a factorial program with BigInteger; it has gone beyond 480000! without crashing,
+Pie Number of slices to send: Send
 

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?
+Pie Number of slices to send: Send
 

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
1
+Pie Number of slices to send: Send
 

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
+Pie Number of slices to send: Send
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
+Pie Number of slices to send: Send
 

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
+Pie Number of slices to send: Send
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.

+Pie Number of slices to send: Send
 

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
+Pie Number of slices to send: Send
 

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.
+Pie Number of slices to send: Send
I never knew Sod’s Law was recursive.
+Pie Number of slices to send: Send
 

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


If anything can go wrong, it can go wrong?
+Pie Number of slices to send: Send
That looks like a recursive tautology And it’s transitively closed. Should I move this thread to diversions or MD?
+Pie Number of slices to send: Send
 

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().
machines help you to do more, but experience less. Experience this tiny ad:
a bit of art, as a gift, the permaculture playing cards
https://gardener-gift.com


reply
reply
This thread has been viewed 1900 times.
Similar Threads
having trouble with a fraction program
Need Explanation of unpredicted output even if methods are synchronized
Integer.Min_value
cannot understand the exception in my code,please help
doubts getting exponentially INCREMENTed
More...

All times above are in ranch (not your local) time.
The current ranch time is
Mar 28, 2024 23:11:26.