Programming puzzle: Longest list of regular numbers?

[Han]

(04-17-2017 07:06 PM)pier4r Wrote:  You just solved 2 in 204 seconds on a Hp 48? Impressive.

I got the same number of Emil because I did not count 1

Ah clever you saved already the multiplication results instead of doing the over and over

Well, I merely implemented a fairly known algorithm; the algorithm itself is pretty efficient. The HP48 made it slightly nicer in that I could save the table of terms onto the stack.

[e_emil]

Nice code Han! As pier4r says, our sequences begin with two.

I looked at examples from oeis and I attacked Challenge 2 with the first Mathematica code, just changing the range to 604661760 since we already know it's the 1429th number (or 1430th, counting from one). Using the built-in EulerPhi[] function in a loop isn't a recipe for an efficient calculation, so the execution time won't surprise you: 6383 seconds (1 hour 46 minutes) on a fairly modern dell laptop.

Han's hp48 calculation was over 30 times faster than this!

   

[pier4r]

Just saw this: http://www.hpmuseum.org/forum/thread-8201.html

Han, how does the Prime performs?

I do have a Ti89, but I did not use it for years and refreshing the Ti basic now is a no go.

[Han]

(04-18-2017 07:13 PM)pier4r Wrote:  Just saw this: http://www.hpmuseum.org/forum/thread-8201.html

Han, how does the Prime performs?

I do have a Ti89, but I did not use it for years and refreshing the Ti basic now is a no go.

Using the TEVAL command, the hardware calculator returns 0.828 seconds for the 1429-th Hamming number.

And it takes the Prime 133.468 seconds to compute the 9733-rd value. I created a CAS equivalent function in order to handle larger numbers, which ran slightly slower (3.167 seconds) than the non-CAS version when computing the 1429-th value.

[Claudio L.]

(04-18-2017 07:22 PM)Han Wrote:  

(04-18-2017 07:13 PM)pier4r Wrote:  Just saw this: http://www.hpmuseum.org/forum/thread-8201.html

Han, how does the Prime performs?

I do have a Ti89, but I did not use it for years and refreshing the Ti basic now is a no go.

Using the TEVAL command, the hardware calculator returns 0.828 seconds for the 1429-th Hamming number.

And it takes the Prime 133.468 seconds to compute the 9733-rd value. I created a CAS equivalent function in order to handle larger numbers, which ran slightly slower (3.167 seconds) than the non-CAS version when computing the 1429-th value.

For the record:

newRPL running Han's program, unmodified. I did copy/paste from the forum, replaced \<< and other characters with the real Unicode ones and saved as a pure .txt file, put it on an SD card, read the file and compiled with STR->.
For the 1429th value (using 1430 as argument on Han's program, as it counts from one):

1429 ==> newRPL: 0.687 seconds
9733 ==> newRPL: 39.87 seconds without GC (doing MEM before running), 85.21 seconds with heavily fragmented memory (second run immediately after).
14999 ==> newRPL: 94.8 seconds, the result is 2305843009213693952 = 2^61
EDIT:
14999 ==> newRPL: 113.57 seconds, result is 1.236950581248E20
17499 ==> newRPL: 159.46 seconds, result is 1.549681956E21 (only 48 kbytes free memory after)
To answer the original challenge, interpolating linearly between the timings at 17500 and 15000 results, newRPL would obtain 15349 results in 120 seconds.
END EDIT

I maxed out my patience before maxing out the memory. I want to clarify this entry is to report Han's algorithm speed, all credit goes to him for the program as I didn't even read the code.


EDIT: MEM reports 131 kbytes free with all 15000 values on the stack. Also worth clarifying that since these numbers are < 2^63, simple 64-bit integers can be used. For larger numbers the variable precision floating point kicks in and should slow down considerably.

[Claudio L.]

(04-18-2017 10:09 PM)Claudio L. Wrote:  14999 ==> newRPL: 94.8 seconds, the result is 2305843009213693952 = 2^61

I suspect something wrong, the result is the same after iteration 11562 = 2.304e18. All results after that are = 2^61. I need to study the algorithm and what's happening at this iteration so scratch that result off for now.

[pier4r]

Impressive the new rpl, even faster than the prime

[e_emil]

This convinced me to try out newRPL (just got myself a spare 50g)

[Claudio L.]

(04-18-2017 10:36 PM)Claudio L. Wrote:  

(04-18-2017 10:09 PM)Claudio L. Wrote:  14999 ==> newRPL: 94.8 seconds, the result is 2305843009213693952 = 2^61

I suspect something wrong, the result is the same after iteration 11562 = 2.304e18. All results after that are = 2^61. I need to study the algorithm and what's happening at this iteration so scratch that result off for now.

Fixed! There was a bug in newRPL's == operator which was fixed. For those who want to try Han's code, I uploaded a ROM with the fix (to the usual download location).
It also implements MIN and MAX, which to my surprise were not yet implemented (it was an oversight, they were listed under the wrong category in the command database).
I've attached here Han's code with the proper Unicode characters. The actual sequence to get it in the calc is:
put the text on the SD card (hanprog.txt), then do (on the stack):

Code:


"hanprog.txt" SDOPENRD    @ This opens the file and returns a handle number
DUP SDFILESIZE                 @ Get the size of the file
OVER SDREADTEXT           @ Read the entire file as a string
SWAP SDCLOSE                  @ Close the file
STR->                                    @ Compile the program

Now the corrected benchmark results:

14999 --> 113.57 seconds, result is 1.236950581248E20
The slowdown versus the previous report is due to the change from 64-bit integers to variable precision reals after iteration 11563. The bug I fixed never let the result go over 2^63 hence computations were faster. I'll update the original post with the right timings.

[pier4r]

Thumbs up Claudio!

Maybe picking up little programs here and there due to programming challenges (or answers to questions) is a nice way to debug a new system (not only newRPL, I mean in general).

As soon as the newRPL allows usb transfers of programs, I guess I will flood the newRPL thread with questions.

[C.Ret]

(04-18-2017 07:22 PM)Han Wrote:  

(04-18-2017 07:13 PM)pier4r Wrote:  Just saw this: http://www.hpmuseum.org/forum/thread-8201.html

Han, how does the Prime performs?

I do have a Ti89, but I did not use it for years and refreshing the Ti basic now is a no go.

Using the TEVAL command, the hardware calculator returns 0.828 seconds for the 1429-th Hamming number.

And it takes the Prime 133.468 seconds to compute the 9733-rd value. I created a CAS equivalent function in order to handle larger numbers, which ran slightly slower (3.167 seconds) than the non-CAS version when computing the 1429-th value.

I am sorry being outlaw for the challenge; I am off by one unit since I start counting the Hamming Numbers from H(1)=1 in order to be consistant with what was done in another (french) forum.

Using a regular HP Prime in Cas-mode, I get the following results all in less than one second using less than 5% the potential power of the method (mainly limited by no more than 10 000 elements in a regular list).


1429th \(H_{1430}\; = \;2^{11}\,.\,3^{10}\,.\,5\;=\;604661760\; = \;6.0466\,10^8\) ( 166_ms 1.38%_mem)

9733th \( H_{9734}\; = \;2^{30}\,.\,3^{10}\,.\,5^{5}\; = \;198135565516800000\; = \;1.9814\,10^{17}\) ( 575_ms 4.88%_mem)

14999th \(H_{15000}\; = \;2^{45}\,3^{2}\,5^8\; = \;123695058124800000000\; = \;1.237\,10^{20}\) ( 793_ms 6.46%_mem)

https://drive.google.com/file/d/1sMIh5s5...sp=sharing

Next, I compute the 900000th in exactly one minute and ten seconds (using 99.75% of available list's memory), can any one check my result ?

900000th
\( H_{900001}\; = \; 2^{109}\,3^{83}\,5^{12} \; = \; 63237358572568057903168577690859215941320256664938047927726400497254400000000000​0 \; = \; 6.3237\,10^{80} \) ( 1.1_min 99.75%_mem)

Unfortunately, computing the 1E6th is impossible due to a limited list capacity but was expected in less than two minutes.

[John Keith]

Using Han's program, 9733 can be done on the hp 50g if Last Stack is disabled. Takes about 27 minutes on a physical 50g.

For 12-digit calculators a good test number is 3428, since the 3428th Hamming number is the largest one less than 10^12. Should be possible on a 48G with a merged RAM card.

[C.Ret]

Hi,

I may suggest changing your algorithm, I get up to the 3428th in 2min7sec on my HP-28S.
The HP-50g have much more punch than my ageless HP-28S. I am sure you will break easily my record !

Feel free to adapt this HP-28S style code;

Code:

HAM:
« → r « HRAZ 
        WHILE T r <
        REPEAT
            "Enumaring..." 1 DISP
            1 X + 'X' STO
            0  X LA * FOR y
              X LB * y LC * - IP → z
                  « IF 'E' y 1 + GET z < THEN
                                       'E' y 1 + z PUT
                                         N 1 + 'N' STO
                      'H' y L3 * z L5 * + X L2 * -
                           DUP -1250 * IP 1 + SWAP PUT 
                    END »
            NEXT
            T N + 'T' STO
        END 
        "Extracting..." 1 DISP  
        2 X ^ 'H' 1
        T r - 0 FOR i
                   i 2 DISP
                   DO UNTIL GETI END
        -1 STEP  1 - GET EXP * CEIL
        1240 .2 BEEP CLMF » »

DISP were mainly for debugging and later for speed optimization.

Where HRAZ is :

Code:

HRAZ:
«        2 LN 'L2' STO        3 LN 'L3' STO      5 LN 'L5' STO
      L2 L3 / 'LA' STO     L2 L5 / 'LB' STO   L3 L5 / 'LC' STO
             0 'X" STO           1  'N' STO         1  'T' STO
 { 30 } -1 CON 'E' STO {1250} 0 CON  'H' STO  »

I used global variables to keep a trace of what happened after each run. Don't know if that speed-up the computations or not ? Having all these variables local will make the 'user menu' much clearer.


On HP-48/50g, faster algorithms may certainly exist storing 'H' as a list in order to take advantage of the built-in SORT instruction that may certainly spare run time.

Such an instruction is missing on the HP-28s, to avoid sorting, I use a kind of rudimentary (but huge) hash-table; all 'H' values are in the range ] -1 ; 0 ], and relative order is kept for any slide 'X' ; no sorting require, just have to count non null value to extract the result !

Regards.
C.Ret

[John Keith]

Thanks, I'll check it out when I have some spare time.

The HP-48G and later have a built-in SORT command but it is notoriously slow. Fortunately there is LSORT which is orders of magnitude faster.

[C.Ret]

(01-18-2021 05:44 PM)John Keith Wrote:  The HP-48G and later have a built-in SORT command but it is notoriously slow. Fortunately there is LSORT which is orders of magnitude faster.

If you plan to use an LSORT instruction, you may can use a code like the one I made to test my algorithm with a home-made HP-28S's LSORT program:

Code:

« → r « HRAZ "Enumaring..." 1 DISP
        DO
          1 X + 'X' STO
          0  X LA * FOR y
            X LB * y LC * - IP → z
              « IF 'E' y 1 +  GET z < THEN 
                                       'E' y 1 + z PUT
                                         N 1 + 'N' STO
                  H y L3 * z L5 * + X L2 * - + 'H' STO
                END »
          NEXT
          T N + DUP 'T' STO
        UNTIL T r >= END "Sorting..." 1 DISP
        2 X ^ H   LSORT   N r + T - GET EXP * CEIL
        1240 .2 BEEP CLMF » »

No hash-table here, all the value are collected in the 'H' list, then 'H' is sort and the expected result extract from the sorted list directly.
This is the exact algorithm I use on my HP Prime which have a powerfull parametric SORT instruction.