Re: Tough FACTORIAL math problem...

Article View: comp.lang.pascal.misc

Article #4

Back to comp.lang.pascal.misc Previous Next

From: Risto Lankinen
Date: Tue, 20 Feb 1996 07:17

32 lines
1772 bytes

Hi!

kcline@sun132.spd.dsccc.com (Kevin Cline) wrote:
>In article <4fr8be$ass@news.iconn.net>, The Crow <thecrow@iconn.net>
>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. ...

   [a suggested solution deleted]

>This solution runs in O(n).  With a bit more thought a log(n) solution
>is possible.

There is an algorithm that calculates the last non-zero _binary_ digit
of ANY factorial - with SUB-LOGARITHMIC time even in the worst case!!!

Mail me if interested but be prepared to explain what you need it for.
The algorithm is indeed very VERY fast, and so I don't want to give it
away without being credited at least.  Also, please mention "rightmost
non-zero binary digit algorithm" in your request.

terv: Risto

-- 
Risto Lankinen / System Engineer  ***************************************
Nokia Telecommunications,         *  2                              2   *
Cellular Data; Helsinki, Finland. * 2 -1 is PRIME!  Now working on 2 +1 *
risto.lankinen@ntc.nokia.com      ***************************************

Technical Details

Message-ID: <4gbsir$opr@axl02it.ntc.nokia.com>

Path: arc1-ca.pugleaf.net!ntc.nokia.com!usenet

References: <4fr8be$ass@news.iconn.net> <4g0giv$94s@sun132.spd.dsccc.com>

Show Full Headers

Complete Article Headers

Path: arc1-ca.pugleaf.net!ntc.nokia.com!usenet
From: Risto Lankinen <risto.lankinen@ntc.nokia.com>
Newsgroups: comp.lang.pascal.misc,comp.lang.c++,comp.lang.c,comp.lang.pascal.borland
Subject: Re: Tough FACTORIAL math problem...
Date: 20 Feb 1996 07:17:47 GMT
Organization: Nokia Telecommunications
Message-ID: <4gbsir$opr@axl02it.ntc.nokia.com>
References: <4fr8be$ass@news.iconn.net> <4g0giv$94s@sun132.spd.dsccc.com>
NNTP-Posting-Host: pc-rlankinen.ntc.nokia.com
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Mailer: Mozilla 1.2N (Windows; I; 16bit)

Reply to Parent Message