lurk101
Posts: 1073
Joined: Mon Jan 27, 2020 2:35 pm
Location: Cumming, GA (US)

Double base palindromes

Tue Sep 14, 2021 3:35 am

Here's a simple problem (Project Euler problem #36) solved on Pico in C++. It would be interesting to compare the performance of C, MicroPython, or BBCBASIC solutions

Code: Select all

// double-base-palindromes.cpp

// 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 <algorithm>
#include <iostream>
#include <string>

#include <pico/stdlib.h>

using namespace std;

static bool palindrome(string p) {
    string p2(p);
    reverse(p2.begin(), p2.end());
    return p == p2;
}

int main() {
    stdio_init_all();
    getchar_timeout_us(1000); // swallow the spurious EOF character???
    cout << "\033[H\033[J" << flush; // try to clear the screen
    
    unsigned int t = time_us_32();
    unsigned int sum = 0;
    for (int p = 1; p <= 1000000; p++) {
        char cbase[32];
        itoa(p, cbase, 10);
        if (palindrome(cbase)) {
            itoa(p, cbase, 2);
            if (palindrome(cbase))
                sum += p;
        }
    }
    cout << "Sum is " << sum << endl;
    cout << "Run time is " << (time_us_32() - t) / 1000000.0 << " seconds" << endl;
}

Code: Select all

Sum is 872187
Run time is 5.84647 seconds
Last edited by lurk101 on Tue Sep 14, 2021 4:56 am, edited 2 times in total.

lurk101
Posts: 1073
Joined: Mon Jan 27, 2020 2:35 pm
Location: Cumming, GA (US)

Re: Double base palindromes

Tue Sep 14, 2021 4:14 am

In C

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);
    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;
    for (int p = 1; p <= 1000000; p++) {
        char cbase[32];
        itoa(p, cbase, 10);
        if (palindrome(cbase)) {
            itoa(p, cbase, 2);
            if (palindrome(cbase))
                sum += p;
        }
    }
    printf("Sum is %u\n", sum);
    printf("Run time is %f seconds\n", (time_us_32() - t) / 1000000.0);
}

Code: Select all

Sum is 872187
Run time is 3.456046 seconds
Last edited by lurk101 on Tue Sep 14, 2021 4:38 am, edited 1 time in total.

lurk101
Posts: 1073
Joined: Mon Jan 27, 2020 2:35 pm
Location: Cumming, GA (US)

Re: Double base palindromes

Tue Sep 14, 2021 4:38 am

Finally, C multi core

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/multicore.h"
#include <pico/stdlib.h>

static int palindrome(char* p) {
    int i, l = strlen(p);
    for (i = 0; i < l / 2; i++)
        if (p[i] != p[l - i - 1])
            return 0;
    return 1;
}

static unsigned int search(int start) {
    unsigned int sum = 0;
    for (int p = start; p <= 1000000; p += 2) {
        char cbase[32];
        itoa(p, cbase, 10);
        if (palindrome(cbase)) {
            itoa(p, cbase, 2);
            if (palindrome(cbase))
                sum += p;
        }
    }
    return sum;
}

static void core1_entry(void) {
    multicore_fifo_push_blocking(search(2));
    for (;;)
        __wfi();
}

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();
    multicore_launch_core1(core1_entry);

    printf("Sum is %u\n", search(1) + multicore_fifo_pop_blocking());
    printf("Run time is %f seconds\n", (time_us_32() - t) / 1e6);
}

Code: Select all

Sum is 872187
Run time is 1.958642 seconds

pidd
Posts: 2802
Joined: Fri May 29, 2020 8:29 pm
Location: Wirral, UK
Contact: Website

Re: Double base palindromes

Tue Sep 14, 2021 5:27 am

I suspect it would considerably faster if you generate all the decimal palindromic integers with loops and test only for base2 palindromacy? There are only 1998 decimal palidromic integers less than 1 million if my sums are right.

9 of length 1
9 of length 2
90 of length 3
90 of length 4
900 of length 5
900 of length 6

Or is your objective just to compare the different languages with the same underlying algorithm

lurk101
Posts: 1073
Joined: Mon Jan 27, 2020 2:35 pm
Location: Cumming, GA (US)

Re: Double base palindromes

Tue Sep 14, 2021 6:01 am

pidd wrote:
Tue Sep 14, 2021 5:27 am
I suspect it would considerably faster if you generate all the decimal palindromic integers with loops and test only for base2 palindromacy?
That's exactly what it does.
Or is your objective just to compare the different languages with the same underlying algorithm
Base 10 numbers are shorter than their base 2 equivalent, so those are tested first. A much longer base 2 number is only created and checked when the base 10 number passes.

My interests are twofold. First it's always surprising how problems are tacked differently based on language, and second how interpreted languages compare speed wise.
Last edited by lurk101 on Tue Sep 14, 2021 6:13 am, edited 1 time in total.

pidd
Posts: 2802
Joined: Fri May 29, 2020 8:29 pm
Location: Wirral, UK
Contact: Website

Re: Double base palindromes

Tue Sep 14, 2021 6:13 am

lurk101 wrote:
Tue Sep 14, 2021 6:01 am
pidd wrote:
Tue Sep 14, 2021 5:27 am
I suspect it would considerably faster if you generate all the decimal palindromic integers with loops and test only for base2 palindromacy? There are only 1998 decimal palidromic integers less than 1 million if my sums are right.

9 of length 1
9 of length 2
90 of length 3
90 of length 4
900 of length 5
900 of length 6

Or is your objective just to compare the different languages with the same underlying algorithm
Base 10 numbers are shorter than their base 2 equivalent, so those are tested first. A much longer base 2 number is only created and checked when the base 10 number passes.

Yes, but you are performing 999999 decimal tests plus 1998 binary tests.

If you generate the decimal palindromes you have no decimal tests and only 1998 binary tests. I suspect the overhead for generation is considerably less than the palindrome test.

I will have a play tomorrow night if I get a chance - it will be ugly but I suspect it will be very fast.

EDIT: or more precisely, generating 1998 palindromes has considerably less overhead than testing 999999 integers for palindromacy.
Last edited by pidd on Tue Sep 14, 2021 6:16 am, edited 1 time in total.

lurk101
Posts: 1073
Joined: Mon Jan 27, 2020 2:35 pm
Location: Cumming, GA (US)

Re: Double base palindromes

Tue Sep 14, 2021 6:16 am

pidd wrote:
Tue Sep 14, 2021 6:13 am
Yes, but you are performing 999999 decimal tests plus 1998 binary tests.

If you generate the decimal palindromes you have no decimal tests and only 1998 binary tests. I suspect the overhead for generation is considerably less than the palindrome test.
I see... How about

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);
    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;
        for (int j = 0; j < 10; j++) {
            int j2 = j * 100 + i * 10 + j; // nXn
            if (j && palindrome(itoa(j2, b2, 2)))
                sum += j2;
            for (int k = 0; k < 10; k++) {
                int k2 = k * 10000 + j2 * 10 + k; // nXXXn
                if (k && palindrome(itoa(k2, b2, 2)))
                    sum += k2;
            }
        }
    }
    for (int i = 0; i < 100; i += 11) {
        if (palindrome(itoa(i, b2, 2)))
            sum += i;
        for (int j = 0; j < 10; j++) {
            int j2 = j * 1000 + i * 10 + j; // nXXn
            if (j && palindrome(itoa(j2, b2, 2)))
                sum += j2;
            for (int k = 0; k < 10; k++) {
                int k2 = k * 100000 + j2 * 10 + k; // nXXXXn
                if (k && palindrome(itoa(k2, b2, 2)))
                    sum += k2;
            }
        }
    }
    printf("Sum is %u\n", sum);
    printf("Run time is %f seconds\n", (time_us_32() - t) / 1e6);
}

Code: Select all

Sum is 872187
Run time is 0.015281 seconds

User avatar
davidcoton
Posts: 6586
Joined: Mon Sep 01, 2014 2:37 pm
Location: Cambridge, UK

Re: Double base palindromes

Tue Sep 14, 2021 9:44 am

lurk101 wrote:
Tue Sep 14, 2021 6:16 am
pidd wrote:
Tue Sep 14, 2021 6:13 am
If you generate the decimal palindromes you have no decimal tests and only 1998 binary tests. I suspect the overhead for generation is considerably less than the palindrome test.
I see... How about
...

Code: Select all

Sum is 872187
Run time is 0.015281 seconds
QED. Fantastic optimisation by changing algorithm, how much more performance can be squeezed out, either by algorithm or code optimisation?
Location: 345th cell on the right of the 210th row of L2 cache

ejolson
Posts: 8639
Joined: Tue Mar 18, 2014 11:47 am

Re: Double base palindromes

Tue Sep 14, 2021 9:50 am

lurk101 wrote:
Tue Sep 14, 2021 6:16 am
pidd wrote:
Tue Sep 14, 2021 6:13 am
Yes, but you are performing 999999 decimal tests plus 1998 binary tests.

If you generate the decimal palindromes you have no decimal tests and only 1998 binary tests. I suspect the overhead for generation is considerably less than the palindrome test.
I see... How about

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);
    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;
        for (int j = 0; j < 10; j++) {
            int j2 = j * 100 + i * 10 + j; // nXn
            if (j && palindrome(itoa(j2, b2, 2)))
                sum += j2;
            for (int k = 0; k < 10; k++) {
                int k2 = k * 10000 + j2 * 10 + k; // nXXXn
                if (k && palindrome(itoa(k2, b2, 2)))
                    sum += k2;
            }
        }
    }
    for (int i = 0; i < 100; i += 11) {
        if (palindrome(itoa(i, b2, 2)))
            sum += i;
        for (int j = 0; j < 10; j++) {
            int j2 = j * 1000 + i * 10 + j; // nXXn
            if (j && palindrome(itoa(j2, b2, 2)))
                sum += j2;
            for (int k = 0; k < 10; k++) {
                int k2 = k * 100000 + j2 * 10 + k; // nXXXXn
                if (k && palindrome(itoa(k2, b2, 2)))
                    sum += k2;
            }
        }
    }
    printf("Sum is %u\n", sum);
    printf("Run time is %f seconds\n", (time_us_32() - t) / 1e6);
}

Code: Select all

Sum is 872187
Run time is 0.015281 seconds
Are there any triple base palindromes?

For example is there an n other than 0 or 1 which is a palindrome base 2, 3 and 5? What's the smallest such number?

What about numbers simultaneously that are palindromes base 2, 3, 5 and 7?

What about base 2, 4, 8 and 16?

Is there a set of bases such that there is no n which is simultaneously a multidigit palindrome in each of the bases?

hippy
Posts: 10967
Joined: Fri Sep 09, 2011 10:34 pm
Location: UK

Re: Double base palindromes

Tue Sep 14, 2021 11:06 am

Python allows a string to be reversed by using 's[::-1]' and that gives an elegant algorithm with a run time of 5.8 seconds on a Pi 3B (non-plus) -

Code: Select all

def Dec(n) : return str(n)
def Bin(n) : return bin(n)[2:]
def Rev(s) : return s[::-1]

sum = 0
for n in range(1, 1000000):
    if Dec(n) == Rev(Dec(n)):
        if Bin(n) == Rev(Bin(n)):
            sum += n
Unfortunately MicroPython doesn't allow that, so the string has to be reversed a character at a time, 8.5 seconds on the Pi, but 'forever' on a Pico. Time for a rethink - which reduces execution to 5.5 seconds on the Pi.

It still feels like forever on a Pico, though an interpreter being 130 times slower than native perhaps isn't that bad -

Code: Select all

import time

def Palindrome(s):
    for n in range(len(s)):
        if s[n] != s[-(n+1)]:
            return False
    return True

t = time.ticks_ms()

sum = 0
for n in range(1, 1000000):
    if Palindrome(str(n)):
        if Palindrome(bin(n)[2:]):
            sum += n

t = time.ticks_ms() - t
print("Sum is {}".format(sum))
print("Run time is {} seconds".format(t / 1000))

Code: Select all

Sum is 872187
Run time is 758.844 seconds

pidd
Posts: 2802
Joined: Fri May 29, 2020 8:29 pm
Location: Wirral, UK
Contact: Website

Re: Double base palindromes

Tue Sep 14, 2021 11:16 am

lurk101 wrote:
Tue Sep 14, 2021 6:16 am
pidd wrote:
Tue Sep 14, 2021 6:13 am
Yes, but you are performing 999999 decimal tests plus 1998 binary tests.

If you generate the decimal palindromes you have no decimal tests and only 1998 binary tests. I suspect the overhead for generation is considerably less than the palindrome test.
I see... How about

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);
    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;
        for (int j = 0; j < 10; j++) {
            int j2 = j * 100 + i * 10 + j; // nXn
            if (j && palindrome(itoa(j2, b2, 2)))
                sum += j2;
            for (int k = 0; k < 10; k++) {
                int k2 = k * 10000 + j2 * 10 + k; // nXXXn
                if (k && palindrome(itoa(k2, b2, 2)))
                    sum += k2;
            }
        }
    }
    for (int i = 0; i < 100; i += 11) {
        if (palindrome(itoa(i, b2, 2)))
            sum += i;
        for (int j = 0; j < 10; j++) {
            int j2 = j * 1000 + i * 10 + j; // nXXn
            if (j && palindrome(itoa(j2, b2, 2)))
                sum += j2;
            for (int k = 0; k < 10; k++) {
                int k2 = k * 100000 + j2 * 10 + k; // nXXXXn
                if (k && palindrome(itoa(k2, b2, 2)))
                    sum += k2;
            }
        }
    }
    printf("Sum is %u\n", sum);
    printf("Run time is %f seconds\n", (time_us_32() - t) / 1e6);
}

Code: Select all

Sum is 872187
Run time is 0.015281 seconds

Excellent!!!
I've always enjoyed optimising things for speed so you've set a challenge point now.

User avatar
davidcoton
Posts: 6586
Joined: Mon Sep 01, 2014 2:37 pm
Location: Cambridge, UK

Re: Double base palindromes

Tue Sep 14, 2021 1:03 pm

@pidd Would you like to try this? It reduces the number of for loops. I'm a bit nervous suggesting it, because I'm not set up to test on a Pico, so I haven't tried the code which may contain typos or other errors, and my C is very rusty.

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);
    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++) {
                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);
}
Location: 345th cell on the right of the 210th row of L2 cache

lurk101
Posts: 1073
Joined: Mon Jan 27, 2020 2:35 pm
Location: Cumming, GA (US)

Re: Double base palindromes

Tue Sep 14, 2021 1:19 pm

ejolson wrote:
Tue Sep 14, 2021 9:50 am
What about base 2, 4, 8 and 16?
Wouldn't those all yield the same answer? In other words, wouldn't a base 16 palindrome also always be base 2, 4, and 8 palindromes?

User avatar
davidcoton
Posts: 6586
Joined: Mon Sep 01, 2014 2:37 pm
Location: Cambridge, UK

Re: Double base palindromes

Tue Sep 14, 2021 2:05 pm

lurk101 wrote:
Tue Sep 14, 2021 1:19 pm
ejolson wrote:
Tue Sep 14, 2021 9:50 am
What about base 2, 4, 8 and 16?
Wouldn't those all yield the same answer? In other words, wouldn't a base 16 palindrome also always be base 2, 4, and 8 palindromes?
No. 101101 is palindromic, 2D is not.
Conversely, 11011101 is not, DD is.
Location: 345th cell on the right of the 210th row of L2 cache

pidd
Posts: 2802
Joined: Fri May 29, 2020 8:29 pm
Location: Wirral, UK
Contact: Website

Re: Double base palindromes

Tue Sep 14, 2021 3:35 pm

davidcoton wrote:
Tue Sep 14, 2021 1:03 pm
@pidd Would you like to try this? It reduces the number of for loops. I'm a bit nervous suggesting it, because I'm not set up to test on a Pico, so I haven't tried the code which may contain typos or other errors, and my C is very rusty.

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);
    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++) {
                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);
}
I'm not setup with any spare picos at the moment, I keep on meaning to purchase a handful of them. I'll try to release one tonight if I have time.

Likewise, my C is laborious through lack of familiarity and I can never read other peoples C easily compared to my more favoured languages. Its only saving grace is that I find it easier than Python.

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.

To speed things up more it may be possible not to build the full decimal palindrome but just half of it and incorporate that into a pseudo binary palidrome check, there will need to be two checks for odd lengths and even lengths ... not quite got my head round it but there is something like that possible, it may be one step too far for me.

I also suspect you could predict the next binary and next decimal palindrome (ie an equation for the next in series), that would obviate the need for a palindrome check, it would just need comparisons for which one is less (then look for next one of that type) and if they are equal (add it on). I imagine that could be the fastest method if it is indeed feasible.

lurk101
Posts: 1073
Joined: Mon Jan 27, 2020 2:35 pm
Location: Cumming, GA (US)

Re: Double base palindromes

Tue Sep 14, 2021 3:42 pm

davidcoton wrote:
Tue Sep 14, 2021 1:03 pm
@pidd Would you like to try this? It reduces the number of for loops. I'm a bit nervous suggesting it, because I'm not set up to test on a Pico, so I haven't tried the code which may contain typos or other errors, and my C is very rusty.

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);
    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++) {
                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);
}
Yes, that works even better (by 1 microsecond).

Code: Select all

Sum is 872187
Run time is 0.015280 seconds
Multi core version of same

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/multicore.h>
#include <pico/stdlib.h>

static int palindrome(char* p) {
    int i, l = strlen(p);
    for (i = 0; i < l / 2; i++)
        if (p[i] != p[l - i - 1])
            return 0;
    return 1;
}

unsigned int search(int start) {
    char b2[32];
    unsigned int sum = 0;
    for (int i = start; i < 10; i += 2) {
        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++) {
                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;
            }
        }
    }
    return sum;
}

void core1_entry(void) {
    multicore_fifo_push_blocking(search(1));
    for (;;)
        __wfi();
}

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();
    multicore_launch_core1(core1_entry);
    unsigned int sum = search(0) + multicore_fifo_pop_blocking();
    t = time_us_32() - t;
    printf("Sum is %u\n", sum);
    printf("Run time is %f seconds\n", t / 1e6);
}

Code: Select all

Sum is 872187
Run time is 0.008747 seconds

User avatar
davidcoton
Posts: 6586
Joined: Mon Sep 01, 2014 2:37 pm
Location: Cambridge, UK

Re: Double base palindromes

Tue Sep 14, 2021 4:08 pm

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.
Location: 345th cell on the right of the 210th row of L2 cache

User avatar
davidcoton
Posts: 6586
Joined: Mon Sep 01, 2014 2:37 pm
Location: Cambridge, UK

Re: Double base palindromes

Tue Sep 14, 2021 4:17 pm

lurk101 wrote:
Tue Sep 14, 2021 3:42 pm
...
Yes, that works even better (by 1 microsecond).

Code: Select all

Sum is 872187
Run time is 0.015280 seconds
That is ... rather less gain than I expected :? :cry:
Simpler loops replaced by more variable initialisation?

I really must get a new OS installed on my Pi400 and connect it to a Pico.
And learn my way round the multicore stuff -- at 48% it's got impressively close to the theoretical best case 50% time reduction for two cores.
Location: 345th cell on the right of the 210th row of L2 cache

ejolson
Posts: 8639
Joined: Tue Mar 18, 2014 11:47 am

Re: Double base palindromes

Tue Sep 14, 2021 4:26 pm

davidcoton wrote:
Tue Sep 14, 2021 4:17 pm
lurk101 wrote:
Tue Sep 14, 2021 3:42 pm
...
Yes, that works even better (by 1 microsecond).

Code: Select all

Sum is 872187
Run time is 0.015280 seconds
That is ... rather less gain than I expected :? :cry:
Simpler loops replaced by more variable initialisation?

I really must get a new OS installed on my Pi400 and connect it to a Pico.
And learn my way round the multicore stuff -- it's got impressively close to the theoretical 50% time reduction here.
Guess and check falls into that category of embarrassingly parallel algorithms that always scale well. Have no quadruple or triple base palindromes been found?
Last edited by ejolson on Tue Sep 14, 2021 4:27 pm, edited 1 time in total.

lurk101
Posts: 1073
Joined: Mon Jan 27, 2020 2:35 pm
Location: Cumming, GA (US)

Re: Double base palindromes

Tue Sep 14, 2021 4:27 pm

davidcoton wrote:
Tue Sep 14, 2021 4:08 pm
It should be possible to check and reject even numbers, since the leading zero rule means all binary palindromes will be odd.
Ok, but it's faster to check for odd when the number is still in binary form.

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/multicore.h>
#include <pico/stdlib.h>

static int palindrome(char* p) {
    int i, l = strlen(p);
    for (i = 0; i < l / 2; i++)
        if (p[i] != p[l - i - 1])
            return 0;
    return 1;
}

unsigned int search(int start) {
    char b2[32];
    unsigned int sum = 0;
    for (int i = start; i < 10; i += 2) {
        if ((i & 1) && palindrome(itoa(i, b2, 2)))
            sum += i;
        if (((i * 11) & 1) && 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 && (j2 & 1) && palindrome(itoa(j2, b2, 2)))
                sum += j2;
            int j3 = j * 1000 + i * 110 + j; // nXXn
            if (j && (j3 & 1) && palindrome(itoa(j3, b2, 2)))
                sum += j3;
            for (int k = 0; k < 10; k++) {
                int k2 = k * 10000 + j2 * 10 + k; // nXXXn
                if (k && (k2 & 1) && palindrome(itoa(k2, b2, 2)))
                    sum += k2;
                int k3 = k * 100000 + j3 * 10 + k; // nXXXXn
                if (k && (k3 & 1) && palindrome(itoa(k3, b2, 2)))
                    sum += k3;
            }
        }
    }
    return sum;
}

void core1_entry(void) {
    multicore_fifo_push_blocking(search(1));
    for (;;)
        __wfi();
}

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();
    multicore_launch_core1(core1_entry);
    unsigned int sum = search(0) + multicore_fifo_pop_blocking();
    t = time_us_32() - t;
    printf("Sum is %u\n", sum);
    printf("Run time is %f seconds\n", t / 1e6);
}

Code: Select all

Sum is 872187
Run time is 0.005057 seconds

lurk101
Posts: 1073
Joined: Mon Jan 27, 2020 2:35 pm
Location: Cumming, GA (US)

Re: Double base palindromes

Tue Sep 14, 2021 4:31 pm

ejolson wrote:
Tue Sep 14, 2021 4:26 pm
Have no quadruple or triple base palindromes been found?
Perhaps a BBCBASIC program would find them?

lurk101
Posts: 1073
Joined: Mon Jan 27, 2020 2:35 pm
Location: Cumming, GA (US)

Re: Double base palindromes

Tue Sep 14, 2021 4:33 pm

davidcoton wrote:
Tue Sep 14, 2021 4:17 pm
That is ... rather less gain than I expected :? :cry:
No matter! The simpler loop is far more elegant.

ejolson
Posts: 8639
Joined: Tue Mar 18, 2014 11:47 am

Re: Double base palindromes

Tue Sep 14, 2021 4:42 pm

lurk101 wrote:
Tue Sep 14, 2021 4:31 pm
ejolson wrote:
Tue Sep 14, 2021 4:26 pm
Have no quadruple or triple base palindromes been found?
Perhaps a BBCBASIC program would find them?
That's a good idea. Triple and quadruple base palindromes appear a difficult enough problem that a convenient programming language might be required. But what if no such palindromes exist?
Last edited by ejolson on Tue Sep 14, 2021 4:43 pm, edited 1 time in total.

lurk101
Posts: 1073
Joined: Mon Jan 27, 2020 2:35 pm
Location: Cumming, GA (US)

Re: Double base palindromes

Tue Sep 14, 2021 4:42 pm

ejolson wrote:
Tue Sep 14, 2021 4:26 pm
Guess and check falls into that category of embarrassingly parallel algorithms that always scale well. Have no quadruple or triple base palindromes been found?
I would have expected similar run times between the flash version and the no-flash version, since the critical search function should reside in XIP cache. But no, the code and data in RAM version is faster!

Code: Select all

Sum is 872187
Run time is 0.004451 seconds

hippy
Posts: 10967
Joined: Fri Sep 09, 2011 10:34 pm
Location: UK

Re: Double base palindromes

Tue Sep 14, 2021 4:48 pm

pidd wrote:
Tue Sep 14, 2021 6:13 am
If you generate the decimal palindromes you have no decimal tests and only 1998 binary tests. I suspect the overhead for generation is considerably less than the palindrome test.
Generating known and potentially palindromic numbers and only checking those is certainly quicker in MicroPython, slashing a 12 minute run time down to about 2 seconds.
lurk101 wrote:
Tue Sep 14, 2021 4:27 pm
it's faster to check for odd when the number is still in binary form.
Applying that halves it again -

Code: Select all

import time

def Palindrome(s):
    for n in range(len(s) >> 1):
        if s[n] != s[-(n+1)]:
            return False
    return True

def Fast(n):
    global sum
    if Palindrome(bin(n)[2:]):
        sum += n
        
def Slow(n):
    global sum
    if Palindrome(str(n)):
        if Palindrome(bin(n)[2:]):
            sum += n

def f(n, div, mpy):
    return ((n // div) % 10) * mpy

t = time.ticks_ms()
sum = 0

for n in range(1, 10, 2):
    Fast(n)                                                       # a
    Fast(n + f(n, 1, 10))                                         # aa
    Fast(n + f(n, 1, 100))                                        # a0a
    Fast(n + f(n, 1, 1000))                                       # a00a
    Fast(n + f(n, 1, 10000))                                      # a000a
    Fast(n + f(n, 1, 100000))                                     # a0000a
for n in range(11, 100, 2):
    Fast(n + f(n, 1, 10000)  + f(n, 10, 1000))                    # ab0ba
    Fast(n + f(n, 1, 100000) + f(n, 10, 10000))                   # ab00ba
for n in range(101, 1000, 2):
    Slow(n)                                                       # cba    - includes aba and aaa
    Slow(n + f(n, 1, 1000))                                       # acba   - includes abba and aaaa
    Fast(n + f(n, 1, 10000)  + f(n, 10, 1000))                    # abcba
    Fast(n + f(n, 1, 100000) + f(n, 10, 10000) + f(n, 100, 1000)) # abccba

t = time.ticks_ms() - t
print("Sum is {}".format(sum))
print("Run time is {} seconds".format(t / 1000))

Code: Select all

Sum is 872187
Run time is 1.192 seconds
If copy and pasting from Thonny actually pasted what was copied; there would be far fewer edits to this post !
Last edited by hippy on Tue Sep 14, 2021 5:29 pm, edited 6 times in total.

Return to “General”