Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much
 
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 romping around the Monastery: (6)
As of 2014-09-23 07:00 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (210 votes), past polls