Click here to Skip to main content
12,296,307 members (63,488 online)

Algorithms

 
GeneralRe: Factorials Pin
Ian Uy25-Jun-08 6:32
memberIan Uy25-Jun-08 6:32 
GeneralRe: Factorials Pin
Tim Craig25-Jun-08 8:55
memberTim Craig25-Jun-08 8:55 
GeneralRe: Factorials Pin
Luc Pattyn25-Jun-08 11:01
mvpLuc Pattyn25-Jun-08 11:01 
GeneralRe: Factorials Pin
Tim Craig25-Jun-08 21:06
memberTim Craig25-Jun-08 21:06 
AnswerRe: Factorials Pin
cp987624-Jun-08 12:33
membercp987624-Jun-08 12:33 
AnswerRe: Factorials Pin
Matthew Butler24-Jun-08 12:38
memberMatthew Butler24-Jun-08 12:38 
GeneralRe: Factorials Pin
cp987624-Jun-08 14:05
membercp987624-Jun-08 14:05 
GeneralRe: Factorials Pin
Luc Pattyn24-Jun-08 15:02
mvpLuc Pattyn24-Jun-08 15: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 20:09
membercp987624-Jun-08 20:09 
GeneralRe: Factorials Pin
Luc Pattyn24-Jun-08 23:53
mvpLuc Pattyn24-Jun-08 23:53 
GeneralRe: Factorials Pin
cp987625-Jun-08 2:27
membercp987625-Jun-08 2:27 
GeneralRe: Factorials Pin
Luc Pattyn25-Jun-08 2:34
mvpLuc Pattyn25-Jun-08 2:34 
GeneralRe: Factorials Pin
cp987625-Jun-08 2:40
membercp987625-Jun-08 2:40 
AnswerRe: Factorials Pin
tim_one14-Jul-08 8:37
membertim_one14-Jul-08 8:37 
AnswerRe: Factorials Pin
Arash Partow25-Jun-08 2:14
memberArash Partow25-Jun-08 2:14 
GeneralRe: Factorials Pin
Ian Uy25-Jun-08 6:26
memberIan Uy25-Jun-08 6:26 
QuestionHow to determine the next x,y coordinate for a tank in a 2-D game... Pin
Edmundisme18-Jun-08 8:35
memberEdmundisme18-Jun-08 8:35 
AnswerRe: How to determine the next x,y coordinate for a tank in a 2-D game... Pin
73Zeppelin18-Jun-08 11:38
member73Zeppelin18-Jun-08 11:38 
GeneralRe: How to determine the next x,y coordinate for a tank in a 2-D game... Pin
Matthew Butler18-Jun-08 11:44
memberMatthew Butler18-Jun-08 11:44 
GeneralRe: How to determine the next x,y coordinate for a tank in a 2-D game... Pin
73Zeppelin18-Jun-08 22:00
member73Zeppelin18-Jun-08 22:00 
GeneralRe: How to determine the next x,y coordinate for a tank in a 2-D game... Pin
Edmundisme18-Jun-08 12:00
memberEdmundisme18-Jun-08 12:00 
AnswerRe: How to determine the next x,y coordinate for a tank in a 2-D game... Pin
Matthew Butler18-Jun-08 11:41
memberMatthew Butler18-Jun-08 11:41 
GeneralRe: How to determine the next x,y coordinate for a tank in a 2-D game... Pin
Edmundisme18-Jun-08 12:01
memberEdmundisme18-Jun-08 12:01 
JokeRe: How to determine the next x,y coordinate for a tank in a 2-D game... Pin
CPallini18-Jun-08 21:19
mvpCPallini18-Jun-08 21:19 
QuestionPolyline offset algorithm Pin
beko16-Jun-08 21:59
memberbeko16-Jun-08 21: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.160525.2 | Last Updated 26 May 2016
Copyright © CodeProject, 1999-2016
All Rights Reserved. Terms of Service
Layout: fixed | fluid