pidd wrote: ↑Tue Sep 14, 2021 3:35 pm

You appear to have done what I was planning next, using three nested loops to build up the different lengths of palindromic integers at the same time but at the different nesting levels for the different lengths (my English is about as good as my C). Only experimentation will find out it its faster as is or whether the amount of arithmetic building the palindrome is punishing.

Yes, I've just folded the two sets of loops into one set (or tried to). It results in a slightly different method of generating NN. There are also some variable name changes to accommodate the two simultaneous sets. For loops are often a slow element, so reducing the number of loops with little increased complexity in return should be faster. I don't think there's much to gain trying to generate decimal palindromes faster, especially since echoing a half-string needs two versions for odd and even full lengths. It would require number to string in base 10, manipulate string, sting (base 10) to number to string (base 2) which seems likely to be slow.

It should be possible to check and reject even numbers, since the leading zero rule means all binary palindromes will be odd. The shorter length even palindrome decimal strings still need to be generated, so they can be wrapped with an odd digit in the second and innermost loop. But the innermost loop need not generate even numbers.

So my next iteration:

Code: Select all

```
// double-base-palindromes.c
// Euler Project Problem 36
// The decimal number, 585 = 1001001001 (binary), is palindromic in both bases.
// Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.
// (Please note that the palindromic number, in either base, may not include leading zeros.)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <pico/stdlib.h>
static int palindrome(char* p) {
int i, l = strlen(p);
if (p[l - 1] == 0) // Even binary numbers are not palindromic
return 0;
for (i = 0; i < l / 2; i++)
if (p[i] != p[l - i - 1])
return 0;
return 1;
}
int main() {
stdio_init_all();
getchar_timeout_us(1000); // swallow the spurious EOF character???
printf("\033[H\033[J"); // try to clear the screen
fflush(stdout);
unsigned int t = time_us_32();
unsigned int sum = 0;
char b2[32];
for (int i = 0; i < 10; i++) {
if (palindrome(itoa(i, b2, 2)))
sum += i;
if(palindrome(itoa(i*11,b2,2)))
sum += (11*i);
for (int j = 0; j < 10; j++) {
int j2 = j * 100 + i * 10 + j; // nXn
if (j && palindrome(itoa(j2, b2, 2)))
sum += j2;
int j3 = j * 1000 + i * 110 + j; // nXXn
if (j && palindrome(itoa(j3, b2, 2)))
sum += j3;
for (int k = 0; k < 10; k+=2) { // odd numbers only at these lengths
int k2 = k * 10000 + j2 * 10 + k; // nXXXn
if (k && palindrome(itoa(k2, b2, 2)))
sum += k2;
int k3 = k * 100000 + j3 * 10 + k; // nXXXXn
if (k && palindrome(itoa(k3, b2, 2)))
sum += k3;
}
}
}
printf("Sum is %u\n", sum);
printf("Run time is %f seconds\n", (time_us_32() - t) / 1e6);
}
```

After that, maybe checking the scope and declaration point of the variables (i, j, j2, j3, k2, k3) will yield further gains -- I can't remember the general optimisation advice in that regard.