+- Hack Forums (https://hackforums.net)
+-- Forum: Tech (https://hackforums.net/forumdisplay.php?fid=444)
+--- Forum: Coding (https://hackforums.net/forumdisplay.php?fid=151)
+---- Forum: Coders Lounge (https://hackforums.net/forumdisplay.php?fid=5)
+---- Thread: Performance of Logarithm vs Recursive calculations. (/showthread.php?tid=5341773)
Performance of Logarithm vs Recursive calculations. - severos - Jul 17, 2016
I'm writing a function that have some calculations, those can be solved using either a Log(base, value) function, or recursive calls.
From performance view point, which one is better to use??
I know that writing a single Log() line is way much readable, but a friend told me that Log calculations can take long time depending on value.
* - ng-Coder - Jul 17, 2016
(Jul 17, 2016 04:46 AM)severos Wrote: I'm writing a function that have some calculations, those can be solved using either a Log(base, value) function, or recursive calls.
From performance view point, which one is better to use??
I know that writing a single Log() line is way much readable, but a friend told me that Log calculations can take long time depending on value.
First this is nifty pick that's only crucial when we're talking of core graphics engine, big games or some sort.
Recursive function may make shorter code to that of Logarithm but don't just conclude that makes it faster or better in performance point of view.
This depends on what sort of calculation this function of yours is to be doing.
You have to pay a price for recursively calling a function as it consumes more time than adjusting a loop counter by logarithm.
Read this: http://www.eecs.yorku.ca/course_archive/2010-11/W/2011/Notes/s2_recursion.pdf
You can search for more info about this on Google.
.
* - severos - Jul 17, 2016
Quote:First this is nifty pick that's only crucial when we're talking of core graphics engine, big games or some sort.It's not a graphic related thing, more of calculation for some storage management system.
Quote:This depends on what sort of calculation this function of yours is to be doing.The calculations, it's doing nesting levels of files and directories to find a perfect fit.
Using recursive is pretty tempting but I'm afraid of the cases where something might go wrong and pass some large number that would cause stack over flow. Also there's the extra time/storage for each call stack frame.
I've already tried googling things like "logarithm vs recursion performance" but ended up with things explaining what recursion is and someone asking about recursion with logarithmic time complexity, never got things related to my question :/
I'm not new to programming, just posted this here since it's not a language dependent problem.
* - stugz - Jul 17, 2016
IIRC, Knuth covers logarithms in Vol. 1 of TAOCP. He also presents an algorithm to calculate them. Perhaps, that might be a useful avenue to explore. I cannot comment on your specific requirement in comparing performance but knowing Knuth - his algorithm should be efficient.
* - ng-Coder - Jul 17, 2016
(Jul 17, 2016 08:00 AM)severos Wrote: It's not a graphic related thing, more of calculation for some storage management system.
The calculations, it's doing nesting levels of files and directories to find a perfect fit.
Using recursive is pretty tempting but I'm afraid of the cases where something might go wrong and pass some large number that would cause stack over flow. Also there's the extra time/storage for each call stack frame.
I apologise for telling you google 🙂, I think you're better off to go with iterative module with self managed stack-like memory in this situation.
You can see how Microsoft construct and manage its resource tree, this should be easier and safer than forcing tail recursion or relying on recursion counter.
1. Build the tree/structure of the storage system.
2. The iterating function alter global state of the structure by growing the tree branch by branch, all this can be implement with while loop on for loop inside the iterating module.
I wish I can afford to draft sameple for this here but, sorry.
.