Optimize program to test for divisibility of numbers 3.0

Question

This is a follow up on my previous question.

JS1's answer suggested that I should use a precomputed table containing all permutations of the lowest valid number for each number between 1 and MAX. It was well described how to implement the precomputed table but somewhere I seem to have miserably failed since the code runs much slower than my previous versions of the code.

I don't believe there's anything wrong with my lookup table but if that's for any use here is the code I wrote to obtain all permutations for numbers between 1 and MAX.

Something with my code seems off because for larger calculations (the example found in my previous question) the code runs terribly slow.

#include <stdio.h>

int lookup[] = {
#include "table.h"
};

#define LENGTH(x) (sizeof(x) / sizeof((x)[0]))
#define MAX 1000000

int main(void) {
  int n[100];
  int x, i, j, k, l, m, N;

  scanf("%d", &N);
  for(i=0;i<N;i++) scanf("%d", &n[i]);
  for(x=1;x<MAX;x++) {
    j=x-1;
    i=-x;
    while((unsigned int)(j) < LENGTH(lookup) && lookup[j] != i) ++j;
    for(l=0;l<N;l++) {
      m = j;
      while((k = lookup[++m]) > 0) {
        if(k%n[l]==0)break;
      }
      if(k<0) goto outer;
    }
    break;
    outer:
    continue;
  }
  fprintf(stdout, "%d\n", x);
}

Perhaps the access time on the array is affecting the speed?

Answer 1

Table generator

Your table generator has a bug, which caused it to crash on my machine. This line:

  if(*len > buflen) {

should be:

  if(*len >= buflen) {

Second, your table generator is outputting entries for permutations that aren't required. For example, since 12 and 21 are permutations of each other, you only need to output "-12 21", and later on, there shouldn't be a "-21" entry because you've already checked for 21. But currently, your table includes both, so your program will check entries that it doesn't need to check.

Incorrect table searching

There are a couple of things wrong with your program. The biggest problem is that you are starting over at index 1 every time through the loop. You really don't have to do that because to get to the next number, you just need to skip all the negative numbers. In other words:

   for(x=1;x<MAX;x++) {
     j=x-1;
     i=-x;

should be:

    j = 0;
    for(x=1;x<MAX;x++) {
      i=-x;

Just making that change with your current table reduces the program time back down to "normal" levels, although it still isn't correct.

A second problem is that you are skipping lookup[j] when doing the dividing loop. This is because your loop uses a preincrement, most likely because you are trying to avoid the first number of the sequence, which is negative.

  m = j;
  while((k = lookup[++m]) > 0) {

What you can do is change the table's negative entry to positive. Then you can use a postincrement:

lookup[j] = -lookup[j];
for(l=0;l<N;l++) {
  m = j;
  while((k = lookup[m++]) > 0) {
    if(k%n[l]==0)break;
  }
  if(k<0) goto outer;
}

Searching the optimized table

Once you start using a table that doesn't include redundant entries, your search will need to change. Your current search looks for the next number. But since not every number will exist, all you need to do is search for a non-negative number. Also, I appended a -1000000 entry at the end of my table to make sure I didn't run past the end of the table.

Your current search:

 while((unsigned int)(j) < LENGTH(lookup) && lookup[j] != i) ++j;

would turn into:

while (lookup[j] >= 0)
    ++j;

Putting it all together

This is what your code would look like with all the changes. This code assumes that the table you generate has a -1000000 entry at the end and contains no redundant entries:

#include <stdio.h>

int lookup[] = {
#include "table.h"
};

#define MAX 1000000

int main(void) {
  int n[100];
  int i, j, k, m, N;

  scanf("%d", &N);
  for(i=0;i<N;i++) scanf("%d", &n[i]);
  for(i=0;i<MAX;i++) {
    while(lookup[i] >= 0)
        ++i;
    lookup[i] = -lookup[i];
    for(j=0;j<N;j++) {
      m = i;
      while((k = lookup[m++]) > 0) {
        if(k%n[j]==0)break;
      }
      if(k<0) goto outer;
    }
    break;
    outer:
    continue;
  }
  fprintf(stdout, "%d\n", lookup[i]);
}

You can find my own version of the table generator and solver program here on Github.