Very Simple Programming Challenge

This is the place for ALL of the user submitted challenges. If you create a little challenge/mission/riddle/whatever, post it here.
Forum rules
Do not post missions that you did NOT create without proper citing.

C version threaded, with precalc.

Post by boriz666 on Sun Jun 07, 2015 7:26 am
([msg=88383]see C version threaded, with precalc.[/msg])

Greetings,
another solution to the problem in c, this time it is also threaded, which shaves a bit
off the execution time, but what really boosts the efficiency is only calculating the
x^y one time, so if you got say a range of numbers from 10000000-99999999 we only calculate
the 0^8,1^8,2^8 .. 9^8 one time and saves the result in our pre-calculate buffer for lookup on the
next calculation.

Some timing:

my first attempt, none threading : avg 5.812 sec run time
second attempt, no threading + lookup : avg 1.694 sec run time
third attempt, threading NO lookup : avg 1.162 sec run time
fourth attempt, threaded + calc 1 time only : avg. 0.470 sec run time [8 threads]
fifth attempt, threaded + x^y lookup tbl. : avg. 0.260 sec run time [8 threads]

As you can see, from this you get a huge gain by just modifying the code to not
calculate the x^y more than one time.

Even by threading a bad implementation you do get some preformance boost,
around half a second, not that bad.

But threading the better implementation works magic in the overall picture and ends
on an average execution time of 0.470 seconds.

EDIT:

From talking with folks on irc, I came to the idea to use a lookup table for the x^y
calculations, and have run the program with the lookup code in place of the actual
pow(x,y) to save cpu time, the avg execution got down to:
avg 250ms with 8 threads.


Code: Select all

int preCalc[10][10] = {
                        {1,1,1,1,1,1,1,1,1,1},
                        {0,1,2,3,4,5,6,7,8,9},
                        {0,1,4,9,16,25,36,49,64,81},
                        {0,1,8,27,64,125,216,343,512,729},
                        {0,1,16,81,256,625,1296,2401,4096,6561},
                        {0,1,32,243,1024,3125,7776,16807,32768,59049},
                        {0,1,64,729,4096,15625,46656,117649,262144,531441},
                        {0,1,128,2187,16384,78125,279936,823543,2097152,4782969},
                        {0,1,256,6561,65536,390625,1679616,5764801,16777216,43046721},
                        {0,1,512,19683,262144,1953125,10077696,40353607,134217728,387420489}
                      };






Code with pre-calculations, 8 threads

Code: Select all
// compile with: gcc -lm -lpthread -o powernumbrs-threaded powernumbrs-threaded.c
#include <pthread.h>
#include <stdio.h>
#include <string.h>
#include <math.h>

#define NUM_THREADS     8

struct thread_data{
   int  from;
   int  to;
   char *message;
};

int preCalc[10][10];

struct thread_data thread_data_array[NUM_THREADS];

int isPowerNumber(int pn);
void *threadFunc(void *arg);

int pnMax = 25;
int stepSize = 1000;

pthread_mutex_t mutexNext;
int nextAvailable = 0;

pthread_mutex_t mutexcnt;
int cnt = 0; // how many power numbers did we find!

int numbers[26];

void *threadFunc(void *arg)
{

        struct thread_data *data;
        data = (struct thread_data *) arg;

        int moreWork = 1;


   while (moreWork) {
        int from = data->from;
        int to = data->to;

        int j;

        for (j=from;j<to;j++) {

         if ( isPowerNumber(j) ) {
           pthread_mutex_lock (&mutexcnt);
           cnt++;
           numbers[cnt] = j;
           pthread_mutex_unlock (&mutexcnt);
           printf("%d is a power number\n",j);
         }
        }

        pthread_mutex_lock (&mutexcnt);
        if ( cnt == pnMax) moreWork = 0;
        else {
         pthread_mutex_lock (&mutexNext);
          data->from = nextAvailable;
          nextAvailable += stepSize;
          data->to = nextAvailable;
         pthread_mutex_unlock (&mutexNext);

        }
        pthread_mutex_unlock (&mutexcnt);

    }
        return NULL;
}

int isPowerNumber(int pn) {

  char str[15];
  sprintf(str,"%d\0",pn);
  int nrLength = strlen(str);

  char* pt = str;
  int i;
  int total = 0;

  for ( i=0;i<sizeof(str);i++) {
    if ( pt[i] == '\0') {
      if (total == pn) return 1;
      return 0;
      break;
    }

    int nr = str[i] - '0';

    if ( preCalc[nrLength][nr] ) {
     total += preCalc[nrLength][nr];
    }
    else {
     int preCalcPow = pow(nr,nrLength);
     preCalc[nrLength][nr] =  preCalcPow;
     total += preCalcPow;
    }

  }
}

int main(void)
{

        pthread_mutex_init(&mutexcnt, NULL);
        pthread_mutex_init(&mutexNext, NULL);

        pthread_t threadList[NUM_THREADS];
        int err;

        int i = 0;
        int from = 0;

        for ( i=0; i<NUM_THREADS;i++) {

          thread_data_array[i].from = from;
          thread_data_array[i].to = from;

          err = pthread_create(&(threadList[i]),NULL,threadFunc,(void *) &thread_data_array[i]);
          if (err != 0)
            printf("\nError creating thread :[%s]", strerror(err));

          from += stepSize;

        }

        for (i=0; i<NUM_THREADS;i++) {
           pthread_join(threadList[i],NULL);
        }

        pthread_mutex_destroy(&mutexcnt);
        pthread_mutex_destroy(&mutexNext);

        pthread_exit(NULL);
        return 0;
}




boriz666
Experienced User
Experienced User
 
Posts: 99
Joined: Tue Mar 24, 2015 11:53 am
Blog: View Blog (0)


Re: Very Simple Programming Challenge

Post by Iblist on Fri Jun 12, 2015 8:25 pm
([msg=88511]see Re: Very Simple Programming Challenge[/msg])

Here's my solution written in Python.

Code: Select all
count = 0
number = 0

while count < 26:
    #Empty storage
    storage = 0

    #Turns numbers into strings#
    numString = str(number)
   
    #Finds length of numString#   
    length = len(numString)

    for i in range(0, length):
        storage = storage + pow(int(numString[i]), length)

    if storage == number:
        print(storage)
        count = count+1

    number = number+1


Takes a little while to find all the numbers, but it gets there eventually. Thanks for the challenge, it was a fun little distraction! :geek:
Those who create and rely upon brilliant and complex creations are often destroyed by some idiot plugging an infected usb stick somewhere they shouldn't have.
User avatar
Iblist
Experienced User
Experienced User
 
Posts: 68
Joined: Fri Jul 11, 2014 12:05 pm
Blog: View Blog (0)


Re: Very Simple Programming Challenge

Post by tremor77 on Sat Jun 13, 2015 10:08 pm
([msg=88524]see Re: Very Simple Programming Challenge[/msg])

@boriz666: wow nice work.. I'm tempted to try porting some of your solution to my javascript solution to see if I can get lower computation times.. I'm actually extrememly impressed at how quickly the javascript worked, I ran it on an i7 and with 8 threads and managed to get around 1.6 something secs.
User avatar
tremor77
Addict
Addict
 
Posts: 1098
Joined: Wed Mar 31, 2010 12:00 pm
Location: New York
Blog: View Blog (0)


Re: Very Simple Programming Challenge

Post by boriz666 on Mon Jun 15, 2015 6:01 am
([msg=88533]see Re: Very Simple Programming Challenge[/msg])

@tremor77,
your javascript example actually made me think "can't this be done faster in c",
after my miserable first attempt of 5-6 seconds!

So after seeing your great example i decided to make it threaded and to do some
other optimizations.

Keep up the good work!
boriz666
Experienced User
Experienced User
 
Posts: 99
Joined: Tue Mar 24, 2015 11:53 am
Blog: View Blog (0)


Previous

Return to User Submitted

Who is online

Users browsing this forum: No registered users and 0 guests

cron