Takebe Katahiro
(1664  1739)
A beautiful algorithm
Bit's of his life
This name probably does not ring a bell for
most people because Takebe Katahiro was a japanese mathematician, which
was not common, especially at that time. Born in 1664
from a samourai familly, the mutation of a still feudal Japan could
only encourage Takebe to complete a samourai formation that was very
incomplete..... very quickly he follows the teaching of Seki Takakazu (?
 1708),
the most brilliant mathematician of Japan!
The mathematicians of this country did not know of the occidental
science. Using littles sticks instead of numbers and without
trigonometry (!), Seki and his disciple will build a new science in
Japan, developping algebra and analysis. Takebe dies in 1739.
Around :
Takebe is interested in Pi,
and even calculate 41 decimals using the Archimede method and a
polygon with 1024
sides, which is very a,azing considering the numerical system used !
This does not stop Takebe to offer us a very interesting formula, since
our japanese friend is the first to have expressed the square of a
circle arc in the from of an inifite sum in his Classique de
Tetsujutsu (1722) .
The proofs were not rigourous back then (unfortunatly!), we only have
the numerical method that he used to get his formula...
We easily get out of it an algorithm with modern notation then a sum
with very interesting performance. Since I could not find anywhere a
proof, I looked myself and found one that is not hard, but I'm still
looking for a more elegant method!
Proof
Let f(u)= and U_{n}=. We get :
hence from Alembert's critiria,
the serie converges for u<1.
(In passing, with the formula Moivre/Stirling,
we can easily show that the serie does not converge for u=1)
The function being even, it is therefore defined on (1,1).
We are going to find the exacte expression of f by a classical
procedure but that can be classsified as "brute force, typical of first
years"!
Let's look for the differential equation that satisfies f !
We have :
so calculate for u[0,1) :
hence y=f(u) satisfy :
Integrate between 0 and x(0,1) :
but, y'(0)=0 (u=0 in the power serie of the limit f'(u))
so we integrate once more :
Finnaly for r>1 : take U_{0}=4. We have :
which brings an end to the proof! It goes without further saying that
the two forms of U_{n} are easily deduced one and the
other from imediate recurrence(so immediate that I'm not even going to
write it down!)
Trials
Not only the formula is quite beutiful
but it's performance is far from rubish! It is quite evident from the
ratio form that the convergence is linear.
= in our case here. This means with large
enough n, the sequence U_{n} nearly behave like
a geometric serie of ratio . Moivre/Stirling
equivalence gives us furthermore :
whoes convergence is a little bit faster than the linear convergence...
Theoretically, we can even construct thanks to the different values of
r convergant sequences nearly linear as fast as we can!
Let's check all of this with small trials (for r=2) :
n=1 
3,055050 
n=5 
3,1399 (1) 
n=10 
3,141568 (4) 
n=20 
3,141592643 (7) 
n=50 
17 correct
decimals 
n=100 
33 correct
decimals

n=200 
64 correct
decimals

which gives us a convergence of around n / 3, not too bas...
Now for r=3 :
n=5 
3,14157 (4) 
n=10 
3,141592644 (7) 
n=50 
33 correct
decimals

n=100 
63 correct
decimals

Convergence of roughly 2n/3
And then for r=6 :
n=5 
3,141592646 (7) 
n=10 
13 correct
decimals 
n=50 
61 correct
decimals

Convergence 1.2n ?
Finnaly for a bit of fun, r=12
n=5 
11 correct
decimals

n=10 
20 correct
decimals

n=50 
92 correct
decimals

We start flirting with a convergence of 2n, but it's surprising
that the convergence seems to slow down when she should be a but better
than the linear convergence....
You should notice that for r=2 or r=3, we get a series
of rational that only needs an extraction of a root at the end,
interesting!
Acceleration of convergence
As always with linear convergence
(that is sequences that resemble more and more to a geometric
sequence), the Delta2 of Aitken
shoulf be terribly efficiant. But it's a bit deceiving....
For r=2 :

Without Aitken 
With Aitken 
n=2 
3,112 (1) 
3,132 (1) 
n=5 
3,1399 (1) 
3,141428 (3) 
n=10 
3,141568 (4) 
3,14159179 (5) 
n=20 
3,141592643 (7) 
3,141592653479 (9) 
n=50 
17 correct
decimals

19 correct
decimals

n=100 
33 correct
decimals

35 correct
decimals

n=200 
64 correct
decimals

66 correct
decimals

no need to carry on further with the demonstration, the Delta2
only adds 2 more decimals to the result, which is not very
conclusive!
For r=6
n=5 
3,141592646 (7) 
3,14159265325 (9) 
n=10 
13 correct
decimals 
15 correct
decimals 
n=50 
61 correct
decimals 
65 correct
decimals

Just a bit better, even if there 4 more decimals for n=50,
this start to be become a bit more interesting. I can unfortunatly not
push the calculation firther for the moment...
back to home page 