Click here to Skip to main content
12,824,247 members (44,836 online)

Algorithms

 
GeneralRe: Factorials Pin
Ian Uy25-Jun-08 7:32
memberIan Uy25-Jun-08 7:32 
GeneralRe: Factorials Pin
Tim Craig25-Jun-08 9:55
memberTim Craig25-Jun-08 9:55 
GeneralRe: Factorials Pin
Luc Pattyn25-Jun-08 12:01
mvpLuc Pattyn25-Jun-08 12:01 
GeneralRe: Factorials Pin
Tim Craig25-Jun-08 22:06
memberTim Craig25-Jun-08 22:06 
AnswerRe: Factorials Pin
cp987624-Jun-08 13:33
membercp987624-Jun-08 13:33 
AnswerRe: Factorials Pin
Matthew Butler24-Jun-08 13:38
memberMatthew Butler24-Jun-08 13:38 
GeneralRe: Factorials Pin
cp987624-Jun-08 15:05
membercp987624-Jun-08 15:05 
GeneralRe: Factorials Pin
Luc Pattyn24-Jun-08 16:02
mvpLuc Pattyn24-Jun-08 16:02 
Hi Peter,

IMO this will behave much better; it gives 4 for 10000000, does not overflow,
has no loops but uses a recursion (scaling down by a factor of 5).

private int rightmostNonzeroInFactorial(int n) {
	int result = 1;
	// factor ending on 1
	// no change
	// factor ending on 2
	int count2 = (n+8) / 10;
	// factor ending on 3
	int count3 = (n + 7) / 10;
	// factor ending on 4
	int count4 = (n + 6) / 10;
	// factor ending on 5
	int count5 = (n + 5) / 10;
	// factor ending on 6
	int count6 = (n + 4) / 10;
	// factor ending on 7
	int count7 = (n + 3) / 10;
	// factor ending on 8
	int count8 = (n + 2) / 10;
	// factor ending on 9
	int count9 = (n + 1) / 10;
	// factor ending on 0
	int count10 = (n + 0) / 10;
	count5 += count10;
	if (count5 != 0) {
		result = (result * rightmostNonzeroInFactorial(count5)) % 10;
		count2 -= count5;
	}
	count2 += 2 * count4;	// 4 = 2*2
	count2 += 3 * count8;	// 8 = 2*2*2
	count2 += 4 * count6;	// 16 = 2*2*2*2

	count3 += 2 * count9;	// 9 = 3*3;
	count3 += 3 * count7;	// 27 = 3*3*3

	int[] fact3 = new int[] { 1, 3, 9, 7 };	// 3^5 ends on 3
	result = (result * fact3[count3 % fact3.Length]) % 10;

	int[] fact2 = new int[] { 1, 2, 4, 8 };	// 2^5 ends on 2
	int factor2=fact2[count2 % fact2.Length];
	if (factor2 == 1 && count2 != 0) factor2 = 6;	// 2^4 = 16
	result = (result * factor2) % 10;

	return result;
}


Main principle is factors that are not multiples of 5 don't care about their
digits except the lowest one (and also: there will be more powers of 2 than
powers of 5).

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

Voting for dummies? No thanks. Dead | X|


GeneralRe: Factorials Pin
cp987624-Jun-08 21:09
membercp987624-Jun-08 21:09 
GeneralRe: Factorials Pin
Luc Pattyn25-Jun-08 0:53
mvpLuc Pattyn25-Jun-08 0:53 
GeneralRe: Factorials Pin
cp987625-Jun-08 3:27
membercp987625-Jun-08 3:27 
GeneralRe: Factorials Pin
Luc Pattyn25-Jun-08 3:34
mvpLuc Pattyn25-Jun-08 3:34 
GeneralRe: Factorials Pin
cp987625-Jun-08 3:40
membercp987625-Jun-08 3:40 
AnswerRe: Factorials Pin
tim_one14-Jul-08 9:37
membertim_one14-Jul-08 9:37 
AnswerRe: Factorials Pin
Arash Partow25-Jun-08 3:14
memberArash Partow25-Jun-08 3:14 
GeneralRe: Factorials Pin
Ian Uy25-Jun-08 7:26
memberIan Uy25-Jun-08 7:26 
QuestionHow to determine the next x,y coordinate for a tank in a 2-D game... Pin
Edmundisme18-Jun-08 9:35
memberEdmundisme18-Jun-08 9:35 
AnswerRe: How to determine the next x,y coordinate for a tank in a 2-D game... Pin
73Zeppelin18-Jun-08 12:38
member73Zeppelin18-Jun-08 12:38 
GeneralRe: How to determine the next x,y coordinate for a tank in a 2-D game... Pin
Matthew Butler18-Jun-08 12:44
memberMatthew Butler18-Jun-08 12:44 
GeneralRe: How to determine the next x,y coordinate for a tank in a 2-D game... Pin
73Zeppelin18-Jun-08 23:00
member73Zeppelin18-Jun-08 23:00 
GeneralRe: How to determine the next x,y coordinate for a tank in a 2-D game... Pin
Edmundisme18-Jun-08 13:00
memberEdmundisme18-Jun-08 13:00 
AnswerRe: How to determine the next x,y coordinate for a tank in a 2-D game... Pin
Matthew Butler18-Jun-08 12:41
memberMatthew Butler18-Jun-08 12:41 
GeneralRe: How to determine the next x,y coordinate for a tank in a 2-D game... Pin
Edmundisme18-Jun-08 13:01
memberEdmundisme18-Jun-08 13:01 
JokeRe: How to determine the next x,y coordinate for a tank in a 2-D game... Pin
CPallini18-Jun-08 22:19
mvpCPallini18-Jun-08 22:19 
QuestionPolyline offset algorithm Pin
beko16-Jun-08 22:59
memberbeko16-Jun-08 22:59 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.


Advertise | Privacy | Mobile
Web01 | 2.8.170308.1 | Last Updated 22 Mar 2017
Copyright © CodeProject, 1999-2017
All Rights Reserved. Terms of Service
Layout: fixed | fluid