Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
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 chilling in the Monastery: (3)
As of 2014-07-12 23:50 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    When choosing user names for websites, I prefer to use:








    Results (242 votes), past polls