Jump to content

Talk:Addition chains

From Rosetta Code

Is this related to Addition-chain_exponentiation? If so, should we consider the difficulties mentioned on the talk page there? (Do we want tasks which might require months or years of computation time to complete where the alternative is basically to hardcode a specific list of constants?) --Rdm (talk) 18:47, 28 January 2016 (UTC)

This task is more or less related to Addition-chain_exponentiation. The difference is that is asks to count a number of optimal solutions. It can be, and has be solved (brute force or other method) for all the required numbers in less than a few seconds. No hardcode alternative. The extra-credit task may require more time for the number 12509 (It has been solved by Knuth). In summary : no mega-years involved in this task, only clever or not-clever algorithmic solution. OEIS has published solutions up to n = 1000. Anyway, it is only a proposal. --G.Brougnard (talk) 19:46, 28 January 2016 (UTC)

Cookies help us deliver our services. By using our services, you agree to our use of cookies.