Re: IMPORTANT Re: Zero digits in powers




On 23/06/2005 02:06, vkarlamov@xxxxxxxxx wrote:

> Jean-Claude Arbaut wrote:
>>
>> You need to carry N digits for all computations
>>
>
> What is N?
>

An integer, this time ;-)


For example, 2^20 = 1048576, in your favorite programming language you
define an array of integers of size N. Usually for this problem I use N>200.

Let's call A this array, with members a_1 ... a_N.

You set a_1=6, a_2=7, etc. so your array looks like

[ 6 7 5 8 4 0 1 0 0 0 0 0 ... ]

This array may represent the last N decimal digits of any number, here of
numbers of the form 2^k.

You find "0" digits with a loop thru the array, but stopping at the last
digit (here it's a "1"). You must keep track of this last digit's index.
For k large enough, though, the whole array is significant (there are no
extra "0" digits to take into account).

Now, you have 2^20 and want to compute 2^21, you just do as when you compute
by hand, that is, you multiply digits by two from left to right, while
taking the carry into account.

Here you first do 6 + 6 = 12 = 10 + 2

[ 2 7 5 8 4 0 1 ], carry = 1

Then 7 + 7 + 1 = 15 = 10 + 5

[ 2 5 5 8 4 0 1 ], carry = 1

[ 2 5 1 8 4 0 1 ], carry = 1

[ 2 5 1 7 4 0 1 ], carry = 1

[ 2 5 1 7 9 0 1 ], carry = 0

[ 2 5 1 7 9 0 1 ], carry = 0

[ 2 5 1 7 9 0 2 ], carry = 0


So 2^21 = 2097152.

If the carry = 1 at the end ot the loop, you must increment the last digit's
index, and set the new digit to 1, except if you are already at the end of
the array A, in which case you just forget the carry (it would modify a
digit you don't care).

There may be faster algorithms (for instance representing numbers in base
100 or 1000 or higher instead of 10), but I am already happy with this one:
very easy, and very fast.




If you want to compute n^40, it's a bit more complex.
Given a series a(n), compute differences

D(a)(n) = a(n+1) - a(n)
D^2(a)(n) = D(a)(n+1) - D(a)(n)
D^k(a)(n) = D^(k-1)(n+1) - D^(k-1)(n)

Then b(n) defined by b(n) = D^n(a)(0) is called the binomial transform of
a(n), but here it's not very interesting. What *is* interesting is the fact
that if a(n) is a polynomial of degree p, then D(a) is a polynomial of
degree p-1, etc. And D^p is a constant.

It's not very difficult to derive an algorithm to compute n^40 with only
additions from the preceding fact. You just need to maintain 40 numbers, so
40 arrays like the one in the preceding algo. And to initialize you use the
binomial transform b(n) of a(n)=n^40, which satisfies b(n) = 0 for n > 40.
You only need the 40 first terms, with which you initialize your 40 numbers.

If you are interested, the binomial transform has many great properties, for
example it has an inverse transform, which is almost the binomial transform
itself! It can also be written as
b(n) = (-1)^n*sum((-1)^k*binom(n,k)*a(k),k=0..n)
a(n) = sum(binom(n,k)*b(k),k=0..n)
and since the binomial transform of a polynomial is zero apart few values,
it can be used to identify many sequences. Some series have a simple
transform: Bell numbers, Bernoulli numbers, etc.

.