New subject: [math-fun] computer word sizes of 2^2^n

6 Jul 2016

      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:  Карацу́ба

[math-fun] computer word sizes of 2^2^n

Bill Gosper

Joerg Arndt

Eric Angelini

James Propp

tags

participants (4)