2
\$\begingroup\$

(EDIT: here is the follow up qusetion)

Using this program to test for the smallest number where its permutations or itself is divisible by 10 or less numbers is twice as slow as the fastest program I found doing this (I don't have the source code). How can this program be twice as slow, what optimizations can I do without messing with the compiler flags?

#include <stdio.h>
#include <string.h>
#define MAX 1000000

int main() {
  int N,p[10],n[100];
  int mask[MAX];
  register int i, j, k;

  scanf("%d", &N);
  for(i=0;i<N;i++) scanf("%d", &n[i]);
  memset(mask,0,sizeof(mask));
  i = MAX+1;
  while(--i) {
    k=i;
    p[0]=0;
    p[1]=0;
    p[2]=0;
    p[3]=0;
    p[4]=0;
    p[5]=0;
    p[6]=0;
    p[7]=0;
    p[8]=0;
    p[9]=0;
    while (k>0) {p[k%10]++; k/=10;}

    for(j=1;j<10;j++) if(p[j]>0) {k=j; p[j]--; break;}
    for(j=0;j<10;j++) while (p[j]>0) {k=10*k+j; p[j]--;}
    for(j=0;j<N;j++) if(i%n[j]==0) mask[k]|=(1<<j);
  }
  for(i=1;i<MAX;i++) if(mask[i]==(1<<N)-1) break;
  fprintf(stdout, "%d\n", i);
}

This program uses bitmasks to test all numbers between 1 and MAX for divisibility with the given numbers and then prints out the smallest number whose permutations or itself is divisible by all given numbers. It is not fast enough!

Example input

7
164 278 293 382 483 598 23

This will test all numbers and check which ones are divisible by the given numbers and the output should be 102246.

It is compiled using the GCC compiler with the following flags:

-g -O2 -std=gnu99 -static -lm

Test the code here.

\$\endgroup\$
14
  • \$\begingroup\$ the posted code fails to compile. It is missing #include <string.h> Always compile with all warnings enabled. (for gcc, at a minimum use: -Wall -Wextra -pedantic ) then fix those warnings. \$\endgroup\$ Oct 15 '15 at 17:26
  • \$\begingroup\$ why are you including the math library when the 1) code does not need it 2) the code does not have: #include <math.h> \$\endgroup\$ Oct 15 '15 at 17:27
  • \$\begingroup\$ in modern C compilers, the register modifier has only one effect, namely that the address of the associated variable cannot be acquired. \$\endgroup\$ Oct 15 '15 at 17:30
  • \$\begingroup\$ @user3629249 Sorry, but this is for a programming challenge where the compiler flags are fixed. You're right about the missing header file, that was something I forgot to include (I added the memset code on ideone.com). Should be fixed now. \$\endgroup\$
    – Linus
    Oct 15 '15 at 17:31
  • 1
    \$\begingroup\$ this line: scanf("%d", &N); has a couple of problems. 1) always check the returned value from scanf() to assure the operation was successful. 2) the value input into 'N' is not checked to assure it is in the range of 1,,,99. 3) the user of this program will be staring at a blinking cursor and have no indication of what to do next. (I.E. prompt the user and check the results for validity \$\endgroup\$ Oct 15 '15 at 17:34
1
\$\begingroup\$

Check if work is necessary first

I was able to speed up your program 2x by making the following simple change. If i is not divisible by any n[j], you can skip the whole lengthy computation of k and just move on to the next i. In other words, at the top of your loop, add this:

  while(--i) {
    // This is a quick check to see if we even need to compute k.
    for(j=0;j<N;j++) {
        if(i%n[j]==0)
            break;
    }
    // None of the numbers divide into i, so skip this i.
    if (j == N)
        continue;

    // The rest of your loop...
  }

Since your program was only running for 0.7 seconds on my machine, I tested it by increasing MAX by 10x and using inputs that would force the answer to be something really big. By doing that, I found that this change sped up your program by about 2x compared to your original program.

Further optimizations

A small optimization to my previous change is that you can reuse the work that you do during the quick check by saving the bits that you need to set in the mask.

Another thing I noticed was that the p array is always set to 0 at the end of every loop, so you don't have to explicitly zero it yourself at the beginning of the loop. However, this change didn't appear to speed up your program so the compiler probably already optimized that away.

So your loop would now look like this:

  int p[10] = {0};

  while(--i) {
    int maskBits = 0;
    for(j=0;j<N;j++) {
        if(i%n[j]==0)
            maskBits |= (1 << j);
    }
    if (maskBits == 0)
        continue;
    k=i;
    while (k>0) {p[k%10]++; k/=10;}

    for(j=1;j<10;j++) if(p[j]>0) {k=j; p[j]--; break;}
    for(j=0;j<10;j++) while (p[j]>0) {k=10*k+j; p[j]--;}
    mask[k] |= maskBits;
  }

This ran about 5-10% faster than the previous version.

\$\endgroup\$
4
  • \$\begingroup\$ using inputs that would force the answer to be something really big are you sure you avoided overflow errors in doing so? \$\endgroup\$
    – Caridorc
    Oct 15 '15 at 19:22
  • \$\begingroup\$ @Caridorc There are no overflow problems in the program. It's just that if the answer is very big, the program doesn't find it and just prints out 1000000. I used inputs that made the answer bigger than 1000000, but less than 10000000. All of this is well within the bounds of an int. \$\endgroup\$
    – JS1
    Oct 15 '15 at 19:30
  • \$\begingroup\$ @JSI excellent, I was just wondering :) \$\endgroup\$
    – Caridorc
    Oct 15 '15 at 19:49
  • \$\begingroup\$ @JS1 Works very well. It now only took 0.16s to run all tests! However, the fastest program executes in 0.13s... Are there any more optimizations that can be made to beat that? \$\endgroup\$
    – Linus
    Oct 15 '15 at 20:56
1
\$\begingroup\$

for loop

i = MAX+1;
while(--i) {

This should be converted to a for loop, it will become more readable.

Smallest scope possible

Maybe in this challenge C99 is not an option, but I would like to reccomend declaring variables in loop declarations, like:

for(int i=1;i<MAX;i++) 

Avoiding repetition

Please, avoid repetion:

p[0]=0;
p[1]=0;
p[2]=0;
p[3]=0;
p[4]=0;
p[5]=0;
p[6]=0;
p[7]=0;
p[8]=0;
p[9]=0;

Should be:

for (int i = 0; i <= 9; i++) {
    p[i] = 0;
}

and it becomes so much clearer (think what would have happened if you had to set 100 of such items).

\$\endgroup\$
2
  • \$\begingroup\$ All those things except declaring variables in the for loop were made to increase speed not readability. I do agree it looks much cleaner with a for loop rather than the more verbose and repetitive version however speed is the primary focus I have. \$\endgroup\$
    – Linus
    Oct 15 '15 at 18:17
  • \$\begingroup\$ @Linus Remember that only innermost loops should be optimized. \$\endgroup\$
    – Caridorc
    Oct 15 '15 at 18:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.