Skip to main content
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