Programming puzzle: Longest list of regular numbers?
04-17-2017, 07:52 PM
Post: #21
 Han Senior Member Posts: 1,810 Joined: Dec 2013
RE: Programming puzzle: Longest list of regular numbers?
(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.

Graph 3D | QPI | SolveSys
04-17-2017, 07:53 PM
Post: #22
 e_emil Junior Member Posts: 9 Joined: Mar 2017
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 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!

04-18-2017, 07:13 PM
Post: #23
 pier4r Senior Member Posts: 2,001 Joined: Nov 2014
RE: Programming puzzle: Longest list of regular numbers?

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 :)
04-18-2017, 07:22 PM (This post was last modified: 04-18-2017 07:34 PM by Han.)
Post: #24
 Han Senior Member Posts: 1,810 Joined: Dec 2013
RE: Programming puzzle: Longest list of regular numbers?
(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.

Graph 3D | QPI | SolveSys
04-18-2017, 10:09 PM (This post was last modified: 04-19-2017 03:27 PM by Claudio L..)
Post: #25
 Claudio L. Senior Member Posts: 1,577 Joined: Dec 2013
RE: Programming puzzle: Longest list of regular numbers?
(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.
04-18-2017, 10:36 PM
Post: #26
 Claudio L. Senior Member Posts: 1,577 Joined: Dec 2013
RE: Programming puzzle: Longest list of regular numbers?
(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.
04-18-2017, 11:10 PM
Post: #27
 pier4r Senior Member Posts: 2,001 Joined: Nov 2014
RE: Programming puzzle: Longest list of regular numbers?
Impressive the new rpl, even faster than the prime

Wikis are great, Contribute :)
04-19-2017, 10:43 AM
Post: #28
 e_emil Junior Member Posts: 9 Joined: Mar 2017
RE: Programming puzzle: Longest list of regular numbers?
This convinced me to try out newRPL (just got myself a spare 50g)
04-19-2017, 03:09 PM (This post was last modified: 04-19-2017 03:27 PM by Claudio L..)
Post: #29
 Claudio L. Senior Member Posts: 1,577 Joined: Dec 2013
RE: Programming puzzle: Longest list of regular numbers?
(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.

Attached File(s)
04-19-2017, 04:06 PM (This post was last modified: 04-19-2017 04:06 PM by pier4r.)
Post: #30
 pier4r Senior Member Posts: 2,001 Joined: Nov 2014
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 :)
 « Next Oldest | Next Newest »

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