## 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
*/

#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
{
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
```