🚀 go-pugleaf

thecrow@iconn.net (The Crow) wrote:
>
> Here is what I am trying to do, I want to find the last NON-ZERO digit of a 
> given factorial.  For instance,
> 
> 5! = 120
> 
> so the last non-zero digit is 2.  I want to be able to do this up to 1000.  
> Problem is, no matter how huge of a data-type you use, there isn't any way for 
> the computer to handle 1000!, it is however possible to find the last non-zero 
> digit somehow.  One thing I have tried is as I went through mulitplying the 
> series of numbers in the factorial (5 * 4 * 3 * 2) I would remove all the 
> trailing ZEROS, I got this to work up to 789, but it wont work with 1000 and i 
> am not really sure why.  If anyone has a clue how I can do this let me know.
> 
> -- 
> The Crow - thecrow@iconn.net
> "It can't rain all the time"
> -Kryptology
> 


Why not treat the numbers as strings.  There is a technique of
multiplying numbers using a table.

Imagine multiplying 7658 x 453.  Form a table 4 x 3.


 7  6  5  8
+----------+
|          | 4
|          | 5
|          | 3
+----------+  

Draw horizontal and vertical lines for each column and row.  Next draw
diagonal lines (/) between each sqaure.  Multiply each number (column
by row) and insert the answers in each half of each sqaure.

            6
e.g.,     +---+
          |1 /|
          | / | 3  
          |/ 8|
          +---+

When the table is complete you add the diagonal columns (from right
to left) putting the last digit under the corresponding column and
carry the remainder of the answer into the next column (to the left).
(if the total was 156 put a 6 under the column and add 15 to the next
diagonal on the left).

When you have finished adding the diagonal columns you will find the
answer from left to right around the table.

       5   6
     +---+---+
     |1 /|1 /|
   1 | / | / | 3  		The answer is 168.
     |/ 5|/8 |
     +-------+
       6   8


You could treat all your numbers as strings, muliply them by using
an array (or to save on memory you could evaluate each column as you
go.

I don't have any code handy.  If you want some Email me and I'll try
to find some time.  State whether you want to use an array or memory.
The memory version will probably be slower because as the numbers
grow it will be re-evaluating columns many times over.



Mal
mjsmith@mpx.com.au