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.
Programming Praxis 
Make the range count by 3 in stead of checking the square mod 9.
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 9814072356Here’s some Haskell, first some variants of the pandigital function itself:
Now try it out. It’s important for speed to a) ensure the interpreter is actually compiling and optimizing input files, and b) make sure we use Int type declarations appropriately to avoid conversions to and from Integer bignums: