Pandigital Squares, Faster And Smaller

October 6, 2020

In a previous exercise, we wrote a program to compute pandigital squares, defined as ten-digit numbers with integral square roots in which each digit zero through nine appears exactly once. We remarked at the time that our solution, though not very fast, was fast enough.

Your task is to write a program that finds pandigital squares, reducing the time and space requirements of the naive solution. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

2 Responses to “Pandigital Squares, Faster And Smaller”

  1. Make the range count by 3 in stead of checking the square mod 9.

  2. Daniel said

    Here’s a solution in C.

    Relative to my earlier solution, this reduces the space requirements by using a bit array for determining if a number is pandigital, instead of using an array of integers. This alone slightly increases the time requirements, but is more than offset by another modification that conducts the search in parallel. In aggregate, using 6 threads on my 8-core CPU, runtime decreases by about 41% versus my earlier solution.

    /*
     * search.c
     *
     * Build
     *   $ gcc -O2 -o search -fopenmp search.c
     *
     * Usage
     *   $ [OMP_NUM_THREADS=INT] search
     */
    
    #include <stdbool.h>
    #include <stdint.h>
    #include <stdio.h>
    #include <stdlib.h>
    
    #include <omp.h>
    
    #define MIN_PANDIGITAL 1023456789
    #define MAX_PANDIGITAL 9876543210
    
    static bool is_pandigital(int64_t x) {
      if (x < MIN_PANDIGITAL || x > MAX_PANDIGITAL)
        return false;
      int array = 0;
      for (int i = 0; i < 10; ++i) {
        int r = x % 10;
        if ((array >> r) & 1)
          return false;
        array |= 1 << r;
        x /= 10;
      }
      return true;
    }
    
    int main(void) {
      int start = 31991;  // int(sqrt(MIN_PANDIGITAL))
      int end = 99380;  // int(sqrt(MAX_PANDIGITAL))
      #pragma omp parallel
      {
        int num_threads = omp_get_num_threads();
        int thread_num = omp_get_thread_num();
        for (int x = start + thread_num; x <= end; x += num_threads) {
          int64_t square = (int64_t)x * (int64_t)x;
          if (is_pandigital(square)) {
            #pragma omp critical
            printf("%ld\n", square);
          }
        }
      }
      return EXIT_SUCCESS;
    }
    

    Example Usage:

    $ export OMP_NUM_THREADS=6; time for x in {1..1000}; do ./search > /dev/null; done
    real    0m1.673s
    user    0m3.697s
    sys     0m0.860s
    
    $ ./search
    1026753849
    1042385796
    1248703569
    1098524736
    ...
    9054283716
    9351276804
    9761835204
    9814072356
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: