kilograham
Raspberry Pi Engineer & Forum Moderator
Raspberry Pi Engineer & Forum Moderator
Posts: 1029
Joined: Fri Apr 12, 2019 11:00 am
Location: austin tx

Re: Double base palindromes

Wed Sep 22, 2021 9:11 pm

Go (tinygo) is available

User avatar
RichardRussell
Posts: 1112
Joined: Thu Jun 21, 2012 10:48 am

Re: Double base palindromes

Wed Sep 22, 2021 10:03 pm

RichardRussell wrote:
Wed Sep 22, 2021 6:22 pm
The fastest I've managed to achieve is 0.42 seconds
This gets it down to 0.39 seconds in BBC BASIC (yes I know I'm looping more times than I need to but I've still not found a faster solution):

Code: Select all

   10 TIME=0
   20 Ln2=LN2
   30 Sum=0
   40 FOR A%=100001 TO 900009 STEP 200002
   50   FOR B%=0 TO 90090 STEP 10010
   60     FOR X%=A%+B% TO A%+B%+9900 STEP 1100
   70       PROCbc(X%)
   80     NEXT
   90   NEXT
  100 NEXT
  110 FOR A%=10001 TO 90009 STEP 20002
  120   FOR B%=0 TO 9090 STEP 1010
  130     FOR X%=A%+B% TO A%+B%+900 STEP 100
  140       PROCbc(X%)
  150     NEXT
  160   NEXT
  170 NEXT
  180 FOR A%=1001 TO 9009 STEP 2002
  190   FOR B%=0 TO 990 STEP 110
  200     PROCbc(A%+B%)
  210   NEXT
  220 NEXT
  230 FOR A%=101 TO 909 STEP 202
  240   FOR B%=0 TO 90 STEP 10
  250     PROCbc(A%+B%)
  260   NEXT
  270 NEXT
  280 FOR X%=11 TO 99 STEP 22
  290   PROCbc(X%)
  300 NEXT
  310 FOR N%=1 TO 9 STEP 2
  320   Sum += N%
  330 NEXT
  340 PRINT "Sum of all double-base palindromes: "; Sum
  350 PRINT "Calculation time: "; TIME/100; " seconds"
  360 END
  370
  380 DEF PROCbc(N%)
  390 LOCAL P%,Q%
  400 P%=N%:Q%=1<<(LNN%/Ln2)
  410 WHILE P%
  420   IF (P%EORN%DIVQ%)AND1 ENDPROC
  430   P%DIV=2:Q%DIV=2
  440 ENDWHILE
  450 Sum += N%
  460 ENDPROC
I'm concerned about the legitimacy of this algorithm anyway, because it's not exactly 'discovering' that the number is a decimal palindrome, rather the numbers being tested are chosen to have that property.

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

Re: Double base palindromes

Wed Sep 22, 2021 11:51 pm

kilograham wrote:
Wed Sep 22, 2021 9:11 pm
Go (tinygo) is available
Woohoo! Is this

https://tinygo.org/docs/reference/micro ... lers/pico/

the correct link to download it? It looks like serial over USB is not supported yet.

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

Re: Double base palindromes

Thu Sep 23, 2021 12:39 am

ejolson wrote:
Wed Sep 22, 2021 8:11 pm
As this thread is in the Pico section, one is somewhat constrained by which programming languages are available. At this point I understand that to be
  • C/C++ and Assembler
  • MicroPython and CircuitPython
  • BBC and MicroMite Basic
  • Inform
with partial support for
  • Free Pascal
  • Rust
Are there any language options for the Pico left out?
And also back to the argument whether C runs on a Pico, there isn't a C compiler so the Pico only sees native binary. I'm not sure how pedantic that is but C is not in the same classification as Python or the Basics which run entirely on the Pico but of course they are interpreters but until a C compiler appears on the Pico, the Pico doesn't see any C.

I keep wondering whether the SDK can compile the intermediate C from Freebasic, I haven't found any mention on the internet as yet.

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

Re: Double base palindromes

Thu Sep 23, 2021 4:37 am

RichardRussell wrote:
Wed Sep 22, 2021 10:03 pm
RichardRussell wrote:
Wed Sep 22, 2021 6:22 pm
The fastest I've managed to achieve is 0.42 seconds
This gets it down to 0.39 seconds in BBC BASIC (yes I know I'm looping more times than I need to but I've still not found a faster solution):

Code: Select all

   10 TIME=0
   20 Ln2=LN2
   30 Sum=0
   40 FOR A%=100001 TO 900009 STEP 200002
   50   FOR B%=0 TO 90090 STEP 10010
   60     FOR X%=A%+B% TO A%+B%+9900 STEP 1100
   70       PROCbc(X%)
   80     NEXT
   90   NEXT
  100 NEXT
  110 FOR A%=10001 TO 90009 STEP 20002
  120   FOR B%=0 TO 9090 STEP 1010
  130     FOR X%=A%+B% TO A%+B%+900 STEP 100
  140       PROCbc(X%)
  150     NEXT
  160   NEXT
  170 NEXT
  180 FOR A%=1001 TO 9009 STEP 2002
  190   FOR B%=0 TO 990 STEP 110
  200     PROCbc(A%+B%)
  210   NEXT
  220 NEXT
  230 FOR A%=101 TO 909 STEP 202
  240   FOR B%=0 TO 90 STEP 10
  250     PROCbc(A%+B%)
  260   NEXT
  270 NEXT
  280 FOR X%=11 TO 99 STEP 22
  290   PROCbc(X%)
  300 NEXT
  310 FOR N%=1 TO 9 STEP 2
  320   Sum += N%
  330 NEXT
  340 PRINT "Sum of all double-base palindromes: "; Sum
  350 PRINT "Calculation time: "; TIME/100; " seconds"
  360 END
  370
  380 DEF PROCbc(N%)
  390 LOCAL P%,Q%
  400 P%=N%:Q%=1<<(LNN%/Ln2)
  410 WHILE P%
  420   IF (P%EORN%DIVQ%)AND1 ENDPROC
  430   P%DIV=2:Q%DIV=2
  440 ENDWHILE
  450 Sum += N%
  460 ENDPROC
I'm concerned about the legitimacy of this algorithm anyway, because it's not exactly 'discovering' that the number is a decimal palindrome, rather the numbers being tested are chosen to have that property.
Woohoo! It's amazing how counting the leading zeros using logarithms without a floating-point unit leads to a program which is about 10 times faster than my code from

viewtopic.php?p=1916324#p1916324

Using the build of BBC Basic from

viewtopic.php?p=1916315#p1916315

I can confirm the improved run times as

Code: Select all

>RUN
Sum of all double-base palindromes: 872187
Calculation time: 0.38 seconds
>RUN
Sum of all double-base palindromes: 872187
Calculation time: 0.38 seconds
>RUN
Sum of all double-base palindromes: 872187
Calculation time: 0.39 seconds
>RUN
Sum of all double-base palindromes: 872187
Calculation time: 0.38 seconds

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

Re: Double base palindromes

Thu Sep 23, 2021 4:48 am

pidd wrote:
Thu Sep 23, 2021 12:39 am
I keep wondering whether the SDK can compile the intermediate C from Freebasic, I haven't found any mention on the internet as yet.
Beware there may still be a bug in the C back end of Freebasic which generates code using calls to longjmp without the volatile declarations needed for the gcc optimizer. Since the default optimization in the Pico SDK is -O3, I'd specifically turn the optimizer off with -Og when trying to get any C generated by Freebasic to compile. If that works, one could then check higher levels of optimization or possibly insert the necessary volatile declarations as gcc will warn you which variables might unexpectedly get clobbered across calls to longjmp.

WestfW
Posts: 123
Joined: Tue Nov 01, 2011 9:56 pm

Re: Double base palindromes

Thu Sep 23, 2021 5:48 am

Many high level languages have an easy mechanism for calling code written in C, but C has no such need to do the reverse.
I've seen otherwise fast compiled languages "call" system utility programs (with the equivalent of "system()") when there was a (potentially) large on-disk database to sort. It probably makes a lot of sense, some of the time.
[cheating]
Well, it would certainly be cheating if we were trying to compare languages. But in this case, we're comparing overall system-level behavior, using whatever cheats are readily available. Using an machine code check() function for a BASIC program doesn't really seem like cheating "more" than using the PIO to do bit reversal, or even the CLZ/REV version (very much calling asm from C in PICO's case, but still cheating even if those were native ARM instructions, since they're stepping outside of C.)
We're not trying to claim that BASIC is a horrible language because it's so much slower than C, we are just noticing that "the algorithm still works pretty well.")

(Heh. It reminds be of a crypto class I took, where one of the assignments included "just iterate through all 2^32 possible values of x", which was a bit mind boggling since I had been working on slow-ish 8bit microcontrollers for a while. It only took about 7 seconds on my desktop, though.)
(and that's why Python is popular, too. You can simply express the solution to a problem, and whatever cringe you may feel "knowing" how awful it is to have implemented an array as a dictionary indexed by a string, when you run it, it is 'fast enough.')

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

Re: Double base palindromes

Thu Sep 23, 2021 9:22 am

ejolson wrote:
Wed Sep 22, 2021 8:11 pm
As this thread is in the Pico section, one is somewhat constrained by which programming languages are available. At this point I understand that to be
  • C/C++ and Assembler
  • MicroPython and CircuitPython
  • BBC and MicroMite Basic
  • Inform
with partial support for
  • Free Pascal
  • Rust
Are there any language options for the Pico left out?
Ada, Forth, Go, JavaScript, Lisp, Lua, There is also a Blockly/Scratch-style drag-and-drop visual programming environment. Not sure what level of support each offers.

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

Re: Double base palindromes

Thu Sep 23, 2021 10:20 am

RichardRussell wrote:
Wed Sep 22, 2021 10:03 pm
I'm concerned about the legitimacy of this algorithm anyway, because it's not exactly 'discovering' that the number is a decimal palindrome, rather the numbers being tested are chosen to have that property.
Also, palindromic generators ought to at least include an additional report to verify they are in fact generating all decimal palindromes, not generating duplicates, and getting lucky because those aren't binary palindromes. That's a flaw, not by design, except when it can be shown to be by design.

A simple count of how many decimals were tested as binary ought to do it. I make that 1110.

Admission : My own MicroPython plus PIO code generates duplicate 'n0n'.

User avatar
RichardRussell
Posts: 1112
Joined: Thu Jun 21, 2012 10:48 am

Re: Double base palindromes

Thu Sep 23, 2021 11:24 am

hippy wrote:
Thu Sep 23, 2021 10:20 am
A simple count of how many decimals were tested as binary ought to do it. I make that 1110.
Yes, adding a count to the BBC BASIC program gives:

Code: Select all

Number of decimal palindromes tested: 1110
Sum of all double-base palindromes: 872187

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

Re: Double base palindromes

Thu Sep 23, 2021 1:58 pm

WestfW wrote:
Thu Sep 23, 2021 5:48 am
[cheating]
Well, it would certainly be cheating if we were trying to compare languages. But in this case, we're comparing overall system-level behavior, using whatever cheats are readily available. Using an machine code check() function for a BASIC program doesn't really seem like cheating "more" than using the PIO to do bit reversal, or even the CLZ/REV version (very much calling asm from C in PICO's case, but still cheating even if those were native ARM instructions, since they're stepping outside of C.)
Of course. In this context the term would be used in jest.

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

Re: Double base palindromes

Thu Sep 23, 2021 2:12 pm

hippy wrote:
Thu Sep 23, 2021 9:22 am
ejolson wrote:
Wed Sep 22, 2021 8:11 pm
As this thread is in the Pico section, one is somewhat constrained by which programming languages are available. At this point I understand that to be
  • C/C++ and Assembler
  • MicroPython and CircuitPython
  • BBC and MicroMite Basic
  • Inform
with partial support for
  • Free Pascal
  • Rust
Are there any language options for the Pico left out?
Ada, Forth, Go, JavaScript, Lisp, Lua, There is also a Blockly/Scratch-style drag-and-drop visual programming environment. Not sure what level of support each offers.
Could you provide links?

Except for USB support, it looks to me like tinygo is pretty feature complete. It uses the LLVM backend to generate code and the same parser as standard Go to process the source. The initialisation code has been extended, but the map type is more limited.

Since I have only a USB cable connected to my Pico, it's difficult to find palindromes using any language that only supports the serial UART.

Is lack of USB support simply priorities? I'd think it possible to link to tinyusb from tinygo with a simple wrapper to convert the Go application binary interface to the one used by C. As far as I can tell, Free Pascal and Rust have the same problem.

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

Re: Double base palindromes

Thu Sep 23, 2021 3:33 pm

ejolson wrote:
Thu Sep 23, 2021 2:12 pm
Since I have only a USB cable connected to my Pico, it's difficult to find palindromes using any language that only supports the serial UART.
How do you deal with this when using USB only?

After you press the white button and plug in your Pico to upload a .uf2 file there is no emulated USB COM port for your terminal program to connect with. As soon as the .uf2 file is uploaded the Pico reboots to the fresh image, and becomes a USB COM device. By the time I get to issue the terminal program (running on the host) commands to connect to the newly created COM device, I've already missed any output issued by the Pico.

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

Re: Double base palindromes

Thu Sep 23, 2021 3:58 pm

lurk101 wrote:
Thu Sep 23, 2021 3:33 pm
ejolson wrote:
Thu Sep 23, 2021 2:12 pm
Since I have only a USB cable connected to my Pico, it's difficult to find palindromes using any language that only supports the serial UART.
How do you deal with this when using USB only?

After you press the white button and plug in your Pico to upload a .uf2 file there is no emulated USB COM port for your terminal program to connect with. As soon as the .uf2 file is uploaded the Pico reboots to the fresh image, and becomes a USB COM device. By the time I get to issue the terminal program (running on the host) commands to connect to the newly created COM device, I've already missed any output issued by the Pico.
Add code on the Pico to wait until the USB COM device is connected.

There is a working example in the BBC Basic interpreter. It's complicated by the fact that one doesn't want to wait when executing an autorun file that blinks the LED but this pushed the wait code into its own subroutine so it is easier to spot.

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

Re: Double base palindromes

Thu Sep 23, 2021 4:13 pm

ejolson wrote:
Thu Sep 23, 2021 2:12 pm
hippy wrote:
Thu Sep 23, 2021 9:22 am
Ada, Forth, Go, JavaScript, Lisp, Lua, There is also a Blockly/Scratch-style drag-and-drop visual programming environment. Not sure what level of support each offers.
Could you provide links?
https://gitter.im/ada-lang/raspberrypi- ... ce=orgpage
viewtopic.php?t=305350
https://github.com/skvamme/pico_atlast
https://giters.com/wa1tnr/camelforth-rp2040-a
viewtopic.php?t=304964
http://www.ulisp.com/show?3KN3
https://github.com/technoblogy/ulisp-arm
https://github.com/kevinboone/luapico
https://www.hackster.io/news/bipes-brin ... 754e9c9d82

In theory it should be possible to convert any interpreter-plus-VM written in C, which compiles and runs on a Pi, to run on an RP2040 -- though its not always that easy in practice.

My interest is going one step beyond that and integrating interpreter VM's within MicroPython. My Holy Grail is a C interpreter though I haven't achieved that yet.

I am surprised no one's brought a JVM to a Pico yet. I had a go at that, and porting a variety of other languages, but, as I am not a C programmer by trade, I find it hard going at the best of times.
Last edited by hippy on Thu Sep 23, 2021 5:03 pm, edited 1 time in total.

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

Re: Double base palindromes

Thu Sep 23, 2021 4:31 pm

hippy wrote:
Thu Sep 23, 2021 4:13 pm
ejolson wrote:
Thu Sep 23, 2021 2:12 pm
hippy wrote:
Thu Sep 23, 2021 9:22 am
Ada, Forth, Go, JavaScript, Lisp, Lua, There is also a Blockly/Scratch-style drag-and-drop visual programming environment. Not sure what level of support each offers.
Could you provide links?
https://gitter.im/ada-lang/raspberrypi- ... ce=orgpage
viewtopic.php?t=305350
https://github.com/skvamme/pico_atlasth ... h-rp2040-a
viewtopic.php?t=304964
http://www.ulisp.com/show?3KN3
https://github.com/technoblogy/ulisp-arm
https://github.com/kevinboone/luapico
https://www.hackster.io/news/bipes-brin ... 754e9c9d82

In theory it should be possible to convert any interpreter-plus-VM written in C, which compiles and runs on a Pi, to run on an RP2040 -- though its not always that easy in practice.

My interest is going one step beyond that and integrating interpreter VM's within MicroPython. My Holy Grail is a C interpreter though I haven't achieved that yet.

I am surprised no one's brought a JVM to a Pico yet. I had a go at that, and porting a variety of other languages, but, as I am not a C programmer by trade, I find it hard going at the best of times.
Thanks for that list. The third link doesn't work but otherwise very interesting.

Given time I might try finding multiple-base palindromes using picolua. Though listed as a proof of concept, the port claims to include USB, an editor and saves files to the built-in flash using LittleFS.

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

Re: Double base palindromes

Thu Sep 23, 2021 5:07 pm

ejolson wrote:
Thu Sep 23, 2021 3:58 pm
lurk101 wrote:
Thu Sep 23, 2021 3:33 pm
ejolson wrote:
Thu Sep 23, 2021 2:12 pm
Since I have only a USB cable connected to my Pico, it's difficult to find palindromes using any language that only supports the serial UART.
How do you deal with this when using USB only?

After you press the white button and plug in your Pico to upload a .uf2 file there is no emulated USB COM port for your terminal program to connect with. As soon as the .uf2 file is uploaded the Pico reboots to the fresh image, and becomes a USB COM device. By the time I get to issue the terminal program (running on the host) commands to connect to the newly created COM device, I've already missed any output issued by the Pico.
Add code on the Pico to wait until the USB COM device is connected.

There is a working example in the BBC Basic interpreter. It's complicated by the fact that one doesn't want to wait when executing an autorun file that blinks the LED but this pushed the wait code into its own subroutine so it is easier to spot.

I notice that you blink the LED in your 'waiting for UART' code where you simply wait for 10 seconds. Typically there is no need to wait there since the terminal program will already connected to a real serial port at the time the Pico starts.
But then you'd need to know the USB port was intended to be connected. My goal (and yours I think) is to make a program use either, whichever is in use. Waiting for USB when the connection is to UART could take a while!
Last edited by lurk101 on Thu Sep 23, 2021 5:18 pm, edited 1 time in total.

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

Re: Double base palindromes

Thu Sep 23, 2021 5:09 pm

Oops. Lost a line-break between third and fourth. Now fixed.

I HAZ LOLCODES SO CLOSE ON YA PICO. GONNA BE BAD 1 DAY BLOOD - viewtopic.php?t=242139

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

Re: Double base palindromes

Thu Sep 23, 2021 6:49 pm

lurk101 wrote:
Thu Sep 23, 2021 5:07 pm
ejolson wrote:
Thu Sep 23, 2021 3:58 pm
lurk101 wrote:
Thu Sep 23, 2021 3:33 pm

How do you deal with this when using USB only?

After you press the white button and plug in your Pico to upload a .uf2 file there is no emulated USB COM port for your terminal program to connect with. As soon as the .uf2 file is uploaded the Pico reboots to the fresh image, and becomes a USB COM device. By the time I get to issue the terminal program (running on the host) commands to connect to the newly created COM device, I've already missed any output issued by the Pico.
Add code on the Pico to wait until the USB COM device is connected.

There is a working example in the BBC Basic interpreter. It's complicated by the fact that one doesn't want to wait when executing an autorun file that blinks the LED but this pushed the wait code into its own subroutine so it is easier to spot.

I notice that you blink the LED in your 'waiting for UART' code where you simply wait for 10 seconds. Typically there is no need to wait there since the terminal program will already connected to a real serial port at the time the Pico starts.
But then you'd need to know the USB port was intended to be connected. My goal (and yours I think) is to make a program use either, whichever is in use. Waiting for USB when the connection is to UART could take a while!
This autodetect seems to work.

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include "pico/stdlib.h"
#include "tusb.h"

void stdio_init(int uart_rx_pin) {
    gpio_init(uart_rx_pin);
    gpio_set_pulls(uart_rx_pin, 1, 0);
    sleep_ms(1);
    bool v1 = gpio_get(uart_rx_pin);
    gpio_set_pulls(uart_rx_pin, 0, 1);
    sleep_ms(1);
    bool v2 = gpio_get(uart_rx_pin);
    gpio_set_pulls(uart_rx_pin, 0, 0);
    if (v1 != v2) {
        stdio_usb_init();
        while (!tud_cdc_connected())
            sleep_ms(1000);
    } else {
        stdio_uart_init();
        getchar_timeout_us(1000);
    }
}

int main() {
    stdio_init(PICO_DEFAULT_UART_RX_PIN);
    printf("Hello world\n");
    for (;;)
        ;
}
with

Code: Select all

pico_enable_stdio_uart(test 1)
pico_enable_stdio_usb(test 1)
and gets around IO to both drivers.

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

Re: Double base palindromes

Thu Sep 23, 2021 8:46 pm

lurk101 wrote:
Thu Sep 23, 2021 5:07 pm
ejolson wrote:
Thu Sep 23, 2021 3:58 pm
lurk101 wrote:
Thu Sep 23, 2021 3:33 pm

How do you deal with this when using USB only?

After you press the white button and plug in your Pico to upload a .uf2 file there is no emulated USB COM port for your terminal program to connect with. As soon as the .uf2 file is uploaded the Pico reboots to the fresh image, and becomes a USB COM device. By the time I get to issue the terminal program (running on the host) commands to connect to the newly created COM device, I've already missed any output issued by the Pico.
Add code on the Pico to wait until the USB COM device is connected.

There is a working example in the BBC Basic interpreter. It's complicated by the fact that one doesn't want to wait when executing an autorun file that blinks the LED but this pushed the wait code into its own subroutine so it is easier to spot.
I notice that you blink the LED in your 'waiting for UART' code where you simply wait for 10 seconds. Typically there is no need to wait there since the terminal program will already connected to a real serial port at the time the Pico starts.

But then you'd need to know the USB port was intended to be connected. My goal (and yours I think) is to make a program use either, whichever is in use. Waiting for USB when the connection is to UART could take a while!
Something went wrong again with quoting something I didn't write so I fixed it.

I think the idea behind autodetect USB or UART was to check for actual input from either device. I would prefer to keep that discussion in a different thread

viewtopic.php?f=144&t=311703

so we can focus on palindromes here.

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

Re: Double base palindromes

Thu Sep 23, 2021 9:31 pm

ejolson wrote:
Thu Sep 23, 2021 8:46 pm
I would prefer to keep that discussion in a different thread

viewtopic.php?f=144&t=311703

so we can focus on palindromes here.
Oh! Ok. But this thread has pretty much run its course. Have you found the elusive 2,3,5 palindrome yet?

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

Re: Double base palindromes

Fri Sep 24, 2021 5:09 am

lurk101 wrote:
Thu Sep 23, 2021 9:31 pm
ejolson wrote:
Thu Sep 23, 2021 8:46 pm
I would prefer to keep that discussion in a different thread

viewtopic.php?f=144&t=311703

so we can focus on palindromes here.
Oh! Ok. But this thread has pretty much run its course. Have you found the elusive 2,3,5 palindrome yet?
Finding a number which is simultaneously a palindrome in bases 2, 3 and 5 seems hopeless; however, I was working on a palindrome finder for Kevin Boone's Pico-based lua programming environment.

https://github.com/kevinboone/luapico

After uploading the program euler36.lua to the Pico using ymodem, I obtained

Code: Select all

$ lua -v                                                                        
Lua 5.4.2  Copyright (C) 1994-2020 Lua.org, PUC-Rio                             
$ lua euler36.lua
euler36--Multibase Palindrome Finding Program
Written 2021 by Eric Olson

Summing palindromes from 1 up to 1000000...
done

Sum of all double-base palindromes:  872187
Calculation time 1.325000 seconds.
For reference the code is

Code: Select all

--  euler36.lua -- Multibase Palindrome Finding Program
--  Written 2021 by Eric Olson
--
--  Requires lua 5.3 or greater for bitwise operators

digits=6

function tic()
    tictime=time_ms()
end

function toc()
    return (time_ms()-tictime)/1000
end

function len32(x)
    local n
    n=1
    if x>=1<<16 then
        x=x>>16
        n=n+16
    end
    if x>=1<<8 then
        x=x>>8
        n=n+8
    end
    if x>=1<<4 then
        x=x>>4
        n=n+4
    end
    if x>=1<<2 then
        x=x>>2
        n=n+2
    end
    if x>=1<<1 then
        x=x>>1
        n=n+1
    end
    return n
end

function pow10(n)
    local p,r
    p=10
    if n==0 then
        return 1
    end
    r=1
    while true do
        if n&1==1 then
            r=r*p
        end
        n=n>>1
        if n==0 then
            return r
        end
        p=p*p
    end
end

function mkbasis(k)
    local b,i,n
    n=(k+1)>>1
    b={}
    for i=1,n do
        if i==k-i+1 then
            b[i]=pow10(i-1)
        else
            b[i]=pow10(i-1)+pow10(k-i)
        end
    end
    return b
end

function next(c)
    local j,r
    r=2
    j=1
    while true do
        if c[j]==9 then
            c[j]=c[j]+r-10
            r=1
            j=j+1
            if c[j]==nil then
                return false
            end
        else
            c[j]=c[j]+r
            return true
        end
    end
end

function dot(a,b)
    local i,r,v
    r=0
    for i,v in ipairs(a) do
        r=r+v*b[i]
    end
    return r
end

function ispal(n)
    local i,m
    m=len32(n)
    for i=1,m>>1 do
        if n>>(i-1)&1 ~= n>>(m-i)&1 then
            return false
        end
    end
    return true
end

function main()
    local b,c,count,i,k,tsec,v,x
    print("euler36--Multibase Palindrome Finding Program\n"..
        "Written 2021 by Eric Olson\n")
    print("Summing palindromes from 1 up to "..pow10(digits).."...")
    tic()
    count=0
    for k=1,digits do
        b=mkbasis(k)
        c={}
        for i,v in ipairs(b) do
            c[i]=0
        end
        c[1]=1
        while true do
            x=dot(c,b)
            if ispal(x) then
                count=count+x
            end
            if not next(c) then
                break
            end
        end
    end
    tsec=toc()
    print("done")
    print("\nSum of all double-base palindromes:  "..count.."\n"..
        "Calculation time "..tsec.." seconds.")
end

main()
I suspect optimizing the len32 function--perhaps by using logarithms--could lead to execution times under a second. I did not try any such performance tuning.

It's also worth pointing out all arrays in lua are associative arrays and that could also lead to loss of performance.
Last edited by ejolson on Fri Sep 24, 2021 3:28 pm, edited 10 times in total.

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

Re: Double base palindromes

Fri Sep 24, 2021 5:20 am

ejolson wrote:
Thu Sep 23, 2021 4:37 am
Woohoo! It's amazing how counting the leading zeros using logarithms without a floating-point unit leads to a program which is about 10 times faster than my code from

viewtopic.php?p=1916324#p1916324

Using the build of BBC Basic from

viewtopic.php?p=1916315#p1916315

I can confirm the improved run times as

Code: Select all

>RUN
Sum of all double-base palindromes: 872187
Calculation time: 0.38 seconds
>RUN
Sum of all double-base palindromes: 872187
Calculation time: 0.38 seconds
>RUN
Sum of all double-base palindromes: 872187
Calculation time: 0.39 seconds
>RUN
Sum of all double-base palindromes: 872187
Calculation time: 0.38 seconds
Note the above 0.38 second timings for the Pico version of BBC Basic were made at the default 125 MHz clock speed. If overclocked to 250 MHz one might expect a runtime closer to 0.19 seconds.

User avatar
RichardRussell
Posts: 1112
Joined: Thu Jun 21, 2012 10:48 am

Re: Double base palindromes

Fri Sep 24, 2021 7:45 pm

ejolson wrote:
Fri Sep 24, 2021 5:09 am
Finding a number which is simultaneously a palindrome in bases 2, 3 and 5 seems hopeless
There are only 17 known numbers which are palindromes in both base-2 and base-3, none (apart from the trivial 0 and 1) is also a palindrome in base-5.

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

Re: Double base palindromes

Fri Sep 24, 2021 8:12 pm

ejolson wrote:
Fri Sep 24, 2021 5:20 am
ejolson wrote:
Thu Sep 23, 2021 4:37 am
Woohoo! It's amazing how counting the leading zeros using logarithms without a floating-point unit leads to a program which is about 10 times faster than my code from

viewtopic.php?p=1916324#p1916324

Using the build of BBC Basic from

viewtopic.php?p=1916315#p1916315

I can confirm the improved run times as

Code: Select all

>RUN
Sum of all double-base palindromes: 872187
Calculation time: 0.38 seconds
>RUN
Sum of all double-base palindromes: 872187
Calculation time: 0.38 seconds
>RUN
Sum of all double-base palindromes: 872187
Calculation time: 0.39 seconds
>RUN
Sum of all double-base palindromes: 872187
Calculation time: 0.38 seconds
Note the above 0.38 second timings for the Pico version of BBC Basic were made at the default 125 MHz clock speed. If overclocked to 250 MHz one might expect a runtime closer to 0.19 seconds.
I decided to replace the logarithms for computing the length of a binary number in the BBC Basic program with the same algorithm used in the Lua code. This resulted in

Code: Select all

>RUN
Sum of all double-base palindromes: 872187
Calculation time: 0.61 seconds
>LIST
   10 TIME=0
   20 Ln2=LN2
   30 Sum=0
   40 FOR A%=100001 TO 900009 STEP 200002
   50   FOR B%=0 TO 90090 STEP 10010
   60     FOR X%=A%+B% TO A%+B%+9900 STEP 1100
   70       PROCbc(X%)
   80     NEXT
   90   NEXT
  100 NEXT
  110 FOR A%=10001 TO 90009 STEP 20002
  120   FOR B%=0 TO 9090 STEP 1010
  130     FOR X%=A%+B% TO A%+B%+900 STEP 100
  140       PROCbc(X%)
  150     NEXT
  160   NEXT
  170 NEXT
  180 FOR A%=1001 TO 9009 STEP 2002
  190   FOR B%=0 TO 990 STEP 110
  200     PROCbc(A%+B%)
  210   NEXT
  220 NEXT
  230 FOR A%=101 TO 909 STEP 202
  240   FOR B%=0 TO 90 STEP 10
  250     PROCbc(A%+B%)
  260   NEXT
  270 NEXT
  280 FOR X%=11 TO 99 STEP 22
  290   PROCbc(X%)
  300 NEXT
  310 FOR N%=1 TO 9 STEP 2
  320   Sum += N%
  330 NEXT
  340 PRINT "Sum of all double-base palindromes: "; Sum
  350 PRINT "Calculation time: "; TIME/100; " seconds"
  360 END
  380 DEF PROCbc(N%)
  390 LOCAL P%,Q%
  400 P%=N%:Q%=1<<FNlen32(N%)
  410 WHILE P%
  420   IF (P%EORN%DIVQ%)AND1 ENDPROC
  430   P%DIV=2:Q%DIV=2
  440 ENDWHILE
  450 Sum += N%
  460 ENDPROC
  500 DEF FNlen32(X%)
  510 LOCAL N%
  520 N%=0
  530 IF X%>=65536 THEN
  540   X%=X%>>16
  550   N%=N%+16
  560 ENDIF
  570 IF X%>=256 THEN
  580   X%=X%>>8
  590   N%=N%+8
  600 ENDIF
  610 IF X%>=16 THEN
  620   X%=X%>>4
  630   N%=N%+4
  640 ENDIF
  650 IF X%>=4 THEN
  660   X%=X%>>2
  670   N%=N%+2
  680 ENDIF
  690 IF X%>=2 THEN
  700   X%=X%>>1
  710   N%=N%+1
  720 ENDIF
  730 =N%
which is slower than with the logarithms.

Then I decided to use the logarithm approach in the Lua code and obtained

Code: Select all

$ lua another36.lua                                                            
euler36--Multibase Palindrome Finding Program                                  
Written 2021 by Eric Olson                                                     
                                                                               
Summing palindromes from 1 up to 1000000...                                    
done                                                                           
                                                                               
Sum of all double-base palindromes:  872187                                    
Calculation time 1.593000 seconds.                                             
$ cat another36.lua                                                            
--  euler36.lua -- Multibase Palindrome Finding Program                        
--  Written 2021 by Eric Olson                                                 
--                                                                             
--  Requires lua 5.3 or greater for bitwise operators
                                                                               
digits=6
lof2=math.log(2)                                                                
                                                                                
function tic()                                                                  
    tictime=time_ms()                                                           
end                                                                             
                                                                                
function toc()                                                                  
    return (time_ms()-tictime)/1000                                             
end                                                                             
                                                                                
function pow10(n)                                                               
    local p,r                                                                   
    p=10                                                                        
    if n==0 then                                                                
        return 1                                                                
    end                                                                         
    r=1                                                                         
    while true do                                                               
        if n&1==1 then                                                          
            r=r*p                                                               
        end                                                                     
        n=n>>1                                                                  
        if n==0 then                                                            
            return r                                                            
        end                                                                     
        p=p*p                                                                   
    end                                                                         
end                                                                             
                                                                                
function mkbasis(k)                                                             
    local b,i,n                                                                 
    n=(k+1)>>1                                                                  
    b={}                                                                        
    for i=1,n do                                                                
        if i==k-i+1 then                                                        
            b[i]=pow10(i-1)                                                     
        else                                                                    
            b[i]=pow10(i-1)+pow10(k-i)                                          
        end                                                                     
    end                                                                         
    return b                                                                    
end                                                                             
                                                                                
function next(c)                                                                
    local j,r                                                                   
    r=2                                                                         
    j=1                                                                         
    while true do                                                               
        if c[j]==9 then                                                         
            c[j]=c[j]+r-10                                                      
            r=1                                                                 
            j=j+1                                                               
            if c[j]==nil then                                                   
                return false                                                    
            end                                                                 
        else                                                                    
            c[j]=c[j]+r                                                         
            return true                                                         
        end                                                                     
    end                                                                         
end                                                                             
                                                                                
function dot(a,b)                                                               
    local i,r,v                                                                 
    r=0                                                                         
    for i,v in ipairs(a) do                                                     
        r=r+v*b[i]                                                              
    end                                                                         
    return r                                                                    
end                                                                             
                                                                                
function ispal(n)                                                               
    local i,m                                                                   
    m=math.floor(math.log(n)/lof2)+1                                            
    for i=1,m>>1 do                                                             
        if n>>(i-1)&1 ~= n>>(m-i)&1 then                                        
            return false                                                        
        end                                                                     
    end                                                                         
    return true                                                                 
end                                                                             
                                                                                
function main()                                                                 
    local b,c,count,i,k,tsec,v,x                                                
    print("euler36--Multibase Palindrome Finding Program\n"..                   
        "Written 2021 by Eric Olson\n")                                         
    print("Summing palindromes from 1 up to "..pow10(digits).."...")            
    tic()                                                                       
    count=0                                                                     
    for k=1,digits do                                                           
        b=mkbasis(k)                                                            
        c={}                                                                    
        for i,v in ipairs(b) do                                                 
            c[i]=0                                                              
        end                                                                     
        c[1]=1                                                                  
        while true do                                                           
            x=dot(c,b)                                                          
            if ispal(x) then                                                    
                count=count+x                                                   
            end                                                                 
            if not next(c) then                                                 
                break                                                           
            end                                                                 
        end                                                                     
    end                                                                         
    tsec=toc()                                                                  
    print("done")                                                               
    print("\nSum of all double-base palindromes:  "..count.."\n"..              
        "Calculation time "..tsec.." seconds.")                                 
end                                                                             
                                                                                
main()                                                                          
which is slower than without the logarithms.

After double checking to make sure the logarithms weren't being confused with horse reins, both appear to confirm Murphy's law and its converse can operate simultaneously.

A summary of the timings is

Code: Select all

          Lua    Basic 
len32   1.325     0.61 
log     1.593     0.38
I find it interesting that using logarithms results in faster run times for BBC Basic but the shift and search method results in faster timings for Lua.
Last edited by ejolson on Sat Sep 25, 2021 2:07 am, edited 2 times in total.

Return to “General”