Thread: Program to Multiply Integers as Fast as Hardware?

What is your equivalent function that uses operator * in its implementation?

sorry I forgot to show my main function which does the testing:

Code:

int main( int argc, char** argv ){
    clock_t begin1, end1, begin2, end2;
    long double total;


    int trials, trials1, i=0, SIZE = 31, MAX = 1000000000;

    unsigned long long m = 2, n = 1;     // numbers to be multiplied

    double avg1, avg2, var=0;
    FILE *fp;


    fp = fopen(argv[1], "w");


    START=clock();

    // multiply a most a 31-bit with a 31-bit
    while( i++ < SIZE )
    {
        trials = 1000000;
        avg1 = avg2 = 0;
        while( trials-- )
        {


            trials1 = MAX;
            begin1 = clock();

            while( trials1-- ) m*n;       // timing m*n

            end1 = clock();
            avg1 += (double)(begin1 - end1);


            trials1 = MAX;
            begin2 = clock();

            while( trials1-- ) mult(m,n);   // timing mult

            end2 = clock();
            avg2 += (double)(begin2 - end2);


        }
        
        avg1 /= CLOCKS_PER_SEC;
        avg2 /= CLOCKS_PER_SEC;
        m = (m<<1) - 1;
        n <<= 1;


        fprintf( fp, "%d %g %g\n", i, avg1 / 1000000, avg2 / 1000000 );
    }
    END=clock();
    fclose(fp);
#endif
}

As you can see, I am timing * directly instead of calling a function. If there is something wrong with my method, then please let me know.

Additionally, I am outputting the data in such a way that I can plot it using gnuplot.

[EDIT] Sorry, I just realised that in the fprintf() im am dividing by trials, which is now not 1000 000. Just fixed that - I still get the same results though..

Well, one issue with these kind of tests is that you may end up with the compiler applying optimisations that you did not intend, e.g., perhaps it would just remove a loop that has no net effect, and if that is the loop whose body contains precisely the thing you are trying to time, you could well just be timing the resulting reduced code instead of what you wanted to time.

Also, I noticed that before you tested for operator *, you wrote:

Code:

trials1 = 1000000000;

whereas before you tested smult, you wrote:

Code:

trials1 = MAX;

MAX is not shown, but if MAX happens to be much smaller than 1000000000, then the reason for the unexpected results could lie there.

Here is my full source code, just so there is no confusion - and by that I mean errors caused by me forgetting to make certain changes when copying the code over.

Code:

#include <stdio.h>
#include <stdlib.h> 
#include <limits.h>
#include <time.h>
 
#define MAX 1000000000
#define NUM_FOR_AVG 1000000
#define SIZE 31


inline unsigned long long int smult( long long m, long long n )
{

    unsigned long long x = m ^ ((m ^ n)& -(m > n)),\
                       y = m ^ ((m ^ n)& -(m<n)),\
                       a=0;
    int i = 0; 


    do a += (y&-(x&1))<<(i++); while(x>>=1); 


    return a;
}


int main( int argc, char** argv )
{
    clock_t begin1, end1, begin2, end2;
    unsigned long long m = 2, n = 1;
    double avg1, avg2;
    int trials, trials1, i=0;


    FILE *fp;
    fp = fopen(argv[1], "w");


    while( i++ < SIZE )
    {
        trials = NUM_FOR_AVG;
        avg1 = avg2 = 0;
        while( trials-- )
        {   


            trials1 = MAX;
            begin1 = clock();
            while( trials1-- ) m*n;
            end1 = clock();
            avg1 += (double)(begin1 - end1);
     
            trials1 = MAX;
            begin2 = clock();
            while( trials1-- ) smult(m,n);
            end2 = clock();
            avg2 += (double)(begin2 - end2);


        }
        avg1 /= CLOCKS_PER_SEC;
        avg2 /= CLOCKS_PER_SEC;
        m = (m<<1) -1; 
        n <<= 1;


        fprintf( fp, "%d %g %g\n", i, avg1/NUM_FOR_AVG, avg2/NUM_FOR_AVG );
        printf("%.2g%%\n", (double)i*100/SIZE);
    }   
    fclose(fp);
}

Now running this code again with the NUM_FOR_AVG constant I seem to be getting more sensible results, such as mult() taking some constant time longer than the * operator

Originally Posted by plopperzz

What you say may very well be true, however I take it I need to look at the assembly in order to make tat conclusion?

That would certainly be one way of checking. I believe that to avoid such optimisations, people typically do things like vary the input and/or ensure the output is used such that it cannot be optimised away, but doing these with something so fundamental as operator * may well cause these things to dominate instead of the operation.

For all you know, just swapping the order in which you test may well result in operator * being faster "in most cases".

Try using the calculated values so the optimizer won't remove the calculations altogether. Something like the following.

Code:

#include <stdio.h>
#include <stdlib.h> 
#include <limits.h>
#include <time.h>
  
#define NUM_TRIALS    1000000
#define NUM_REPS   1000000000
#define SIZE               31
 
inline unsigned long long int smult(long long m, long long n) {
  unsigned long long x = m ^ ((m ^ n) & -(m > n)),
    y = m ^ ((m ^ n) & -(m < n)),
    a = 0;
  int i = 0; 
  do
    a += (y & -(x & 1)) << (i++);
  while (x >>= 1);
  return a;
}

int main(int argc, char** argv) {
  clock_t begin;
  unsigned long long m = 2, n = 1, sum;
  double avg1, avg2;
  int trials, reps, i;
  FILE *fp = fopen(argv[1], "w");
  
  for(i = 0; i < SIZE; i++) {
    avg1 = avg2 = 0;
    sum = 0;
    for(trials = 0; trials < NUM_TRIALS; trials++) {   

      begin = clock();
      for(reps = 0; reps < NUM_REPS; reps++)
        sum += m * n;
      avg1 += begin - clock();

      begin = clock();
      for(reps = 0; reps < NUM_REPS; reps++)
        sum += smult(m, n);
      avg2 += begin - clock();
    }
    
    fprintf(fp, "%lld %d %g %g\n", sum, i,
        avg1 / CLOCKS_PER_SEC / NUM_TRIALS,
        avg2 / CLOCKS_PER_SEC / NUM_TRIALS);
    printf("%.2g%%\n", (double)i * 100 / SIZE);
    
    m = (m << 1) - 1;
    n <<= 1;
  }   
  
  fclose(fp);
  return 0;
}

Depending on how smart the optimizer is, this still might not work.
BTW, how long does this take to run on your computer?