Today I was asked by a friend to help with his programming assignment. His program needs to take in a number and output the prime factors of the number. For example, 60 = (2^{2})(3^{1})(5^{1})

So after trying to explain the problem to him, I decided to try writing it myself in C. Of course, he wrote his own version in Java.

123456789101112131415161718192021222324

voidprintPrimeFactors(intnum){intisprime=0,power;inti,z;for(i=2;i<=num;i++){// determine if its a primeisprime=1;for(z=2;z<i;z++){if(i%z==0&&z!=i){isprime=0;}}if(!isprime){continue;}// divide the crap out of itpower=0;while(!(num%i)){num/=i;power++;}if(power>0)printf("(%d^%d)",i,power);}}

After looking at the disassembly for that, I realized how often memory gets accessed, and wondered if I could use the registers. Then, I suddenly transformed into Mr. Geeky and tried to write it in asm using the least amount of memory access possible.

voidprint(intnum,intpower){printf("(%d^%d)",num,power);}voidprintprimefactors(intnum){__asm{movebx,2;// ebx is the current factor startloop:movecx,2;// check if its prime. ecx is the number to divide ebx by. if ebx%ecx is zero and if ecx is not ebx, then go to next factorstartcheckprime:moveax,ebx;// set the highcdq;// set the lowidivecx;// divide ebx by ecx, the remainder is in edxcmpedx,0;// if the remainder is not zero then continuejnecontcheckprime;cmpecx,ebx;// if ecx and ebx are the same then continuejecontcheckprime;jmpcontloop;// aha. factor is not a prime. continuecontcheckprime:addecx,1;cmpecx,ebx;jlstartcheckprime;// if ecx < ebx then nextmovecx,0;moveax,num;movedx,0;divideloop:movnum,eaxcdq;idivebx;cmpedx,0;jneprintout;addecx,1;jmpdivideloop;printout:cmpecx,0;jecontloop;movesi,esp;pushebx;pushecx;callprint;addesp,08h;contloop:addebx,1;cmpebx,num;jlestartloop;}}

Okay, fine theres the memory access in the loop. But it isn’t very tight. Of course, even though its written in ASM, its not going to be much faster than the C version due to the call to printf, which will in fact, make up almost all the time the function spends inside itself. Writing this in ASM is completely pointless. I just did it because I felt the itch to.