[math-fun] computer word sizes of 2^2^n
On 2016-07-06 07:13, Henry Baker wrote:
> Is it just me, or does anyone else find this property pretty cool:
>
> (%i1) x^256-1,factor;
> 2 4 8 16 32 64
128
> (%o1) (x - 1) (x + 1) (x + 1) (x + 1) (x + 1) (x + 1) (x + 1) (x
+ 1) (x + 1)
>
> I.e., the factors of 2^2^n-1 are (2^n-1) and (2^2^k+1) for k<n.
>
> This property has to be useful for some recursions on computer word
> sizes, but I don't recall Knuth using it anywhere.
>
> Is anyone aware of *any* interesting use of this property?
>
It has to be prominent in Knuth (+Graham+Patashnik): it's the generating
function of 1,1,1,1, ... and illustrates the uniqueness of binary notation:
In[1727]:= Product[1 + x^2^n, {n, 0, ∞}]
Out[1727]= 1/(1 - x)
Closely related:
In[1728]:= Product[Cos[t/2^n], {n, ∞}]
Out[1728]= Sinc[t]
--rwg
The analysis of Karatsuba's multiplication speedup recurses on
bisected word length. Or precision, anyway.
https://en.wikipedia.org/wiki/Anatoly_Karatsuba pictures him as
not the least Japanese, so the stress is on the TSU: Карацу́ба
* Bill Gosper <billgosper@gmail.com> [Jul 07. 2016 08:20]:
[...] The analysis of Karatsuba's multiplication speedup recurses on bisected word length. Or precision, anyway. https://en.wikipedia.org/wiki/Anatoly_Karatsuba pictures him as not the least Japanese, so the stress is on the TSU: Карацу́ба
About the Wikipedia page: "His eponymous algorithm is a fast procedure for multiplying large numbers, a divide and conquer algorithm later asymptotically improved by the Schönhage–Strassen algorithm which is based on Karatsuba's ideas and their development.[4][5]" I think the "which is based on" is misleading at least or plain wrong (IMO the latter). This references [5] his daughter with whom I had the misfortune to communicate. See the very end of (Richard Brent, Paul Zimmermann) http://maths-people.anu.edu.au/~brent/pub/pub226.html for what I refer as "misfortune": ------- Start ------- The FEE method of E. A. Karatsuba The reader may wonder why our book does not refer to the FEE method of E. A. Karatsuba. In fact, various drafts of Chapter 4 of the book did refer to this method, but our publisher (CUP) asked us to remove such references to avoid any possibility of legal problems. For brief comments on the FEE method, see for example the draft of the book that is available at arXiv:1004.4710. ------- End ------- If anyone on this list does edit Wikipedia, could this be corrected? Best regards, jj
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
About the Wikipedia page:
"His eponymous algorithm is a fast [...]
... no, "eponymous" is wrong here (as in 95% of its uses), the algorithm doesn't give its name to Karatsuba -- it's the other way round. Best, É. -----Message d'origine----- De : math-fun [mailto:math-fun-bounces@mailman.xmission.com] De la part de Joerg Arndt Envoyé : mardi 12 juillet 2016 15:53 À : math-fun <math-fun@mailman.xmission.com> Objet : Re: [math-fun] computer word sizes of 2^2^n * Bill Gosper <billgosper@gmail.com> [Jul 07. 2016 08:20]:
[...] The analysis of Karatsuba's multiplication speedup recurses on bisected word length. Or precision, anyway. https://en.wikipedia.org/wiki/Anatoly_Karatsuba pictures him as not the least Japanese, so the stress is on the TSU: Карацу́ба
About the Wikipedia page: "His eponymous algorithm is a fast procedure for multiplying large numbers, a divide and conquer algorithm later asymptotically improved by the Schönhage–Strassen algorithm which is based on Karatsuba's ideas and their development.[4][5]" I think the "which is based on" is misleading at least or plain wrong (IMO the latter). This references [5] his daughter with whom I had the misfortune to communicate. See the very end of (Richard Brent, Paul Zimmermann) http://maths-people.anu.edu.au/~brent/pub/pub226.html for what I refer as "misfortune": ------- Start ------- The FEE method of E. A. Karatsuba The reader may wonder why our book does not refer to the FEE method of E. A. Karatsuba. In fact, various drafts of Chapter 4 of the book did refer to this method, but our publisher (CUP) asked us to remove such references to avoid any possibility of legal problems. For brief comments on the FEE method, see for example the draft of the book that is available at arXiv:1004.4710. ------- End ------- If anyone on this list does edit Wikipedia, could this be corrected? Best regards, jj
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I think it's ambiguous whether the "which" (in "which is based on") was intended to modify the antecedent "procedure" (in "fast procedure") or the nearer antecedent "algorithm" (as in "Schonhage-Strassen algorithm"). But maybe those of you who know this story have background information that rules out the former possibility. Jim Propp On Tuesday, July 12, 2016, Eric Angelini <Eric.Angelini@kntv.be> wrote:
About the Wikipedia page:
"His eponymous algorithm is a fast [...]
... no, "eponymous" is wrong here (as in 95% of its uses), the algorithm doesn't give its name to Karatsuba -- it's the other way round.
Best, É.
-----Message d'origine----- De : math-fun [mailto:math-fun-bounces@mailman.xmission.com <javascript:;>] De la part de Joerg Arndt Envoyé : mardi 12 juillet 2016 15:53 À : math-fun <math-fun@mailman.xmission.com <javascript:;>> Objet : Re: [math-fun] computer word sizes of 2^2^n
* Bill Gosper <billgosper@gmail.com <javascript:;>> [Jul 07. 2016 08:20]:
[...] The analysis of Karatsuba's multiplication speedup recurses on bisected word length. Or precision, anyway. https://en.wikipedia.org/wiki/Anatoly_Karatsuba pictures him as not the least Japanese, so the stress is on the TSU: Карацу́ба
About the Wikipedia page:
"His eponymous algorithm is a fast procedure for multiplying large numbers, a divide and conquer algorithm later asymptotically improved by the Schönhage–Strassen algorithm which is based on Karatsuba's ideas and their development.[4][5]"
I think the "which is based on" is misleading at least or plain wrong (IMO the latter).
This references [5] his daughter with whom I had the misfortune to communicate.
See the very end of (Richard Brent, Paul Zimmermann) http://maths-people.anu.edu.au/~brent/pub/pub226.html for what I refer as "misfortune":
------- Start ------- The FEE method of E. A. Karatsuba
The reader may wonder why our book does not refer to the FEE method of E. A. Karatsuba. In fact, various drafts of Chapter 4 of the book did refer to this method, but our publisher (CUP) asked us to remove such references to avoid any possibility of legal problems. For brief comments on the FEE method, see for example the draft of the book that is available at arXiv:1004.4710. ------- End -------
If anyone on this list does edit Wikipedia, could this be corrected?
Best regards, jj
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (4)
-
Bill Gosper -
Eric Angelini -
James Propp -
Joerg Arndt