Testing for divisibility of numbers - follow-up

Question

(Here is the follow up question)

---

I had another go at trying to speed up my program described in my previous question.

JS1's answer was particulary helpful and now my code is only about 20% slower than the fastest program in the programming challange (it runs in 0,13 s and my code runs in 0,16 s). I ran the code with different tools to check how often each line was run, etc.

#include <stdio.h>
#define MAX 1000000

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

  scanf("%d", &N);
  for(i=0;i<N;i++) scanf("%d", &n[i]);
  i = MAX+1;
  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;
  }
  for(i=1;i<MAX;i++) if(mask[i]==(1<<N)-1) break;
  fprintf(stdout, "%d\n", i);
}

Again I ran the code through gcov and here is some extensive information about my program.

        -:    0:Source:talfamiljer.c
        -:    0:Graph:talfamiljer.gcno
        -:    0:Data:talfamiljer.gcda
        -:    0:Runs:1
        -:    0:Programs:1
        -:    1:#include <stdio.h>
        -:    2:#define MAX 1000000
        -:    3:
        1:    4:int main() {
        -:    5:  int N,n[100];
        1:    6:  int p[10] = {0};
        1:    7:  int mask[MAX] = {0};
        -:    8:  register int i, j, k;
        -:    9:
        1:   10:  scanf("%d", &N);
        1:   11:  for(i=0;i<N;i++) scanf("%d", &n[i]);
        -:   12:  i = MAX+1;
  1000001:   13:  while(--i) {
        -:   14:    int maskBits = 0;
  7000000:   15:    for(j=0;j<N;j++) {if(i%n[j]==0)maskBits |= (1 << j);}
  1000000:   16:    if (maskBits == 0)
   941611:   17:        continue;
        -:   18:    k=i;
   343849:   19:    while (k>0) {p[k%10]++; k/=10;}
        -:   20:
   116542:   21:    for(j=1;j<10;j++) if(p[j]>0) {k=j; p[j]--; break;}
   285460:   22:    for(j=0;j<10;j++) while (p[j]>0) {k=10*k+j; p[j]--;}
    58389:   23:    mask[k] |= maskBits;
        -:   24:  }
   102246:   25:  for(i=1;i<MAX;i++) if(mask[i]==(1<<N)-1) break;
        1:   26:  fprintf(stdout, "%d\n", i);
        -:   27:}

Something that caught my eye is that the first while loop runs 1000001. However, it should only have to run until it finds the smallest number whose permutations or itself is divisble my all the numbers in the input file.

7
164 278 293 382 483 598 23

I'd be very happy if you can help me beat the fastest program.

Answer 1

Precomputed table

I was able to get a much faster result by doing the following:

1. I precomputed a table which listed for each number, all the permutations of that number. Only the lowest valid number contained its permutations. For example, the number 102 contained the permutations: 102 120 201 210. The entries for 120, 201, and 210 were empty.

2. I iterated through each number from 1 to MAX. For each number, I checked whether each divisor divided into at least one of the permutations of the number. If all divisors divided at least once, then the program was done and the lowest number was found.

When I say I precomputed a table, I mean that I wrote a separate program to dump a table of 1000000 ints into a C file. I then modified that C file and turned the table into an array of 1000000 ints (a large file > 10MB, but only using about 4 MB at run time), and compiled that huge array into my program. So I had something that looked like this:

int bigArray[] = {
    -1, -2, -3, -4, ..., -12, 21, -13, 31, ...,
    -102, 120, 201, 210, -103, ..., -999999, -1000000
};

I used negative numbers to denote the start of a new permutation and positive numbers to denote permutations of the entry. Thus, the -12 and 21 above mean that 12 is the start of a new permutation and 21 is one of the permutations for it.

I have the code to generate the table and the code to use the table, but rather than post them here, I will leave it to the OP to use this idea and create their own code.

The precomputed table version seemed to be about 2x as fast as the previous version, but since the times were so small (0.03 vs 0.06 seconds), it's hard to say whether that measurement was really accurate.