Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses
 
PerlMonks  

Re^5: OT: Finding Factor Closest To Square Root

by Limbic~Region (Chancellor)
on Feb 24, 2005 at 17:12 UTC ( #434153=note: print w/ replies, xml ) Need Help??


in reply to Re^4: OT: Finding Factor Closest To Square Root
in thread OT: Finding Factor Closest To Square Root

Roy Johnson,
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.

Cheers - L~R


Comment on Re^5: OT: Finding Factor Closest To Square Root

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://434153]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (8)
As of 2015-07-08 02:32 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (93 votes), past polls