last five non zero digit of 10^12!
mukesh tiwari
find last five non zero digits of very large number (upto
1,000,000,000,000) . plz help . one link i found on google groups
(http://groups.google.co.in/group/alt.math.recreational/browse_thread/
thread/b3e9f4fb09446ac/230aa5b8bbd3ad75?hl=en&lnk=st&q=last+non+zero
+digit+of+factorial&rnum=1#230aa5b8bbd3ad75)
is very helpful but this algorithm only gives last non zero digit .
can this algorithm applied for any digit of factorial. other problem
is that my numbers are very big so calculating A[1],A[2],A[3],A[4]
upto 10^12 will take lot of time as according to given method in post
so is there any direct way to calculate A{1],A[2],A[3],A[4].for
example 20! = 2432902008176640000 so last five non zero digit will be
17664
matt271...@yahoo.co.uk
wrote:
> hello everybody , i am trying to solve a problem in which i have to
> find last five non zero digits of very large number (upto
> 1,000,000,000,000) .
You mean the *factorial* of a very large number, right?
> plz help . one link i found on google groups
> (http://groups.google.co.in/group/alt.math.recreational/browse_thread/
> thread/b3e9f4fb09446ac/230aa5b8bbd3ad75?hl=en&lnk=st&q=last+non+zero
> +digit+of+factorial&rnum=1#230aa5b8bbd3ad75)
> is very helpful but this algorithm only gives last non zero digit .
> can this algorithm applied for any digit of factorial. other problem
> is that my numbers are very big so calculating A[1],A[2],A[3],A[4]
> upto 10^12 will take lot of time as according to given method in post
> so is there any direct way to calculate A{1],A[2],A[3],A[4].for
> example 20! = 2432902008176640000 so last five non zero digit will be
> 17664
Here's a suggestion. I think it's similar to the one made in the post
you reference, so acknowledgements to that author. Sorry this is
pretty hurried and garbled.
1. Calculate an array M of the count of the number of
"transformed" (see below) numbers between 1 and n (n being your large
number, whose factorial you want) that are equal to each possible
value mod 100000. So, M(1) is the number of transformed numbers that
are equal to 1 mod 100000, M(2) is the number of transformed numbers
that are equal to 2 mod 100000 etc.
2. The catch is in the "transformed" bit. For numbers divisible by 5
you need to keep dividing by 5 until it's no longer possible, and then
take the final result mod 100000, and add in to the appropriate
element of M.
3. As you're doing this you need to keep track of the number of times
you divide by 5, and then that many times find a number divisible by 2
and divide that by 2 before taking mod 100000 and adding to the
appropriate element of M.
4. But, I hear you say, counting through all the numbers from 1 to n
and doing all this stuff will take forever. BUT... and this is the
crucial bit ... I am fairly confident that with a modicum of ingenuity
you don't have to. You can calculate the counts in M (of which there
are merely 100000) *without* having to consider each number from 1 to
n separately, in O(100000) operations, or thereabouts.
5. Then, using some efficient modular exponentiation routine, you can
calculate the final answer as the product of over i of i^M(i) mod
100000 (without ever having to calculate any i^M(i) in full). This is
only 100000 operations, so should be quite feasible. This will give
you the last five non-zero digits (actually, one or more of these
might be zero of course... I mean the last five digits before the
trailing string of zeros).
matt271...@yahoo.co.uk
To satisfy myself that this can actually be made to work I knocked
together a program, which I have listed below for interest.
Theoretically it should work for any number of digits ("num_digits" in
the program; five in your case) and any n, but in practice there are a
couple of limitations.
The program, as written, requires that integer arithmetic can be
performed on numbers up to a size of 5*n or (10^num_digits)^2,
whichever is larger.
For larger n it looks that execution time is roughly proportional to
log(n)*10^num_digits. So, very insensitive to increasing n, but very
sensitive to increasing numbers of digits.
'------------------------------------------------------------------
Sub doit()
'initialise parameters
n = 1000000
num_digits = 4
pwr = 10 ^ num_digits
'populate mod_count array
'mod_count(i) is count of numbers equal to i mod pwr
ReDim mod_count(1 To pwr - 1)
For i = 1 To pwr - 1
mod_count(i) = n \ pwr
Next
For i = 1 To n Mod pwr
mod_count(i) = mod_count(i) + 1
Next
'remove factors of five
num_fives = 0
k = 5
While k * pwr <= n
num_fives = num_fives + n \ k
For i = 1 To pwr - 1
mod_count(i) = mod_count(i) + n \ (k * pwr)
Next
For i = 1 To (n Mod (k * pwr)) \ k
mod_count(i) = mod_count(i) + 1
Next
k = 5 * k
Wend
While k <= n
num_fives = num_fives + n \ k
For i = 1 To n \ k
mod_count(i) = mod_count(i) + 1
Next
k = 5 * k
Wend
'remove equivalent number of factors of two
block = 4 * pwr / 10
block_decrement = num_fives \ block
For i = 2 To pwr - 2 Step 2
If i Mod 5 <> 0 Then
mod_count(i) = mod_count(i) - block_decrement
mod_count(i / 2) = mod_count(i / 2) + block_decrement
End If
Next
leftover = num_fives Mod block
i = 2
While leftover > 0
If i Mod 5 <> 0 Then
mod_count(i) = mod_count(i) - 1
mod_count(i / 2) = mod_count(i / 2) + 1
leftover = leftover - 1
End If
i = i + 2
Wend
'do the modular exponentiation
last_digits = 1
For i = 1 To pwr - 1
If i Mod 5 <> 0 Then
last_digits = (last_digits * mod_exp(i, mod_count(i), pwr))
Mod pwr
End If
Next
Print last_digits
End Sub
'------------------------------------------------------------------
Function mod_exp(ByVal b, ByVal e, m) As Long
'calculate b^e mod m
mod_exp = 1
While e > 0
If e Mod 2 = 1 Then
mod_exp = (mod_exp * b) Mod m
End If
e = e \ 2
b = (b * b) Mod m
Wend
End Function
zdu
where T is the number of digits of n and k is the number of non-zero digit to calculate.
You could find more detail information in http://zdu.spaces.live.com/blog/cns!C95152CB25EF2037!125.entry
Tim Smith
mukesh tiwari <mukeshtiw...@gmail.com> wrote:
10^12 is only around 40 bits, which is small enough nowadays to make
brute force a possibility. Just multiply out 2, 3, ..., 10^12 mod
100000, but get rid of trailing zeros as you go, by first dividing out
any 5's from any of the factors before you include them in the modular
product, and similarly dividing out exactly one 2 for each 5 you divide
out.
You can calculate ahead of time how many 5's you need to take out:
[10^12/5] + [10^12/5^2] + ... + [10^12/5^17]
and so that is also the number of 2's you need to take out.
If you can process a factor in 100 ns, it would take just over a day to
brute force this. (100 ns is very generous...if you have a 64-bit
machine, you won't even need any kind of double precision integer
arithmetic, as 10^12 fits in a 64-bit integer).
--
--Tim Smith
Tim Smith
Tim Smith <reply_i...@mouse-potato.com> wrote:
> If you can process a factor in 100 ns, it would take just over a day to
> brute force this. (100 ns is very generous...if you have a 64-bit
> machine, you won't even need any kind of double precision integer
> arithmetic, as 10^12 fits in a 64-bit integer).
I just tried a straightforward Java implementation, with no
optimizations, and it takes about 110 ns per factor. A short time
optimizing would probably get it down to something that would run in a
few hours on a typical desktop PC.
--
--Tim Smith
zhao....@gmail.com
> In article <reply_in_group-CECFF6.11395414102...@news.supernews.com>,
> Tim Smith <reply_in_gr...@mouse-potato.com> wrote:
>
> > If you can process a factor in 100 ns, it would take just over a day to
> > brute force this. (100 ns is very generous...if you have a 64-bit
> > machine, you won't even need any kind of double precision integer
> > arithmetic, as 10^12 fits in a 64-bit integer).
>
> I just tried a straightforward Java implementation, with no
> optimizations, and it takes about 110 ns per factor. A short time
> optimizing would probably get it down to something that would run in a
> few hours on a typical desktop PC.
>
> --
> --Tim Smith
It is too slow.
My algorithm could calculate the last 18 non-zero digits of (10000!)!
is 534459594029924352 in 1.64 seconds; and the last 18 non-zero digits
of (10^10000-1)! is 979819424592166912 in 0.14 seconds.