Show 40 post(s) from this thread on one page
Page 2 of 3 First 123 Last
• Apr 20th 2010, 12:58 AM
CaptainBlack
Quote:

Originally Posted by superdude
I think I'm getting the idea. So when you say n=O(log(N)) you're giving a particular example? You're not saying, whenever a subroutine depends on length of the argument then its big O is n=O(log(N)), that's not what you're saying?

For example, knowing that if a number does not have a factor less than or equal to its square root, the number if prime, an algorithm implementing this idea would have big O of $\displaystyle \sqrt{n}$ and a person would write O(n) where [mant]n=\sqrt(N)[/tex] and a person would speak "the algorithm has an efficiency of big O of square-root-n"?

What is an appropriate measure of the size of the problem depends on the problem.

CB
• Apr 20th 2010, 01:43 AM
undefined
Quote:

Originally Posted by superdude
2702811 also crashes the program. I notice 3 is a common factor in both cases.

I like how there are a couple conversations going on at once here, heh.

I copied and pasted your code for use with my XAMPP setup and got problems with 2702811 sometimes but not always, and I wasn't able to get an error with 15999.

To tell the truth, I don't understand the logic of your code, but I notice that the two functions call each other an awful lot.

It seems like you're not doing anything more complex than trial division, so what do you think of this instead?

[php]
<?php
$num = 342132; if ($num < 2) {
echo "No prime factors.";
exit;
}
echo "The prime factorization of " . $num . " is:<br />"; while ($num % 2 == 0) {
echo "2<br />";
$num /= 2; } while ($num % 3 == 0) {
echo "3<br />";
$num /= 3; }$lim = floor(sqrt($num)); for ($i = 5, $inc = 2;$i <= $lim;$i += $inc,$inc = 6 - $inc) { if ($num % $i == 0) { echo$i . "<br />";
$num /=$i;
while ($num %$i == 0) {
echo $i . "<br />";$num /= $i; }$lim = floor(sqrt($num)); } } if ($num != 1) echo $num; ?> [/php] Note: I introduce$inc in order to avoid numbers congruent to 0 (mod 3).
• Apr 20th 2010, 02:12 AM
CaptainBlack
Quote:

Originally Posted by undefined
I like how there are a couple conversations going on at once here, heh.

I copied and pasted your code for use with my XAMPP setup and got problems with 2702811 sometimes but not always, and I wasn't able to get an error with 15999.

To tell the truth, I don't understand the logic of your code, but I notice that the two functions call each other an awful lot.

It seems like you're not doing anything more complex than trial division, so what do you think of this instead?

Code:

<?php $num = 342132; if ($num < 2) {   echo "No prime factors.";   exit; } echo "The prime factorization of " . $num . " is:<br />"; while ($num % 2 == 0) {   echo "2<br />";   $num /= 2; } while ($num % 3 == 0) {   echo "3<br />";   $num /= 3; }$lim = floor(sqrt($num)); for ($i = 5, $inc = 2;$i <= $lim;$i += $inc,$inc = 6 - $inc) { if ($num % $i == 0) { echo$i . "<br />";     $num /=$i;     while ($num %$i == 0) {       echo $i . "<br />";$num /= $i; }$lim = floor(sqrt($num)); } } if ($num != 1) echo $num; ?> Note: I introduce$inc in order to avoid numbers congruent to 0 (mod 3).

Edit: Can anyone tell me how to get the syntax highlighter? I'm searching around for the bbcode...

Consider semi-primes of the form $\displaystyle n=2 \times p$ or $\displaystyle n=3 \times p$ where $\displaystyle p$ is a prime greater than $\displaystyle 5$.

Note that $\displaystyle p>\sqrt{n}$ which looks like it will crash your algorithm.

I would guess that $\displaystyle 31998$ may also give this problems.

I would conjectute that any number of the form $\displaystyle 2^n3^mp$ where $\displaystyle p>2^n3^m$ is a prime will give problems (this is a conjecture because I cant be bothered to analyse such horrible code in detail)

CB
• Apr 20th 2010, 02:21 AM
undefined
Quote:

Originally Posted by CaptainBlack
Consider semi-primes of the form $\displaystyle n=2 \times p$ or $\displaystyle n=3 \times p$ where $\displaystyle p$ is a prime greater than $\displaystyle 5$.

Note that $\displaystyle p>\sqrt{n}$ which looks like it will crash your algorithm.

CB

Suppose n = 14, then the program will first divide out all the 2's, so that $lim = floor(sqrt(7)) = 2. The program will effectively skip the main loop and then correctly conclude that 7 is prime and print it as one of the factors. Edit: This stuff was added afterwards Quote: Originally Posted by CaptainBlack I would guess that$\displaystyle 31998$may also give this problems. I would conjectute that any number of the form$\displaystyle 2^n3^mp$where$\displaystyle p>2^n3^m$is a prime will give problems (this is a conjecture because I cant be bothered to analyse such horrible code in detail) CB 31998 worked fine. If my code is so horrible, let's see yours. Oh and for the conjecture,$\displaystyle 745848 = 2^3*3^4*1151$works just fine as well. • Apr 20th 2010, 02:29 AM CaptainBlack Quote: Originally Posted by undefined Suppose n = 14, then the program will first divide out all the 2's, so that$lim = floor(sqrt(7)) = 2. The program will effectively skip the main loop and then correctly conclude that 7 is prime and print it as one of the factors.

Edit: This stuff was added afterwards

31998 worked fine. If my code is so horrible, let's see yours.

The horror of the code may be a result of using watever language that is in, or it may be the result of a poorly thought out algorithm I can't tell.

If you had an algorithm spec in a more comprehensible language or psuedo-code I would have more confidence in it being the language rather than the algorithm.

CB
• Apr 20th 2010, 02:49 AM
undefined
Quote:

Originally Posted by CaptainBlack
The horror of the code may be a result of using watever language that is in, or it may be the result of a poorly thought out algorithm I can't tell.

If you had an algorithm spec in a more comprehensible language or psuedo-code I would have more confidence in it being the language rather than the algorithm.

CB

Fair enough, although PHP is quite common. Here's Java:

Code:

public ArrayList<Integer> naiveFactorise(int n) {     // returns prime factors in ascending order, duplicates allowed     ArrayList<Integer> pFacts = new ArrayList<Integer>();     if (n < 2) return pFacts;     while (n % 2 == 0) {         pFacts.add(2);         n /= 2;     }     while (n % 3 == 0) {         pFacts.add(3);         n /= 3;     }     int lim = (int)Math.sqrt(n);     for (int i = 5, inc = 2; i <= lim; i += inc, inc = 6 - inc) {         if (n % i == 0) {             pFacts.add(i);             n /= i;             while (n % i == 0) {                 pFacts.add(i);                 n /= i;             }             lim = (int)Math.sqrt(n);         }     }     if (n != 1) pFacts.add(n);     return pFacts; }
The reason 2 and 3 are treated specially is to ease incrementing the loop variable; otherwise they would be included in the main loop like all the other prime candidates.

Edit: For clarification, from my first post I've been writing about a program to produce the prime factorization of n using trial division. Although the OP said the original goal was merely to decide prime vs. composite, the functionality of the program posted by the OP was to produce all the prime factors with multiplicity, so that's what I went by. Obviously the decision problem is easier and simpler. This might have contributed to my code seeming "horrible."
• Apr 20th 2010, 02:54 AM
CaptainBlack
Quote:

Originally Posted by superdude
This was one of the first programs I made and it was a number of years ago. My style was very poor(Doh)
here's the relevant code. primefind gets called first with the first argument being the number in question, startnum is initially 1, and handel is unrelated to prime factoring:

Unless you are dealling with very large numbers or speed is of the essense keep it simple:

Code:

function IsPrm(num) // //  psuedo-code for crude primallity testing // //  assumption: num is an integer type //   if (num<=1)     return false   end     if (num==2)     return true   elseif (mod(num,2)==0)     return false   end     for idx=3 to floor(sqrt(num)) step 2       if mod(num,idx)==0           return false       end   end     return true   endfunction
There are more efficient ways to do it but do you need efficiency?

CB
• Apr 20th 2010, 10:46 AM
superdude
Quote:

Originally Posted by CaptainBlack
Unless you are dealling with very large numbers or speed is of the essense keep it simple:

Code:

function IsPrm(num) // //  psuedo-code for crude primallity testing // //  assumption: num is an integer type //   if (num<=1)     return false   end     if (num==2)     return true   elseif (mod(num,2)==0)     return false   end     for idx=3 to floor(sqrt(num)) step 2       if mod(num,idx)==0           return false       end   end     return true   endfunction
There are more efficient ways to do it but do you need efficiency?

CB

I realize that both my logic and style where very poor for this program. I have written a much more elegant prime factoring program and if you like I can post it. Efficiency is not an issue, if it was I'd use this. My question that I'm asking is why do certain numbers crash the program?
• Apr 20th 2010, 11:04 AM
undefined
Quote:

Originally Posted by superdude
I realize that both my logic and style where very poor for this program. I have written a much more elegant prime factoring program and if you like I can post it. Efficiency is not an issue, if it was I'd use this. My question that I'm asking is why do certain numbers crash the program?

I don't have a definitive answer (debugging your code slows down my system so it's a bit of a pain), but your two functions call each other a huge number of times in general, so maybe there is a situation where a stop condition is accidentally skipped and you are left with infinite recursion. If I were you I would introduce global variables to keep track of function calls, and periodically print out the values of the key variables, either as soon as the function is called, or within the loops, or both, to try to catch runaway recursion. In the process you might spot an issue such as integer overflow, if such a problem exists. And of course, infinite recursion is essentially the same as an infinite loop, which might be the culprit.
• Apr 20th 2010, 11:07 AM
superdude
Quote:

Originally Posted by undefined
I don't have a definitive answer (debugging your code slows down my system so it's a bit of a pain), but your two functions call each other a huge number of times in general, so maybe there is a situation where a stop condition is accidentally skipped and you are left with infinite recursion. If I were you I would introduce global variables to keep track of function calls, and periodically print out the values of the key variables, either as soon as the function is called, or within the loops, or both, to try to catch runaway recursion. In the process you might spot an issue such as integer overflow, if such a problem exists. And of course, infinite recursion is essentially the same as an infinite loop, which might be the culprit.

The strange thing is with 15999 the program crashes even if the first thing is to print something to the screen. That is if step 1 is print("hello world") the program will not do that for 15999.
• Apr 20th 2010, 11:20 AM
undefined
Quote:

Originally Posted by superdude
The strange thing is with 15999 the program crashes even if the first thing is to print something to the screen. That is if step 1 is print("hello world") the program will not do that for 15999.

Then perhaps the error lies somewhere outside the block of code you posted, because I ran it as-is and never got that problem.

I find it extremely unlikely that my version of PHP would behave that much differently from yours and that it's a bug with the PHP interpreter, although I suppose it can't be ruled out entirely without further testing.
• Apr 20th 2010, 11:25 AM
superdude
This is my new version. I'm looking for criticism:
[PHP]
<?php
$num = 15999; if($num%2 != 0 && $num%3 != 0 && isPrime($num))
{
print($num.' is prime'); exit; } print('The primefactorization of '.$num.' is:<br />');
checkSmallPrimes($num, 2);//factors out 2s checkSmallPrimes($num, 3);//factors out 3s
for($i = 5;$i <= floor(sqrt($num));$i += 2)
{
if(isPrime($i)) { while($num%$i==0)//having this as a while loop instead of if increases efficency {$num = $num/$i;
print($i.'<br />'); } if(isPrime($num))
{
print($num); exit; } } } /*returns true if agrument is prime greater than 3, otherwise returns false*/ function isPrime($maybePrime)
{
for($j = 3;$j <= floor(sqrt($maybePrime));$j += 2)
if($maybePrime%$j == 0)
return false;
return true;
}

//$num is being passed by reference function checkSmallPrimes(&$num, $smallPrime) { while($num%$smallPrime==0) {$num /= $smallPrime; print($smallPrime.'<br />');
}
}
?>[/PHP]
• Apr 20th 2010, 11:27 AM
superdude
Quote:

Originally Posted by undefined
Then perhaps the error lies somewhere outside the block of code you posted, because I ran it as-is and never got that problem.

I find it extremely unlikely that my version of PHP would behave that much differently from yours and that it's a bug with the PHP interpreter, although I suppose it can't be ruled out entirely without further testing.

I said it only happens using EasyPHP 1.8. I've reproduced the problem on different computers (with different architecture) so you must be doing something wrong.
• Apr 20th 2010, 12:15 PM
undefined
Quote:

Originally Posted by superdude
I said it only happens using EasyPHP 1.8. I've reproduced the problem on different computers (with different architecture) so you must be doing something wrong.

Sorry, I missed that part. I've never had to debug a language interpreter before, and I don't intend to replace my current PHP with one that is potentially buggy, so I guess I won't be of much help on that.

Quote:

Originally Posted by superdude
This is my new version. I'm looking for criticism:

A small consistency issue: It seems that the program says "$num is prime" when$num is prime and > 3, but if $num == 2 or$num == 3, it will output its prime factorization rather than telling you it's prime.

I don't understand why you treat 3 as a special case; you could just start your loops at 3 instead of 5. The reason I treated 3 as special was because my increment scheme avoided multiples of 3 other than 3, thus I checked the numbers 2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, ... where the differences between two successive terms are 2 and 4 alternating, but starting with 5. This is just an optimization.

Also, I'm not sure if this is a real optimization or not, but I tend to pre-calculate the loop limit floor(sqrt($blah)) as another variable to prevent re-calculating the same thing many times -- possibly a given compiler/interpreter would do this anyway, depends on how smart it is I guess. There's another inefficiency I noticed: you call isPrime() from within the main for() loop (the one that's not contained in a function), and you start trial division over at 5, but in reality it's impossible to have factors between 5 and$i of the main loop because you've divided them out already.

Also, you only call checkSmallPrimes() twice, but the while() loop inside your main for() loop has identical code. If you're going to encapsulate that code as a function, you might as well just call checkSmallPrimes() each time, possibly renaming it to reflect what it does more closely.

One final optimization I can see is that, for composite $num, at the beginning you call isPrime() and trial divide by 2 and all odd numbers up to sqrt($num), and then you do the exact same thing (starting at 5) in the main for() loop. It would be more efficient to keep a boolean value for primality, starting it at true and then setting it to false as soon as a factor < $num is found, thus combining the two loops into one. One last very small point is that using the variable name$maybePrime inside a function called isPrime() seems redundant to me.

Hope you don't mind my tearing apart your code... it's all meant constructively.
• Apr 21st 2010, 11:03 AM
superdude
Quote:

Originally Posted by undefined
Sorry, I missed that part. I've never had to debug a language interpreter before, and I don't intend to replace my current PHP with one that is potentially buggy, so I guess I won't be of much help on that.

A small consistency issue: It seems that the program says "$num is prime" when$num is prime and > 3, but if $num == 2 or$num == 3, it will output its prime factorization rather than telling you it's prime.

I don't understand why you treat 3 as a special case; you could just start your loops at 3 instead of 5. The reason I treated 3 as special was because my increment scheme avoided multiples of 3 other than 3, thus I checked the numbers 2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, ... where the differences between two successive terms are 2 and 4 alternating, but starting with 5. This is just an optimization.

Also, I'm not sure if this is a real optimization or not, but I tend to pre-calculate the loop limit floor(sqrt($blah)) as another variable to prevent re-calculating the same thing many times -- possibly a given compiler/interpreter would do this anyway, depends on how smart it is I guess. There's another inefficiency I noticed: you call isPrime() from within the main for() loop (the one that's not contained in a function), and you start trial division over at 5, but in reality it's impossible to have factors between 5 and$i of the main loop because you've divided them out already.

Also, you only call checkSmallPrimes() twice, but the while() loop inside your main for() loop has identical code. If you're going to encapsulate that code as a function, you might as well just call checkSmallPrimes() each time, possibly renaming it to reflect what it does more closely.

One final optimization I can see is that, for composite $num, at the beginning you call isPrime() and trial divide by 2 and all odd numbers up to sqrt($num), and then you do the exact same thing (starting at 5) in the main for() loop. It would be more efficient to keep a boolean value for primality, starting it at true and then setting it to false as soon as a factor < $num is found, thus combining the two loops into one. One last very small point is that using the variable name$maybePrime inside a function called isPrime() seems redundant to me.

Hope you don't mind my tearing apart your code... it's all meant constructively.

You have some valuable suggestions. Can you elaborate on how your increment scheme avoids multiples of 3 and how you know you won't miss any primes in between? So how do you know alternating between adding 2 and 4 skips multiples of 3? I'm busy today so I'll consider your suggestions in more depth and post back in a day or two.
Show 40 post(s) from this thread on one page
Page 2 of 3 First 123 Last