in reply to
Re^4: OT: Finding Factor Closest To Square Root
in thread OT: Finding Factor Closest To Square Root
I am pretty sure that all combinations need to be considered initially as you can see by my contributions elsewhere in this thread. It is possible to short-circuit early in some cases though, which may be a significant improvement. For instance - here are some ideas:
- Prior to determining the product of each combination, you can abort if you have already seen this combination
- When determining the product of each combination, you can abort if the value is greater than the sqrt
- If combinations are gathered left to right, once you have determined that the product of a given combination is greater than the sqrt() all future combinations that include this combination can be skipped
I have only chosen to implement the first 1 in my Perl code. This is because my combinations aren't gathered left to right. I will see if I can't modify the code to take advantage of all 3 of these short cuts.