3
\$\begingroup\$

(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.

\$\endgroup\$
  • \$\begingroup\$ Not sure how the optimizer is handling it but you might better write ++your_var instead of your_var++. And maybe precompute (1<<N) - 1. \$\endgroup\$ – 301_Moved_Permanently Oct 18 '15 at 23:00
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Aha, that seems very promising. I'll see if I can successfully create my own precomputed table :) \$\endgroup\$ – Linus Oct 19 '15 at 6:03
  • \$\begingroup\$ Okay, I have made my first revision of the table generator and the code to use the table, however my header file where I put the precomputed table exceeds 15MB which is way more than what you got. How did you precompute the table (my code works but is slower than my previous version)? \$\endgroup\$ – Linus Oct 19 '15 at 18:08
  • \$\begingroup\$ @Linus My header file was also > 10 MB in size. It had exactly 1000000 entries in it. The 4 MB I talked about was the size of the array in memory at runtime. I edited my answer to clarify that point. \$\endgroup\$ – JS1 Oct 19 '15 at 20:41
  • \$\begingroup\$ Okay, my array had 1991997 integers (including permutations). However my program takes > 3s to calculate the same example as I have in my question. Whereas the previous took only a few splitseconds. Should I ask a new question entitled "Optimize program to test for divisibility of numbers 3.0"? \$\endgroup\$ – Linus Oct 19 '15 at 20:45
  • \$\begingroup\$ @Linus You must have made a mistake because no number should appear more than once in the array. I'll look at your 3.0 question. \$\endgroup\$ – JS1 Oct 20 '15 at 0:48

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.