European Experts Exchange (EEE.org) :: Free Experts PHP MySql Oracle Microsoft Web SQL Delphi


Algorithms :: Maths :: Factorial question
By: omuyelijah	Date: 05/11/2007 16:28:22	Points: 20	Status: Answered Quality : Excellent
Hello, How do I reckon the last non-zero digit of the factorial of 10,000 using C or C++? Thanks.
By: VGR	Date: 09/11/2007 21:55:31		Type : Comment
2!=2 lnzd = 2 (23=6, keep 6) 3!=6 lnzd = 6 (ok, 64=24, keep 4) 4!=24 lnzd = 4 (ok, 45=20, keep 2) 5!=120 lnzd = 2 (ok, 26=12, keep 2) 6!=720 lnzd = 2 (ok, 27=14, keep 4) 7!=5040 lnzd = 4 (ok, 48=32 keep 2) 8!=40320 lnzd = 2 (ok, 29=18 so next lnzd is probably 8) 9!=362880 lnzd = 8 (ok) I think I found the rule ;-)) lnzd=1; // this is 1! or 0! for (i=1;i<10001;i++) { lnzd2=lnzdi; while lnzd2 is a multiple of 10, divide by ten lnzd=last character of lnzd2 } print out lnzd

By: omuyelijah	Date: 28/12/2007 16:52:21		Type : Comment
I think I did not put the question well. Sorry. Now ur solution is correct but getting beyound i=25, u notice that you can't print the resulting factorial as a result of memory concerns. This is the problem. I recoded in .NET C++, trying out Int64 and double but they had their limits. My aim is to get the factorial all the way. The only programming language that has helped out so far is Java (using BIGINT). Why should c++ be difficult?

By: VGR	Date: 29/12/2007 13:45:57		Type : Assist
you'll always encounter a capacity problem, whatever the actual datatype you use. The best (the one with the actual maximum range) is either an "unsigned big integer" (in Pascal/Delphi it's a LongWord, 32 bits) or an IEEE Extended precision float/real (again, Turbo-Pascal was the only language offering a datatype to map to that internal format of the 80x87 coprocessor : it's an Extended ; other languages (C, C++) just offered Double ) Extended precision can range from 10^-4952 to 10^4957 (from memory), and LongWord goes up to 2^32-1 wich is around 4T, again from memory. When I was a student in mathematical computing, I found that it was enough to use the Stirling Formula to compute the factorial of numbers up to hundreds of powers of ten. The precision of the formula for N! improves with N, and the worst is thus for 0! where the error is 7% : from memory, the formula would output 0.93 in stead of 1 This will not help you with your problem but it's good to know about the factorial function IMHO ; you'll have to modify your computation to compute differently whilst maintaining absolute precision. It should be feasible. Using Dot.Net will NOT help you. It's as limited as other languages. If you run on a 64 bits platform, you can get precision from 10^-63 to 10^64-1 but this only repushes the limitation a little bit farther (remember the factorial is... exponential) good luck

By: omuyelijah	Date: 04/01/2008 20:02:09		Type : Comment
Well, like U had hinted, i'll switch to a better algorithm that will not raise memory concerns and report back as soon as completed. Less I 4get, I wanna say HAPPY NEW YEAR TO YOU, ALL MODERATORS AND MEMBERS OF THIS GREAT FORUM. I WISH ALL A PROSPEROUS YEAR EVEN AS WE EXPECT GREAT CHANGES TO THIS FORUM BYE.

By: Will	Date: 22/05/2008 21:38:47		Type : Comment
I wanted to work out the actual factorials of numbers so I made a C++ program to work it out. It uses arrays to allow it to work up to around 10,000,000 digits. This is adequate for very large factorials; 1 million factorial is about 5.5mill digits. Once it has worked it out you can save it to a text file. You can download the program from: http://www.thecrimelife.net/factorial/ Factorial.exe is the program for most users, while the x64 is for 64 bit OS users and the core2-64 is for people with duel core Intel processors and running a 64bit OS. Also there is a text file of 1 million factorial which took a couple of hours to work out. Hope you can work out your answers from here.

By: omuyelijah	Date: 30/05/2008 16:05:07		Type : Comment
Hi Williams Hector, Thanks for the program. B4 now, someone suggested using arrays to solve the problem but I haven't had time 2 bcos of a lot of projects at hand. Could u send me the codes or explain how u did it so I can write it? Thanks once more and to VGR.

Do register to be able to answer

©2010 These pages are served without commercial sponsorship. (No popup ads, etc...). Bandwidth abuse increases hosting cost forcing sponsorship or shutdown. This server aggressively defends against automated copying for any reason including offline viewing, duplication, etc... Please respect this requirement and DO NOT RIP THIS SITE.
Please DO link to this page! Post to Plurk Post to Yahoo Buzz Post to Delicious Post to Digg Post to MySpace Post to Ping.fm Post to Reddit Post to StumbleUpon

Contact

page generated in 342.463970 milliseconds

Why Google AdSense ads ?

New Improved Search!