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

### 3 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
```
3. matthew said

Here’s some Haskell, first some variants of the pandigital function itself:

```-- pandigital.hs
import Data.List
import Data.Bits

pandigital0 :: Int -> Bool
pandigital0 n = sort (show n) == "0123456789"

-- Use a bitset to track digits
digits1 :: Int -> Int
digits1 0 = 0
digits1 n = setBit (digits1 (div n 10)) (mod n 10)

pandigital1 :: Int -> Bool
pandigital1 n = digits1 n == 1023

-- Bitset with accumulating parameter
digits2 :: Int -> Int -> Int
digits2 s 0 = s
digits2 s n = digits2 (setBit s (mod n 10)) (div n 10)

pandigital2 :: Int -> Bool
pandigital2 n = digits2 0 n == 1023

-- Predeclare the list of candidates as Int list:
s :: [Int]
s = map (^2) [3,6..100000]
```

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:

```\$ ghci -fobject-code -O pandigital.hs
GHCi, version 8.6.5: http://www.haskell.org/ghc/  :? for help
Prelude Main> :set +s
Prelude Main> length s
33333
(0.11 secs, 2,214,536 bytes)
Prelude Main> length \$ filter pandigital0 s
87
(0.03 secs, 57,069,912 bytes)
Prelude Main> length \$ filter pandigital1 s
87
(0.02 secs, 83,248 bytes)
Prelude Main> length \$ filter pandigital2 s
87
(0.02 secs, 83,248 bytes)
```