Timeline for The Knuth-Stolarsky conjecture in addition chains
Current License: CC BY-SA 4.0
17 events
when toggle format | what | by | license | comment | |
---|---|---|---|---|---|
S Sep 30, 2022 at 8:02 | history | bounty ended | CommunityBot | ||
S Sep 30, 2022 at 8:02 | history | notice removed | CommunityBot | ||
Sep 26, 2022 at 16:24 | history | edited | Neill Clift | CC BY-SA 4.0 |
added 356 characters in body
|
Sep 26, 2022 at 3:27 | comment | added | Neill Clift | The standard terminology for $j=k=i-1$ is a 'doubling'. If just $k<j=i-1$ then we call that a 'star step'. | |
Sep 25, 2022 at 4:22 | comment | added | domotorp | Schonhage uses a completely different definition of large/small steps: doi.org/10.1016/0304-3975(75)90008-0 He says that a step is large if $j=k=i-1$. Anyhow, I think that you should make your definition clear and self-contained in your question, and point out that others use different definitions. Linking to this bound on Wikipedia can also help people understand the problem: en.wikipedia.org/wiki/Addition_chain#Chain_length | |
Sep 24, 2022 at 12:31 | comment | added | Neill Clift | Each step in the chain can at most double the last element. So the most significant bit must start at zero $2^0=1$ and move one place at most with each step. Since the most significant bit of $n$ is fixed the number of large steps is fixed for a chain for $n$. The number of small steps can vary. For example $1, 2, 4$ is a chain for 4 with 0 small steps. $1,2,3,4$ is a non-optimal chain for 4 with 1 small step (between 2 and 3). | |
Sep 23, 2022 at 21:16 | comment | added | domotorp | I'm sorry, but I'm still not sure that I get it. A step is large if there is a 2-power between the two numbers? | |
Sep 23, 2022 at 18:23 | comment | added | Neill Clift | I didn't answer the second part of the question. I have some details here: additionchains.com. Basically, the Knuth-Stolarsky conjecture applies to all addition chains. Hence it applies to optimal (or shortest addition chains) since they have smaller small step counts than non-optimal chains. | |
Sep 23, 2022 at 18:16 | comment | added | Neill Clift | I have actually managed to enumerate all addition chains for numbers with 4 small steps (their actual formats rather than just the bit counts as described above). I have covered most of the five small step space (enough to know the bit counts of possible targets. Some details here: additionchains.com/SmallStepEnumeration.html | |
Sep 23, 2022 at 18:14 | comment | added | Neill Clift | We split steps in an addition chain into large (or big) steps and small steps. We have $\lambda(n)=\left\lfloor log_{2}(n)\right\rfloor$ as the number of large steps in a chain for $n$. Small steps have $\lambda(a_i)=\lambda(a_{i-1})$ and large steps have $\lambda(a_i)=\lambda(a_{i-1}) + 1$ | |
Sep 22, 2022 at 13:43 | comment | added | domotorp | What is the definition of a large/small step? Is the conjecture about EVERY addition chain of length $r(n)$, or just that there exists one that satisfies $v(n)\le 2^{s(n)}$? | |
Sep 22, 2022 at 8:47 | history | edited | YCor | CC BY-SA 4.0 |
formatting, added tag
|
S Sep 22, 2022 at 6:06 | history | bounty started | CommunityBot | ||
S Sep 22, 2022 at 6:06 | history | notice added | user482024 | Draw attention | |
S Sep 21, 2019 at 2:53 | history | suggested | CommunityBot | CC BY-SA 4.0 |
some MathJax copy-editing
|
Sep 21, 2019 at 1:54 | review | Suggested edits | |||
S Sep 21, 2019 at 2:53 | |||||
Sep 20, 2019 at 3:16 | history | asked | Neill Clift | CC BY-SA 4.0 |