Re: Interesting question

On Dec 24, 8:47 am, vr <simple.pop...@xxxxxxxxx> wrote:
On Dec 24, 5:19 pm, John <iamach...@xxxxxxxxx> wrote:

Question Write a program that can compute the last non-zero digit of
any factorial for ( 0 <= N <= 10000). For example, if your program is
asked to compute the last nonzero digit of 5!, your program should
produce 2.

Now give a generalized method to find the last X non-zero digits of N
factorial

Strategy:

* start with an inital value for the answer as 1.
* write a for loop to iterate over decimal digits 1-9
* multiply the answer the digit and store the last digit back in
answer. If the last digit is 0 then find the one before it and store
it in answer.

You need to store the last 2 digits, since when you need to remove a
trailing 0 (only happens when multiplying by 5), the tens digit's
parity will have an effect. (e.g.: if the digit is 2, then is 5 times
that going to give you a 1 or a 6?

For that matter, when multiplying by a multiple of 25, the hundreds'
digit is important. And when multiplying by 125, the thousands' digit,
&c.

Since we want 0<=n<=10000, we need to worry about multiples of 625,
and 3125. Thus, you need to keep 7 digits. In general, for arbitrary
n, you need to keep at least log_5(N) +1 digits.


There is still the problem with multiples of 10. for example, when
multiplying by 20, the effect will be the same as multiplying by 2.
You cannot skip them.

From a programming standpoint, for 1<=n<=10000, I would simply loop 1
to 10000, and trim trailing zeroes after the multiplication, and
keeping the next 7 digits (for the powers of 5 problem listed above)
.

Relevant Pages

  • Re: Myth about mathematicians and mental arithmetic
    ... I think mathematicians are more likely than normal ... The cube root of 32768 is of course 32. ... way easier than multiplying two 3 digit numbers together in your head. ...
    (sci.math)
  • Re: How do I hash this?
    ... I got some primary key failures which would indicate matching keys. ... So your hash value could be x * 6320 ... less than y but I'm not sure why multiplying by 79 * 80 makes it ... They are the possible permutations with 1 digit. ...
    (comp.programming)
  • Re: Converting base 255->256 and vice versa
    ... that you only need to be able to multiply by 255 and add a single digit. ... Use the normal hand multiply technique for multiplying by 255, ... saving the lower digit of the product and carrying the higher digit. ... keeping the lower order digit and carrying the high order ...
    (comp.programming)
  • Re: Converting base 255->256 and vice versa
    ... that you only need to be able to multiply by 255 and add a single digit. ... Use the normal hand multiply technique for multiplying by 255, ... Basically, you repeatedly subtract x/256 from x, but only the leftmost ... You all think I'm paranoid, ...
    (comp.programming)
  • Re: Interesting question
    ... asked to compute the last nonzero digit of 5!, ... If the last digit is 0 then find the one before it and store ... For that matter, when multiplying by a multiple of 25, the hundreds' ...
    (sci.math)