\ Article: 135919 of comp.lang.forth \ Path: tunews.univie.ac.at!aconews-feed.univie.ac.at!newsfeed.wu-wien.ac.at!newsfeed.utanet.at!news.germany.com!news.space.net!news.m-online.net!annette.mikron.de!news \ From: Bernd Paysan \ Newsgroups: comp.lang.forth \ Subject: Re: Euler problem #48 \ Date: Thu, 08 May 2008 11:22:15 +0200 \ Organization: (posted via) M-net Telekommunikations GmbH \ Lines: 38 \ Message-ID: <7btaf5-ir.ln1@annette.mikron.de> \ References: <88003316183559@frunobulax.edu> \ NNTP-Posting-Host: mail.mikron.de \ Mime-Version: 1.0 \ Content-Type: text/plain; charset=us-ascii \ Content-Transfer-Encoding: 7Bit \ X-Trace: svr7.m-online.net 1210239001 30096 62.245.145.34 (8 May 2008 09:30:01 GMT) \ X-Complaints-To: abuse@m-online.net \ NNTP-Posting-Date: Thu, 8 May 2008 09:30:01 +0000 (UTC) \ User-Agent: KNode/0.10.4 \ Xref: tunews.univie.ac.at comp.lang.forth:135919 \ Marcel Hendrix wrote: \ > INCLUDE ../bignum/factor.frt \ If you have a 64 bit Forth (and I know you have ;-), you don't need bignums \ for that. All intermediate results have at most 20 digits, and therefore \ easily fit in a 128 bit number; the sum with at most 13 digits fits in a 64 \ bit number. This one should be faster (how much depends on how efficient \ your gs^mod actually is). In Gforth with a 2GHz Athlon64, it takes about \ 1.5ms to run 1000t. I guess iForth64 should do it in less than 1ms, even \ when the division for the modulus might be the limiting factor. \ sum of the last 10 digits of n^n for n=1..1000 Cell 8 < [IF] .( Needs a 64 bit Forth!) cr true abort [THEN] &10000000000 Constant mod# : *mod ( a b -- c ) um* mod# um/mod drop ; : **mod ( x n -- n ) >r 1 swap BEGIN r@ 1 and IF tuck *mod swap THEN r> 2/ dup WHILE >r dup *mod REPEAT 2drop ; : e48 ( n -- g ) 0 swap 1+ 1 DO I dup **mod + LOOP mod# mod ; : Euler48 ( -- ) CR ." The last ten digits of the series " ." 1^1 + 2^2 + 3^3 + ... + 1000^1000 are " 1000 e48 . cr ; \ -- \ Bernd Paysan \ "If you want it done right, you have to do it yourself" \ http://www.jwdt.com/~paysan/