Programming puzzle: Longest list of regular numbers?

04172017, 07:52 PM
Post: #21




RE: Programming puzzle: Longest list of regular numbers?
(04172017 07:06 PM)pier4r Wrote: You just solved 2 in 204 seconds on a Hp 48? Impressive. 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. Graph 3D  QPI  SolveSys 

04172017, 07:53 PM
Post: #22




RE: Programming puzzle: Longest list of regular numbers?
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 builtin 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! 

04182017, 07:13 PM
Post: #23




RE: Programming puzzle: Longest list of regular numbers?
Just saw this: http://www.hpmuseum.org/forum/thread8201.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. Wikis are great, Contribute :) 

04182017, 07:22 PM
(This post was last modified: 04182017 07:34 PM by Han.)
Post: #24




RE: Programming puzzle: Longest list of regular numbers?
(04182017 07:13 PM)pier4r Wrote: Just saw this: http://www.hpmuseum.org/forum/thread8201.html Using the TEVAL command, the hardware calculator returns 0.828 seconds for the 1429th Hamming number. And it takes the Prime 133.468 seconds to compute the 9733rd value. I created a CAS equivalent function in order to handle larger numbers, which ran slightly slower (3.167 seconds) than the nonCAS version when computing the 1429th value. Graph 3D  QPI  SolveSys 

04182017, 10:09 PM
(This post was last modified: 04192017 03:27 PM by Claudio L..)
Post: #25




RE: Programming puzzle: Longest list of regular numbers?
(04182017 07:22 PM)Han Wrote:(04182017 07:13 PM)pier4r Wrote: Just saw this: http://www.hpmuseum.org/forum/thread8201.html 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). 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 64bit integers can be used. For larger numbers the variable precision floating point kicks in and should slow down considerably. 

04182017, 10:36 PM
Post: #26




RE: Programming puzzle: Longest list of regular numbers?
(04182017 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. 

04182017, 11:10 PM
Post: #27




RE: Programming puzzle: Longest list of regular numbers?
Impressive the new rpl, even faster than the prime
Wikis are great, Contribute :) 

04192017, 10:43 AM
Post: #28




RE: Programming puzzle: Longest list of regular numbers?
This convinced me to try out newRPL (just got myself a spare 50g)


04192017, 03:09 PM
(This post was last modified: 04192017 03:27 PM by Claudio L..)
Post: #29




RE: Programming puzzle: Longest list of regular numbers?
(04182017 10:36 PM)Claudio L. Wrote:(04182017 10:09 PM)Claudio L. Wrote: 14999 ==> newRPL: 94.8 seconds, the result is 2305843009213693952 = 2^61 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:
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 64bit 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. 

04192017, 04:06 PM
(This post was last modified: 04192017 04:06 PM by pier4r.)
Post: #30




RE: Programming puzzle: Longest list of regular numbers?
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. Wikis are great, Contribute :) 

01132021, 06:39 PM
(This post was last modified: 01142021 06:53 AM by C.Ret.)
Post: #31




RE: Programming puzzle: Longest list of regular numbers?
(04182017 07:22 PM)Han Wrote:(04182017 07:13 PM)pier4r Wrote: Just saw this: http://www.hpmuseum.org/forum/thread8201.html 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 Casmode, 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} \; = \; 632373585725680579031685776908592159413202566649380479277264004972544000000000000 \; = \; 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. 

01162021, 09:33 PM
Post: #32




RE: Programming puzzle: Longest list of regular numbers?
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 12digit 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. 

01172021, 09:02 PM
(This post was last modified: 01182021 06:02 PM by C.Ret.)
Post: #33




RE: Programming puzzle: Longest list of regular numbers?
Hi,
I may suggest changing your algorithm, I get up to the 3428th in 2min7sec on my HP28S. The HP50g have much more punch than my ageless HP28S. I am sure you will break easily my record ! Feel free to adapt this HP28S style code; Code: HAM: Where HRAZ is : Code: HRAZ: On HP48/50g, faster algorithms may certainly exist storing 'H' as a list in order to take advantage of the builtin SORT instruction that may certainly spare run time. Such an instruction is missing on the HP28s, to avoid sorting, I use a kind of rudimentary (but huge) hashtable; 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 

01182021, 05:44 PM
Post: #34




RE: Programming puzzle: Longest list of regular numbers?
Thanks, I'll check it out when I have some spare time.
The HP48G and later have a builtin SORT command but it is notoriously slow. Fortunately there is LSORT which is orders of magnitude faster. 

01192021, 04:58 PM
(This post was last modified: 01192021 05:10 PM by C.Ret.)
Post: #35




RE: Programming puzzle: Longest list of regular numbers?
(01182021 05:44 PM)John Keith Wrote: The HP48G and later have a builtin 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 homemade HP28S's LSORT program: Code: « → r « HRAZ "Enumaring..." 1 DISP No hashtable 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. 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)