Code Challenge! "The Prime Directive"

[ca_redwards]

Code Challenge! "The Prime Directive"
(pun mostly for Borgtex benefit!)

Welcome to a new non-RegExp Code Challenge!

The Challenge --------------
Create a function that returns the prime factorization of its
parameter. Prime numbers are those whose only factors are
themselves and one!


function prime(p)
{
/* your code here! */
}



prime(2) returns 2
prime(33) returns 3*11
prime(444) returns 2*2*3*37
prime(5555) returns 5*11*101
prime(66666) returns 2*3*41*271
prime(777777) returns 3*7*7*11*13*37
prime(8888888) returns 2*2*2*239*4649
prime(99999999) returns 3*3*11*73*101*137
prime(111111111) returns 3*3*37*333667
prime(2222222222) returns 2*11*41*271*9091


Keep this in mind... You ought to be able to eval() your result to
get back the original parameter!

Hints/suggestions: Brush up on your math knowledge!

Bonus points if your code returns its result before issuing a script
timeout warning!

The Rules --------------
Violation of these rules will result in disqualification.

Submissions must be 100% ECMAscript compliant. Code must be
self-contained and run error-free on IE5, NS6 (or NS7), and MZ1.

Once you've submitted your code, you're done. Do not edit your
submission.

Grading
Submitted code will be graded on a scale from 1 to 10. Attention
will be paid to the functionality, efficiency, simplicity, and brevity
of your approach.

The deadline for this challenge is February 15, 2003.

Good luck! :thumbsup:

[jkd]

Originally posted by ca_redwards
Welcome to a new non-RegExp Code Challenge!

Why non-RegExp? Got something against them? :p

Anyway, this is one thing Javascript is certainly not good for.

I mean, do you expect Javascript to be able to calculate that 2^13,466,917 - 1 is a prime number? No. How do you prime factorize numbers? It isn't a trivial task, and that's why calculating these primes takes a long time, even if written in efficient C code.

[Algorithm]

Short and sweet.function prime(p){
if(typeof(p)!='number' || isNaN(p)) return 'NaN';
p = Math.round(p);
if(p<4) return p.toString();
var d=3, t='';
while(p%2<1 && p>1){ t+='2*'; p/=2; }
while(p>1){
while(p%d) d+=2;
t += d + '*';
p /= d;
}
return t.slice(0,-1);
}

[beetle]

Welll, I got this work without hanging up on 12-digit numbers and smaller.function prime( num, recur )
{
if ( isNaN( num ) ) return NaN;
if ( !recur ) prime.sol = "";
for ( var i = 2, h = num / 2; i < h; i += 2 )
{
if ( i == 4 ) i--;
if ( num % i == 0 )
{
prime.sol += i + "*";
return prime( num / i, 1 )
}
}
return( prime.sol + num );
}

[ca_redwards]

Using the attached test page, I found that Algorithm delivers results in 188 ms.

Originally posted by Algorithm
Short and sweet.function prime(p){
if(typeof(p)!='number' || isNaN(p)) return 'NaN';
p = Math.round(p);
if(p<4) return p.toString();
var d=3, t='';
while(p%2<1 && p>1){ t+='2*'; p/=2; }
while(p>1){
while(p%d) d+=2;
t += d + '*';
p /= d;
}
return t.slice(0,-1);
}

[ca_redwards]

And I found that beetle delivers results in 140 ms.
Originally posted by beetle
Welll, I got this work without hanging up on 12-digit numbers and smaller.function prime( num, recur )
{
if ( isNaN( num ) ) return NaN;
if ( !recur ) prime.sol = "";
for ( var i = 2, h = num / 2; i < h; i += 2 )
{
if ( i == 4 ) i--;
if ( num % i == 0 )
{
prime.sol += i + "*";
return prime( num / i, 1 )
}
}
return( prime.sol + num );
}

My solution returns results in 93 ms! ;)

[beetle]

Uh oh! :eek:

Battle of the milliseconds!

:D

[whammy]

What's a prime number? ;)

[Algorithm]

I don't expect to be graded on this submission, as I've already entered, and it also borrows an idea from beetle's script. Nevertheless, it performs exponentially better than either of our previous entries, so I felt I would be remiss in not posting it. :)function prime(p){
if(typeof(p)!='number' || isNaN(p)) return 'NaN';
p = Math.round(p);
var d=3, t='', h;
while(p%2<1 && p>1){ t+='2*'; p/=2; }
while(p>1){
h = p/d;
while(p%d && d<=h) d+=2;
if(d>h) return t+p;
t += d + '*';
p /= d;
}
return t.slice(0,-1) || ''+p;
}

[ca_redwards]

My test page registered only 16 ms for your "amended" solution! Wow! Mine is still pretty quick at 78 ms... But, could you annotate it for us? How does it work... ?

Originally posted by Algorithm
I don't expect to be graded on this submission, as I've already entered, and it also borrows an idea from beetle's script. Nevertheless, it performs exponentially better than either of our previous entries, so I felt I would be remiss in not posting it. :)function prime(p){
if(typeof(p)!='number' || isNaN(p)) return 'NaN';
p = Math.round(p);
var d=3, t='', h;
while(p%2<1 && p>1){ t+='2*'; p/=2; }
while(p>1){
h = p/d;
while(p%d && d<=h) d+=2;
if(d>h) return t+p;
t += d + '*';
p /= d;
}
return t.slice(0,-1) || ''+p;
}

[whammy]

16 ms? You've got to be kidding me. It looks like Algorithm is living up to his moniker. :D

[ca_redwards]

Attached to my first "timings" message, you'll find the cross-browser test page I have been using to do these benchmarks.

Originally posted by whammy
16 ms? You've got to be kidding me. It looks like Algorithm is living up to his moniker. :D

Download it, strip off the .txt extension and display it in your browser. Paste the entry to be tested into the upper textarea. Then press the prime(..) button! The results of the test cases are displayed in the status line, and an alert shows the number of milliseconds required to do the job! :thumbsup:

[Algorithm]

My test page registered only 16 ms for your "amended" solution! Wow! Mine is still pretty quick at 78 ms... But, could you annotate it for us? How does it work... ?It's actually fairly simple. Starting with 2, divide the number until it can no longer be divided, and then proceed to the next odd number, until the square root of the number is reached. Whatever is left is indivisible and hence prime.

I also created a version that employs the literal square root of the number instead of relying on my current function's estimate, but I didn't notice any difference in performance. If someone with a slower processor than mine would like to compare the two, replace the lineh = p/d;withh = Math.sqrt(p);I'd like to know how the two measure up. :)

[ca_redwards]

I realize that tightening the control loops in this thing is critical. Thus, I simplified my looping conditions and found that my code now runs a tiny bit faster than yours! (15 ms) :D

[joeframbach]

algorithm: i had 20ms for p/d and 10ms for sqrt(p)

[beetle]

Glad I contributed something to this speedemon :D

[Algorithm]

Originally posted by joeframbach
algorithm: i had 20ms for p/d and 10ms for sqrt(p) Thanks, joe. I've been able to confirm that result by testing on extremely large primes (such as 4449114037). The version of my script that employs Math.sqrt is the only one that works without timing out.

[ca_redwards]

Actually, in my solution, I found that it made absolutely no difference whether I compute a Math.sqrt() ahead of time, or simply square the trial factor at each iteration.

Personally, I prefer to square the trial factor rather than square root the target number. Most numbers don't require too many trial factors before they fall apart, so I really don't calculate too many products. In these cases, I believe that it is much cheaper to do a few products than to do a Math.sqrt()!

Originally posted by Algorithm
Thanks, joe. I've been able to confirm that result by testing on extremely large primes (such as 4449114037). The version of my script that employs Math.sqrt is the only one that works without timing out.

And unless someone promptly informs me that they are working on another entry, I may conclude this contest early. Currently, only Algorithm is privy to my solution, and has even offered some clever refinements, but I'd really hate to win my own contest... :p

[ca_redwards]

Unless someone promptly informs me that they are working on another entry, I will conclude this contest tomorrow (Feb 12, 2003).

[ca_redwards]

function prime(p)
{if(!prime[p]) // unknown prime factorization?
{var f=2; // start with trial factor 2.
if(p%2)for(f=3;(p%f)&&(f*f<=p);f+=2); // odd number? try odd factors up to root..
if(f*f>p){prime[p]=p} // reasonable factors exhausted? number is prime.
else{prime[p]=f+'*'+prime(p/f)} // use this factor, recurse for more!
};
return prime[p] // return known factorization
}


This solution uses a few interesting techniques:

Early on, I got the idea that factoring large numbers could be assisted by utilizating relevant factorings from earlier successful calculations. Thus, every factoring result is saved as an enumerated property within the prime function itself (after all, functions, like any other JavaScript object, can be extended with new custom properties!).

Also, I knew that once a factor had been identified, factoring the leftovers would be exactly the same process. Thus, when a factor is found, this solution becomes recursive: prime(p/f) is needed to return prime(p). I love recursion, I just love it!

Algorithm and I recognized (independently!) that trying any factor bigger than the number's root makes no sense-- If the number won't factor by anything up to its root, that's because it's prime. What we didn't agree on was exactly how to construct an efficient loop up to that root. Algorithm suggested evaluating Math.sqrt (prior to the loop, and comparing the incremented factor against its saved value) while I maintained that repeatedly squaring the incremented factor would be more efficient (modern CPUs have a single instruction for multiplication, but may not for calculating roots). And since neither of us knows how Math.sqrt is implemented internally, we may never know which is better.

But Algorithm made a very significant contribution to this "final solution"-- namely, try only odd factors when factoring an odd number! This cuts the runtime in half (literally!). In my earlier solution, I blithely incremented my trial factor one at a time, shamelessly wasting every even factor (larger than 2)!

Qualified entrants were Algorithm and beetle (I think it only appropriate to disqualify myself, since I am judging this contest!).

And the winner is... beetle! His entry outperformed Algorithm's original entry.

Certainly, an honorable mention is due Algorithm for his post-entry submissions (both his own, and his collaborative work with me).

Hurray!

BTW: Where is Borgtex?

[ca_redwards]

Based upon the code in the previous post, here is a bookmarklet you can use to prime factor numbers....

[ca_redwards]

function prime(p){
if(!prime[p]){
var f=2;
if(p%2)
for(f=3;(p%f)&&(f*f<=p);f+=2);
if(f*f>p){
prime[p]=p
}else{
prime[p]=(prime[f]=f)+'*'+prime(p/f)
}
}
return prime[p]
}

The assignment in red significantly speeds up this function when reused.

[liorean]

Two years later...

[Shen]

You guys are all crazy. Maybe that's why I like this site...

BTW......5ms --- too late for the contest, I know. Just saw ca's post today.