Main Page: Difference between revisions

From formulasearchengine
Jump to navigation Jump to search
← Older edit
No edit summary
No edit summary
 
(471 intermediate revisions by more than 100 users not shown)
Line 1: Line 1:
In [[mathematics]], an '''addition chain''' for computing a positive integer ''n'' can be given by a [[sequence]] of [[natural number]]s ''v'' and a sequence of index pairs ''w'' such that each term in ''v'' is the sum of two previous terms, the indices of those terms being specified by ''w'':
This is a preview for the new '''MathML rendering mode''' (with SVG fallback), which is availble in production for registered users.


: ''v'' =(''v''<sub>0</sub>,...,''v''<sub>''s''</sub>), with ''v''<sub>0</sub> = 1  and ''v''<sub>''s''</sub> = ''n''
If you would like use the '''MathML''' rendering mode, you need a wikipedia user account that can be registered here [[https://en.wikipedia.org/wiki/Special:UserLogin/signup]]
:for each 0< ''i'' ≤ ''s'' holds: ''v''<sub>''i''</sub> = ''v''<sub>''j''</sub> + ''v''<sub>''k''</sub>, with ''w''<sub>''i''</sub>=(''j,k'') and 0 ≤ ''j,k'' ≤  ''i''&nbsp;−&nbsp;1
* Only registered users will be able to execute this rendering mode.
* Note: you need not enter a email address (nor any other private information). Please do not use a password that you use elsewhere.


Often only ''v'' is given since it is easy to extract ''w'' from ''v'', but sometimes ''w'' is not uniquely reconstructible. An introduction is given in.<ref>D. E. Knuth, ''The Art of Computer Programming'', Vol 2, "Seminumerical Algorithms", Section 4.6.3, 3rd edition, 1997</ref>
Registered users will be able to choose between the following three rendering modes:


==Examples==
'''MathML'''
As an example: ''v'' = (1,2,3,6,12,24,30,31) is an addition chain for 31 of length 7, since
:<math forcemathmode="mathml">E=mc^2</math>
:2 = 1 + 1
:3 = 2 + 1
:6 = 3 + 3
:12 = 6 + 6
:24 = 12 + 12
:30 = 24 + 6
:31 = 30 + 1


Addition chains can be used for [[addition-chain exponentiation]]: so for example we only need 7 [[multiplication]]s to calculate 5<sup>31</sup>:
<!--'''PNG'''  (currently default in production)
:5<sup>2</sup> = 5<sup>1</sup> × 5<sup>1</sup>
:<math forcemathmode="png">E=mc^2</math>
:5<sup>3</sup> = 5<sup>2</sup> × 5<sup>1</sup>
:5<sup>6</sup> = 5<sup>3</sup> × 5<sup>3</sup>
:5<sup>12</sup> = 5<sup>6</sup> × 5<sup>6</sup>
:5<sup>24</sup> = 5<sup>12</sup> × 5<sup>12</sup>
:5<sup>30</sup> = 5<sup>24</sup> × 5<sup>6</sup>
:5<sup>31</sup> = 5<sup>30</sup> × 5<sup>1</sup>


==Methods for computing addition chains==
'''source'''
Calculating an addition chain of minimal length is not easy; a generalized version of the problem, in which one must find a chain that simultaneously forms each of a sequence of values, is NP-complete.<ref>{{Cite journal|first1=Peter|last1=Downey|first2=Benton|last2=Leong|first3=Ravi|last3=Sethi|title=Computing sequences with addition chains|journal=SIAM Journal on Computing|volume=10|issue=3|year=1981|pages=638–646|doi=10.1137/0210047}}. A number of other papers state that finding a single addition chain is NP-complete, citing this paper, but it does not claim or prove such a result.</ref> There is no known algorithm which can calculate a minimal addition chain for a given number with any guarantees of reasonable timing or small memory usage. However, several techniques to calculate relatively short chains exist.
:<math forcemathmode="source">E=mc^2</math> -->
One very well known technique to calculate relatively short addition chains is the ''binary method'', similar to [[exponentiation by squaring]]. Other well-known methods are the ''factor method'' and ''window method''.{{Citation needed|date=December 2009}}


==Chain length==
<span style="color: red">Follow this [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering link] to change your Math rendering settings.</span> You can also add a [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering-skin Custom CSS] to force the MathML/SVG rendering or select different font families. See [https://www.mediawiki.org/wiki/Extension:Math#CSS_for_the_MathML_with_SVG_fallback_mode these examples].
Let <math>l(n)</math> denote the smallest ''s'' so that there exists an addition chain
of length ''s'' which computes ''n''.
It is known that <ref>A. Schonhage A lower bound on the length of addition chains, Theoret. Comput. Sci. 1 (1975), 1–12.</ref>
:<math>\log(n)+ \log(\nu(n))-2.13\leq l(n) \leq \log(n) + \log(n)(1+o(1))/\log(\log(n))</math>,
where <math>\nu(n)</math> is [[Hamming weight]] of binary expansion of ''n''.


It is clear that ''l''(2''n'') ≤ ''l''(''n'')+1.  Strict inequality is possible, as ''l''(382) = ''l''(191) = 11, observed by Knuth.<ref name=G169/>
==Demos==


==Brauer chain==
Here are some [https://commons.wikimedia.org/w/index.php?title=Special:ListFiles/Frederic.wang demos]:
A '''Brauer chain''' or '''star addition chain''' is an addition chain in which one of the summands is always the previous chain: that is,


:for each ''k''>0: ''a''<sub>''k''</sub> = ''a''<sub>''k-1''</sub> + ''a''<sub>''j''</sub> for some ''j'' < ''k''.


A '''Brauer number''' is one for which the Brauer chain is minimal.<ref name=G169/>
* accessibility:
** Safari + VoiceOver: [https://commons.wikimedia.org/wiki/File:VoiceOver-Mac-Safari.ogv video only], [[File:Voiceover-mathml-example-1.wav|thumb|Voiceover-mathml-example-1]], [[File:Voiceover-mathml-example-2.wav|thumb|Voiceover-mathml-example-2]], [[File:Voiceover-mathml-example-3.wav|thumb|Voiceover-mathml-example-3]], [[File:Voiceover-mathml-example-4.wav|thumb|Voiceover-mathml-example-4]], [[File:Voiceover-mathml-example-5.wav|thumb|Voiceover-mathml-example-5]], [[File:Voiceover-mathml-example-6.wav|thumb|Voiceover-mathml-example-6]], [[File:Voiceover-mathml-example-7.wav|thumb|Voiceover-mathml-example-7]]
** [https://commons.wikimedia.org/wiki/File:MathPlayer-Audio-Windows7-InternetExplorer.ogg Internet Explorer + MathPlayer (audio)]
** [https://commons.wikimedia.org/wiki/File:MathPlayer-SynchronizedHighlighting-WIndows7-InternetExplorer.png Internet Explorer + MathPlayer (synchronized highlighting)]
** [https://commons.wikimedia.org/wiki/File:MathPlayer-Braille-Windows7-InternetExplorer.png Internet Explorer + MathPlayer (braille)]
** NVDA+MathPlayer: [[File:Nvda-mathml-example-1.wav|thumb|Nvda-mathml-example-1]], [[File:Nvda-mathml-example-2.wav|thumb|Nvda-mathml-example-2]], [[File:Nvda-mathml-example-3.wav|thumb|Nvda-mathml-example-3]], [[File:Nvda-mathml-example-4.wav|thumb|Nvda-mathml-example-4]], [[File:Nvda-mathml-example-5.wav|thumb|Nvda-mathml-example-5]], [[File:Nvda-mathml-example-6.wav|thumb|Nvda-mathml-example-6]], [[File:Nvda-mathml-example-7.wav|thumb|Nvda-mathml-example-7]].
** Orca: There is ongoing work, but no support at all at the moment [[File:Orca-mathml-example-1.wav|thumb|Orca-mathml-example-1]], [[File:Orca-mathml-example-2.wav|thumb|Orca-mathml-example-2]], [[File:Orca-mathml-example-3.wav|thumb|Orca-mathml-example-3]], [[File:Orca-mathml-example-4.wav|thumb|Orca-mathml-example-4]], [[File:Orca-mathml-example-5.wav|thumb|Orca-mathml-example-5]], [[File:Orca-mathml-example-6.wav|thumb|Orca-mathml-example-6]], [[File:Orca-mathml-example-7.wav|thumb|Orca-mathml-example-7]].
** From our testing, ChromeVox and JAWS are not able to read the formulas generated by the MathML mode.


Brauer proved that
==Test pages ==
:''l''*(2<sup>''n''</sup>&minus;1) &le; ''n'' &minus; 1 + ''l''*(''n'')
where ''l''* is the length of the shortest star chain.  For many values of ''n'',and in particular for ''n''&nbsp;≤&nbsp;2500, they are equal: ''l''(''n'')&nbsp;=&nbsp;''l''*(''n''). But Hansen showed that there are some values of ''n'' for which ''l''(''n'')&nbsp;≠&nbsp;''l''*(''n''), such as ''n''&nbsp;=&nbsp;2<sup>6106</sup>&nbsp;+&nbsp;2<sup>3048</sup>&nbsp;+&nbsp;2<sup>2032</sup>&nbsp;+&nbsp;2<sup>2016</sup>&nbsp;+&nbsp;1 which has ''l''*(''n'')&nbsp;=&nbsp;6110, ''l''(''n'')&nbsp;≤&nbsp;6109.


==Scholz conjecture==
To test the '''MathML''', '''PNG''', and '''source''' rendering modes, please go to one of the following test pages:
{{main|Scholz conjecture}}
*[[Displaystyle]]
The [[Scholz conjecture]] (sometimes called the ''Scholz–Brauer'' or ''Brauer–Scholz conjecture''), named after [[A. Scholz]] and Alfred T. Brauer), is a [[conjecture]] from 1937 stating that
*[[MathAxisAlignment]]
:''l''(2<sup>''n''</sup>&nbsp;&minus;&nbsp;1)&nbsp;&le;&nbsp;''n''&nbsp;&minus;&nbsp;1&nbsp;+&nbsp;''l''(''n'') .
*[[Styling]]
*[[Linebreaking]]
*[[Unique Ids]]
*[[Help:Formula]]


N. Clift checked this by computer for&nbsp;''n''&nbsp;≤&nbsp;46.  It is known to be true for Brauer numbers.<ref name=G169>Guy (2004) p.169</ref>
*[[Inputtypes|Inputtypes (private Wikis only)]]
 
*[[Url2Image|Url2Image (private Wikis only)]]
==See also==
==Bug reporting==
* [[Addition chain exponentiation]]
If you find any bugs, please report them at [https://bugzilla.wikimedia.org/enter_bug.cgi?product=MediaWiki%20extensions&component=Math&version=master&short_desc=Math-preview%20rendering%20problem Bugzilla], or write an email to math_bugs (at) ckurs (dot) de .
* [[Addition-subtraction chain]]
* [[Vectorial addition chain]]
* [[Lucas chain]]
 
==References==
{{reflist}}
*{{cite journal | last1=Brauer | first1=Alfred | title=On addition chains | doi=10.1090/S0002-9904-1939-07068-7  | mr=0000245  | year=1939 | journal=[[Bulletin of the American Mathematical Society]] | issn=0002-9904 | volume=45 | issue=10 | pages=736–739}}
* {{cite book|author=Richard K. Guy|authorlink=Richard K. Guy|title=[[Unsolved Problems in Number Theory]]|publisher=[[Springer-Verlag]]|year=2004|isbn=0-387-20860-7|oclc=54611248 | zbl=1058.11001}}  Section C6.
 
== External links ==
* http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html
* {{SloanesRef |sequencenumber=A003313|name=Length of shortest addition chain for n}}
*[http://www.numdam.org/item?id=JTNB_1994__6_1_21_0 F. Bergeron, J. Berstel. S. Brlek "Efficient computation of addition chains"]
 
{{DEFAULTSORT:Addition Chain}}
[[Category:Addition chains|*]]
 
[[es:Suma encadenada]]

Latest revision as of 23:52, 15 September 2019

This is a preview for the new MathML rendering mode (with SVG fallback), which is availble in production for registered users.

If you would like use the MathML rendering mode, you need a wikipedia user account that can be registered here [[1]]

  • Only registered users will be able to execute this rendering mode.
  • Note: you need not enter a email address (nor any other private information). Please do not use a password that you use elsewhere.

Registered users will be able to choose between the following three rendering modes:

MathML


Follow this link to change your Math rendering settings. You can also add a Custom CSS to force the MathML/SVG rendering or select different font families. See these examples.

Demos

Here are some demos:


Test pages

To test the MathML, PNG, and source rendering modes, please go to one of the following test pages:

Bug reporting

If you find any bugs, please report them at Bugzilla, or write an email to math_bugs (at) ckurs (dot) de .

Retrieved from "https://en.formulasearchengine.com/index.php?title=Main_Page&oldid=329754"