My original algorithm (the core part of it using Euclid method of finding GCD) is not recursive, it's iterative, pretty much the same as yours. The local variable GCD has the same name as the function (which probably caused your confusion), but the function does not call itself, because the local var declaration takes precedence. So, this is the same iterative method. To avoid the confusion, just rename it to whatever you want, like for example, _GCD, or _gcd, etc.
I ask you kindly: please DO NOT post anything else to this comments thread, I am closing it now. This seemingly everlasting discussion has, IMHO, very little added value and starts looking more and more like some artificial problem/solution very much out of context. In case you value your opinion/suggestion more than my original solution and my following rather detailed comments/explanation, then please post your own tips outside of my comment thread.
Regarding my previous post: obviously I was talking about VB6 (which was the last one before VB.NET arrived), still often referred as simply "VB". You point (1) is just a re-wording of my statement about default passing parameters ByRef in VB; essentially it's correct and in full compliance with my original statement.
The core idea of my statement was simple: do not modify the original parameters passed to the GCD computational algorithm, regardless of potential language specifics of passing parameters.
1. Apparently I refer to "null" (re: "...to check if the result is null") as mathematical term, which is obvious from the code fragment (b!=0); this line is present in my original article and then repeated exactly in your code snippet, so I do not understand the source of confusion.
2. "Stack space" is not the only and by the way, not a primary optimization criteria in modern SW engineering.
3. Code branching is absolutely valid approach; in this particular case it helps significantly reduce the "number crunching" load on the system.
4. In average, my algorithm provide much better performance in a wide range of numbers than that "truncated" version you have described.
Thanks for your comments and have a great day.
Dr.Abell, int is a value type which can never be null. The bit work you perform with AND and OR and the multiple branches of the code result is a less optimzed function call which utilizes more stack space. These are the hard facts of the matter.
Thanks for your comment, but I still think that simple comparison of two integers will run much faster than performing modulo operation first and then still making comparison to check if the result is null. The original algorithm is optimized for speed and utilizes just a microscopic amount of memory, comparing with digital estate of any modern computer. Thus, I would prefer to stay with original solution; if I decide to improve performance further, then I will replace Euclidean algorithm with some others, more complex and also more efficient. But, from practical prospective, this one is doing pretty good job and could be recommended for use in fraction operations.
1.) You are claiming that if both numbers are equal the Euclid part does not need to be run however I am arguing that rather than performing a binary AND followed by a jump if equal or just the jump if equal call you just perform the modulo which will result in a single operation and get the required result which will be much easier for the JITTER to optimize due to less possible branches of code paths to evaluate.
2.) I did not write alternate 1 so I do not care to make points about it.
3.) I have also made this discovery when working on a brain teaser at my work.
4.) Due to recursive calling there is more stack space utilized in your function call.
1. There are 3 reasons given: which one you are talking about (please be specific)?
2. Regarding your example of two equal numbers 1,1: still my algorithm will work correctly and provide better performance.
3. LCM (or LCD) calculation based on GCD is correct; this is the trivial functional relationship used in Fraction Calculator (that was, obviously, the reason to calculate GCD first and then use it in fraction arithmetic).
I am not sure how correct your assertation is... I dont' use var once. I accept the point about the two numbers being the same but I would like to see how that realtes to the problem mathematically. E.g. so what if I pass 1,1? is this not the point of the algorithm...
I would NOT recommend the Alternate 3 for several reason:
1.GCD calculation in Alternate 3 is just a truncated version of the ORIGINAL one (using the same Euclid algorithm, slightly re-written in terms of vars naming), and it's lacking the safety/performance boost provided in ORIGINAL one by the thorough validating/checking of initial conditions: for example, there is no need to run the Euclid part if both numbers are the same, or if the smaller number is GCD, etc.).
2. Alternate 1 is less portable and less safe because it could create a mess with parameters a and b: some languages (e.g. VB) by default use ByRef instead of byBal, so the values a and b could get corrupted in some programming languages.
3. Least Common Multiple (LCM), also known as LCD (Least Common Denominator) calculation shown in Alternate 3 is correct; it is based on the GCD computation and a trivial relationship like: LCD = value1 * value2 / GCD (value1, value2), which is actually implemented in a fraction calculator. I am going to publish the full-size article on several core algorithms, pertinent to the Fraction Calculator and Prime Factoring, covering all these topics.
Thanks and regards,
Last Visit: 31-Dec-99 19:00 Last Update: 28-Dec-14 12:58