User talk:WillNess: Difference between revisions
Content added Content deleted
(→Space complexity improvement -- Hamming numbers: speedup suggestions) |
|||
| Line 59: | Line 59: | ||
: Hi, thanks for the explanations, and for spotting that naming error. The code now runs as is, http://ideone.com/GXh4P0. It is about 30% slower than foldl' version, indeed. As for n<=0, it is invalid input. ''n'' is expected to be 1-based. Probably will have to edit this all in, yes. :) -- [[User:WillNess|WillNess]] ([[User talk:WillNess|talk]]) 13:18, 19 August 2016 (UTC) |
: Hi, thanks for the explanations, and for spotting that naming error. The code now runs as is, http://ideone.com/GXh4P0. It is about 30% slower than foldl' version, indeed. As for n<=0, it is invalid input. ''n'' is expected to be 1-based. Probably will have to edit this all in, yes. :) -- [[User:WillNess|WillNess]] ([[User talk:WillNess|talk]]) 13:18, 19 August 2016 (UTC) |
||
: I've now re-coded foldl' as loops too and got essentially same timings as your entry on Ideone (about 20% speedup; won't edit it in, to keep the clarity of the current version). But, there is still potential for improvement: the k-j enumeration is easily parallelizable: partition the `k`s such that k-j triangle is divided into 4 (8, ...) strips of roughly equal areas, and process each bundle in parallel. Another, really vague idea I once had, can be seen [http://stackoverflow.com/questions/10126285/generating-integers-in-ascending-order-using-a-set-of-prime-numbers/10160054#comment15193650_10126894 here], but it's really vague. :) -- [[User:WillNess|WillNess]] ([[User talk:WillNess|talk]]) 11:07, 20 August 2016 (UTC) |
|||