in reply to Re^7: OT: Finding Factor Closest To Square Root
in thread OT: Finding Factor Closest To Square Root
To see the problem, add the following line:my $N = shift; my $sqrt = sqrt( $N ); my @factor = prime_factors( $N ); return 1 if @factor == 1; # ... rest of the code return $f < $sqrt ? $f : undef;
And to see the problem go away:my $N = shift; my $sqrt = sqrt( $N ); my @factor = prime_factors( $N ); # ADD THIS LINE print "$_\n" for @factor; return 1 if @factor == 1; # ... rest of the code return $f < $sqrt ? $f : undef;
You can see the list of factors changes with the presence of the sqrt() code (at least it does on my machine).my $N = shift; my @factor = prime_factors( $N ); # KEEP THIS LINE print "$_\n" for @factor; return 1 if @factor == 1; # ... rest of the code return $f;
Cheers - L~R
|
|---|
| Replies are listed 'Best First'. | |
|---|---|
|
Re^9: OT: Finding Factor Closest To Square Root
by BrowserUk (Patriarch) on Feb 26, 2005 at 15:00 UTC | |
Hmm. I get the same results both ways:
Which version of Parei do you have? I have
It's kind of hard to see how using the built in sqrt function would influence factorint()> but have you tried moving the call to sqrt after the call to factorint()? Anyway, trying to get beyond that, I picked a few ideas from tall_man's code (which is definitely the benchmark in this thread) and modified your code to read as:
As I understand it, ':int', makes all integers in the program Pari compatible?. And using sqrtint() ought to bypass any imcompatibilities. The fudge with $ARGV[ 0 ] at the top allows me to test the code on some really big numbers without having to type out all the digits--I applied the same hack to tall_man's code, and then ran a few tests. The following is the results from a few carefully chosen (particularly hard) examples timing both programs. Going by the time your program takes in comparison to tall_man's, you appear to be doing a similar amount of work, but your code is returning -1, which I do not understand?
The timings of these two particularly difficult runs, going by how long tall_man'code takes relative to most other runs like:
which despite being nearly as big a number, is solved in under a 1/5th of a second rather than 17+ seconds above. The very close similarity in timing between your code and tall_man's suggests that you are probably doing a very similar amount of work and possibly arriving at the same result, but for some reason, failing to display it?. Maybe a rounding error somewhere. I tried to follow this through--but as you know your code better than I, you might find the solution more quickly. Either way, your determination of the appropriate sequence of tests and short-ciruiting is very impressive. I congratulate you++ :). Examine what is said, not who speaks.
Silence betokens consent.
Love the truth but pardon error.
| [reply] [d/l] [select] |
by Limbic~Region (Chancellor) on Feb 27, 2005 at 14:29 UTC | |
Hmm. I get the same results both ways: While I might expect a different environment not to expose the bug, I am suprised that neither run gave correct results. On my machine, for 24777695232, I get: Read more... (304 Bytes)
Which version of Parei do you have?
...have you tried moving the call to sqrt after the call to factorint()?
Anyway, trying to get beyond that, I picked a few ideas from tall_man's code (which is definitely the benchmark in this thread) and modified your code to read as:
Going by the time your program takes in comparison to tall_man's, you appear to be doing a similar amount of work, but your code is returning -1, which I do not understand?
...which despite being nearly as big a number, is solved in under a 1/5th of a second rather than 17+ seconds above. The very close similarity in timing between your code and tall_man's suggests that you are probably doing a very similar amount of work and possibly arriving at the same result, but for some reason, failing to display it?.
Read more... (387 Bytes)
And then just add a test at the top for $ARGV[0] and loop on the file if not present.
Either way, your determination of the appropriate sequence of tests and short-ciruiting is very impressive. I congratulate you++
Cheers - L~R | [reply] [d/l] [select] |
by BrowserUk (Patriarch) on Feb 27, 2005 at 16:10 UTC | |
Yeah, doing a binary search on 5 numbers is bound to be faster than generating all the combinations and determining the product, but I still don't get anywhere near the 17+ seconds you see You didn't read the output carefully did you :) My point was that for the number '100000000000000000000000000000000000000000000000000000000001', both your code and tall_man's ran for 17.578 seconds. Similarly, for '100000000000000000000000000000000000000000000000000000001' both ran for 3.265 seconds. And for '10000000000000000000000000000000000000000000000000000000001' both ran for under 1/5th of a second. The reason for moving to such big numbers was to try and find values that made the algorithm work very hard, so as to benchmark the algorithm rather than the implementation. The conclusion that I was attempting to draw was that whilst your code wasn't displaying the correct final result, that both programs were taking nearly identical times to run--longer when the task was harder, shorter when simpler; and always within a few fractions of a second--and that your code was probably doing all the right work and just failing display the final result correctly. Which is all the more impressive as your program is doing the work in Perl rather than C as with tall_man's code. In other words, I was trying to pay you a complement. Update: As it turns out, all of the time taken is to calculate the prime factors, with almost nothing to determine the nearest factor. Oh well! Examine what is said, not who speaks.
Silence betokens consent.
Love the truth but pardon error.
| [reply] |