Talk:Addition-chain exponentiation: Difference between revisions
Content added Content deleted
m (→wikipedia content: Cannot call Wikipedia's template from here.) |
|||
| Line 115: | Line 115: | ||
::::::: I'm not sure why you think prime numbers are more troublesome than composites: if you are doing factorization, your method is doomed. Check the output for 77, none of the sequences contains either 7 or 11. --[[User:Ledrug|Ledrug]] 23:27, 27 August 2011 (UTC) |
::::::: I'm not sure why you think prime numbers are more troublesome than composites: if you are doing factorization, your method is doomed. Check the output for 77, none of the sequences contains either 7 or 11. --[[User:Ledrug|Ledrug]] 23:27, 27 August 2011 (UTC) |
||
:::::::: Yes, 33 was enough to show that factorization can be worse than addition chain (length binary chain for 3 + 1 + length binary chain 11 is longer than binary chain for 33). --[[User:Rdm|Rdm]] 02:32, 28 August 2011 (UTC) |
:::::::: Yes, 33 was enough to show that factorization can be worse than addition chain (length binary chain for 3 + 1 + length binary chain 11 is longer than binary chain for 33). --[[User:Rdm|Rdm]] 02:32, 28 August 2011 (UTC) |
||
Knuth's programs: [[http://www-cs-faculty.stanford.edu/~knuth/programs/achain4.w]] and [[http://www-cs-faculty.stanford.edu/~knuth/programs/achain-all.w]]. Pretty fast, but doesn't explain the algorithm very well, maybe because the algorithm only appears complicated to mere mortals. --[[User:Ledrug|Ledrug]] 20:59, 31 August 2011 (UTC) |
|||