MathGroup Archive 2008

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Re: Timing

  • To: mathgroup at smc.vnet.net
  • Subject: [mg88037] Re: [mg87971] Re: Timing
  • From: Carl Woll <carlw at wolfram.com>
  • Date: Tue, 22 Apr 2008 06:29:59 -0400 (EDT)
  • References: <480A0EE6.3090109@csl.pl> <200804211038.GAA28042@smc.vnet.net>

Artur wrote:

>Who know how change bellow procedure to received reasonable timing?
>
>Part:
>Expand[((3 + 2 Sqrt[2])^(2^(n - 1) - 1) - (3 - 2 Sqrt[2])^(2^(n - 1) - 
>1))/(4 Sqrt[2])]/(2^n - 1)
>is every time integer
>  
>
>>Timing[Do[ If[IntegerQ[Expand[((3 + 2 Sqrt[2])^(2^(n - 1) - 1) - (3 - 
>>2 Sqrt[2])^(2^(n - 1) - 1))/(4 Sqrt[2])]/(2^n - 1)],
>>  Print[n]], {n, 1, 17}]]
>>
>>    
>>
>I will be greatfull for any help! (Mayby some N[] or Floor[N[]]  or 
>Int[N[]] will be quickest
>
>Best wishes
>Artur
>  
>
You should review Fibonacci numbers and difference equations. Anyway, 
one can prove that

((3 + 2 Sqrt[2])^(2^(n - 1) - 1) - (3 - 2 Sqrt[2])^(2^(n - 1) -
1))/(4 Sqrt[2])

is an integer. Then notice:

In[166]:= 3 - 2 Sqrt[2] // N

Out[166]= 0.171573

As n gets larger, this term disappears. Therefore, all you need to do is:

f[n_] := Round[(3 + 2 Sqrt[2])^(2^(n-1)-1)/(4 Sqrt[2])]

Of course, the number of digits doubles every time, so on my computer 
things become very slow at f[23] (which is an integer with ~3.2 million 
digits).

So, you might want to experiment with recurrence relations (a la 
Fibonacci). This might allow you to incorporate the 2^n-1 denominator 
and keep things from blowing quite so quickly. For example, if

g[n_] := ((3 + 2 Sqrt[2])^n - (3 - 2 Sqrt[2])^n)/(4 Sqrt[2])

then (from the quadratic satisfied by 3 +/- 2 Sqrt[2]):

g[n+2] == 6 g[n+1] - g[n]
g[0]==0
g[1]==1

 From this one can see that:

{g[n+1], g[n]} == {{6, -1}, {1, 0}} . {g[n], g[n-1]}

or

MatrixPower[{{6, -1}, {1,0}}, n] == {{g[n+1], -g[n]}, {g[n], g[n-1]}}

etc.

Carl Woll
Wolfram Research


  • References:
  • Prev by Date: matrix of vectors - super slow
  • Next by Date: RE: Product
  • Previous by thread: Re: Re: Re: Re: Re: Timing
  • Next by thread: Re: Timing