I am writing a program in MIPS assembly language to find all amicable number pai

Question

I am writing a program in MIPS assembly language to find all amicable number pairs between a given range. I have started by writing a piece of c-code that can run a range from 0-1million in appx 6 seconds. Using sqrt function lends me slightly faster execution. I have chosen to find the square root in the method i have as it cuts down on divisions needed by many sqrt algorithms. I generally do not use gotos but I wanted to replicate my asm code as closely as possible. This was made easier with gotos. The main problem is that the conversion I made to mips makes it run incrediblely slowly. I know it is running in a simulator and thus, through java, but I believe something is wrong when I leave it running for over 12 hours without a complete solution.

The c code is as follows:

int main()
{

clock_t start = clock();
int chk,n1,n2;
int low;
int high = 100000;

int temp_sum = -1;
for(low = 220 ; low < high; low++)
{

int divisor,sum=1;
int stop;
//stop = (int)sqrt(low);
if(temp_sum == low) continue;
for(divisor = 2; divisor < low; divisor++)
{
if((divisor*divisor > low)) goto cont1;
if(is_factor(low,divisor))
{
sum += divisor;
sum += low/divisor;
}
}
cont1:
chk = sum;
if(chk < low)

{
continue;
}

sum = 1;
//stop = (int) sqrt(chk);
for(divisor = 2; divisor < chk; divisor++)
{

if((divisor * divisor) > chk) goto cont2;
if(is_factor(chk,divisor))
{
sum += divisor;
sum += chk / divisor;
}
}
cont2:
if (sum == low)
{
temp_sum = sum;
if(low == chk)
{
continue;
}
n1 = low;
//if(n1 == n2)
//{
// continue;
//}
n2 = chk;

if( n2 > high) continue;
printf("%d, %d ", n1,n2);
//if(is_amacable(n1,n2)){
//}
}

}
printf("Time elapsed: %f ", ((double)clock() - start) / CLOCKS_PER_SEC);

return 0;
}

The assembly code is as follows with explicit comments on each line. It can be assumed that the functions are properly built to allow nested routine calls with proper stack allocation. All that is being included is the main function. It is confusing as this code I have left run for 12 hours and only reached around 20k in my range

My assembly code (the formatting was terrible in this) lives at:
http://pastie.org/10529882

Explanation / Answer

C code:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>


int main(int argc, char** argv) {
   
      clock_t start = clock();
   
      int timelimit, n1, n2, check;
      int counter1 = 220;
     
      printf("Enter the limit: ");
      if (scanf("%d", &timelimit)!=1 || timelimit<=0)
      {
          printf("Invalid an input.");
          return 0;
      }
      else
      {
          while (counter1 < timelimit)
          {
              int sum1 = 0;
              int div1 = 0;
              counter1++;


              int stop = (int) sqrt(counter1);
              while (div1 <= stop)
              {
                  ++div1;
                  if (counter1 % div1 == 0)
                  sum1 += div1;                   
              }
                  check = sum1;
                  sum1 = div1 = 0;


              while (div1 <= check/2)
              {
                  ++div1;
                  if (check % div1 == 0)
                  sum1 += div1;
              }


              if (sum1 == counter1)
              {
                  if (counter1 == check) continue;
                  n1 = counter1;


                  if (n1 == n2) continue;
                  n2 = check;


                  printf("%d, %d ",n1,n2);


              }
          }
      }
      printf("Time elapsed time: %f ", ((double)clock() - start) / CLOCKS_PER_SEC);
      return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.