Factorial benchmark/program help

[D_o_S]

Hiya,

We were just discussing factorials in class today, I thought about coming up with a program... my C/C++ skills are not as 1337 as those of most of you out there... so I ask for help... here is what I have so far:

//

#include "stdafx.h"
#include <iostream>

int factorial(float);

void main(void) {
float number;
int pause;
std::cout << "Please enter a positive integer: ";
std::cin >> number;
if (number < 0)
std::cout << "That is not a positive integer.\n";
else
std::cout << number << " factorial is: " << factorial(number)<<std::endl;
std::cin >> pause;
}

int factorial(float number) {
int temp;

if(number <= 1) return 1;

temp = number * factorial(number - 1);
return temp;
}



What I need added:
1)Compatibility for super-large numbers (6 numbers +)
2)A timing function (calculation took xyz seconds)

Any help greatly appreciated!

[spdycpu]

I've been tinkering with this a little bit, let me know if this is more or less what you need. Here is a file with n!=x out to n!=1000. http://chess.homelinux.com/n1000.doc.gz (decompress with winrar or gunzip)

Also how high you can go depends on the precision of the variable you're working with as well as compiler and/or options at compile time. To get the most precision I used GCC 4.0.1 in linux with long double variables. This allowed absolutely ridiculously huge numbers. Also benchmarking factorial calculation doesn't look like it'll work out too well, as the computations finish near instantly and of course have overflows like mad compiled in Windows. You could calculate n!=0 out to 16 or so and then loop that 1e9 times.

Here is 32 bit signed integers (32 bit floats would have produced the same results, only slower), VC2k5 compiler:

0!=1
1!=1
2!=2
3!=6
4!=24
5!=120
6!=720
7!=5040
8!=40320
9!=362880
10!=3628800
11!=39916800
12!=479001600
13!=1932053504
14!=1278945280
15!=2004310016
16!=2004189184

Biggest number possible: 16!=2004189184
Calculation time: 0.000 seconds


64 bit integers, VC2k5 compiler:

0!=1
1!=1
2!=2
3!=6
4!=24
5!=120
6!=720
7!=5040
8!=40320
9!=362880
10!=3628800
11!=39916800
12!=479001600
13!=6227020800
14!=87178291200
15!=1307674368000
16!=20922789888000
17!=355687428096000
18!=6402373705728000
19!=121645100408832000
20!=2432902008176640000

Biggest number possible: 20!=2432902008176640000
Calculation time: 0.000 seconds


Here is the source (switched it from C++ to C) after modification:

#include <stdio.h>
#include <time.h>

long double factorial(long double number);

int main() {
long double number, i, temp, lastnum;
double time;
clock_t start, end;

/*
printf("\nPlease enter a positive integer: ");
scanf("%d", &number);
if((int)number < 0) {
printf("That is not a positive integer."); exit(0);
}
*/

start = clock();
for(i=0;i<1e9;i++) {
temp = factorial(i);
if(temp < 0.0) {
printf("\nBiggest number possible: %llf!=%llf", i-1, lastnum);
break;
}
printf("%llf!=%llf\n", i, temp);
lastnum = temp;
}

end = clock();
time = (double)(end-start) / CLOCKS_PER_SEC;
printf("\nCalculation time: %0.3f seconds\n", time);
}

long double factorial(long double number) {
long double temp;

if(number == 0) return 1;

temp = number * factorial(number - 1);
return temp;
}


Basically this will just see what the biggest number you can calculate without an overflow and then say how long it took. Try it on different compilers with different compiler flags, etc. to see how the precision changes the results. As far as making a benchmark out of it, I'm not sure how to get around the overflows with a Windows box. When I try to go too high it'll just crash on me, but, works like a charm in linux due to whatever libs GCC adds to support those large numbers.

Here is n!=1000 just for fun :)

1000!=40238726007709377323853154004852479736272065 73347783276441915621430593080833938531761429886287 57782540216836757224938243479237704648834632414382 03924827776519904767707243628314772650359167272379 63916085937547254094271857966181334276849970271004 35327080266483279939335194534223135234710931467901 06485680249867289954692858120660910065031850908529 61662447050100721022710000263212401085057680236329 44194575463730238779630717726381286607551652495843 98750896162116895097475863594375276252007978229810 00133465733734395739846147178869780042890866525388 03414221807112235755062639105026239922466140378903 61940684147248423412279046935660755045520198992441 21792373171487272686446288785609976575981418708652 39619367848553567860415444050248995365322893510403 35767985368080726770791353317147243932400408462538 99648921484521447776917885716258961270019733076769 12478849177725617025596461945749109437070270458645 15708726602553024654081394497568996413735664920769 22131928577760949377249893775941051890101483592529 35279787929172220946742149799356975674552579390158 96439620500573874643694916035708551840426750385721 00157205206936419608674050404796123741156945639952 70297935098651951520748978766356228013963805300932 84441215133571352174988434231993200356799671348640 14159671263015387446432792415644979084702025661083 64091733755332307582221881193582117808957993842518 42333425712710121270245318743131175294388990658948 74171028390426436477391678699810134321952265527493 75692046081753602213281068533754743709403362875142 26472556620820358999016899944609838108609117059793 05380789727368042851412457181693738380929358629387 29387543678823093106123431230700503171222230635340 88929214294623068258429817602552877771044108171568 59302563120293528179918496927330159638964736983675 37743522053997781659615414392624023834214032997668 19173206388002860638457122602455431037848386817449 69178878120621033750842050743933140916513904522203 56330922552740643986927977667857487928941140176823 62822726692458105609267034883379025874610144371293 65902066162972840576479100907874157542488810613970 16004038495072885772206789763825535825012003787292 17650498349940275342957449888281775243370206120115 49827306358746206383411313490496852155685635786034 44487804676438292688532507420336648073873611600125 83196561123099936473503473487312857039677950575584 15160642487895245897211531957553551421740069060117 48667968212623632706096338709729383189865072018605 12277844105176162118102564502477933319039351677818 95141500534149101336406887052048044631652181181579 27096747517516793845565299569387246488577716541438 449678487649532248064000

[spdycpu]

Here is the benchmark program using that factorial function. It loops through n!=0 to n!=16 1e7 times. Here are some results from a few of my computers with it:

Athlon 64 (San Diego) 2.72GHz:
Calculation time: 5.406 seconds
31.447 million factorials per second

Athlon XP (mobile Barton) 2.5GHz:
Calculation time: 6.000 seconds
28.333 million factorials per second

Pentium 4 (Northwood) 3.0GHz:
Calculation time: 10.156 seconds
16.739 million factorials per second

Microsoft VC 2005 compiled binary: http://chess.homelinux.com/factbench.zip
Just run this, it'll calculate for 5-10 seconds (depending on CPU speed) and tell you the results.

Here is the source:

#include <stdio.h>
#include <time.h>

int factorial(int number);

int main() {
unsigned int number, i, x, temp, loop, xn;
double time, fspeed;
clock_t start, end;
temp = 0;
loop = 1e7;
xn = 17;

start = clock();
for(i=0;i<1e7;i++) {
for(x=0;x<xn;x++) {
temp += factorial(x);
}
}
end = clock();

time = (double)(end-start) / CLOCKS_PER_SEC;
fspeed = ((loop*xn) / time) / 1e6;
printf("\nCalculation time: %0.3f seconds", time);
printf("\n%0.3f million factorials per second", fspeed);
printf("\n\nPress enter to exit");
getchar();
return temp;
}

int factorial(int number) {
int temp;

if(number == 0) return 1;

temp = number * factorial(number - 1);
return temp;
}


I had to make factorial(); do something otherwise the compiler would know nothing used it and just wouldn't do anything with the function (completing the test instantly), thats where incrementing temp comes in. It will overflow into oblivion, but, since it gets returned at the end of the program the compiler must calculate the factorial function.

Here is the assembly for it interlaced with the C source, so you can see exactly what is going on:

; Listing generated by Microsoft (R) Optimizing Compiler Version 14.00.50727.42

TITLE C:\c\xs\fact32.c
.686P
.XMM
include listing.inc
.model flat

INCLUDELIB OLDNAMES

EXTRN _getchar:PROC
EXTRN _printf:PROC
EXTRN _clock:PROC
$SG-4 DB 0aH, 'Calculation time: %0.3f seconds', 00H
ORG $+3
$SG-5 DB 0aH, '%0.3f million factorials per second', 00H
ORG $+3
$SG-6 DB 0aH, 0aH, 'Press enter to exit', 00H
PUBLIC _factorial
; Function compile flags: /Ogtpy
; File c:\c\xs\fact32.c
; COMDAT _factorial
_TEXT SEGMENT
_number$ = 8 ; size = 4
_factorial PROC ; COMDAT

; 31 : int factorial(int number) {

push esi

; 32 : int temp;
; 33 :
; 34 : if(number == 0) return 1;

mov esi, DWORD PTR _number$[esp]
test esi, esi
jne SHORT $LN1@factorial
mov eax, 1
pop esi

; 37 : return temp;
; 38 : }

ret 0
$LN1@factorial:

; 35 :
; 36 : temp = number * factorial(number - 1);

lea eax, DWORD PTR [esi-1]
push eax
call _factorial
imul eax, esi
add esp, 4
pop esi

; 37 : return temp;
; 38 : }

ret 0
_factorial ENDP
_TEXT ENDS
PUBLIC __real@3eb0c6f7a0b5ed8d
PUBLIC __real@41a443fd00000000
PUBLIC __real@3f50624dd2f1a9fc
PUBLIC __real@41f0000000000000
PUBLIC __real@416312d000000000
PUBLIC _main
EXTRN __fltused:DWORD
; COMDAT __real@3eb0c6f7a0b5ed8d
CONST SEGMENT
__real@3eb0c6f7a0b5ed8d DQ 03eb0c6f7a0b5ed8dr ; 1e-006
CONST ENDS
; COMDAT __real@41a443fd00000000
CONST SEGMENT
__real@41a443fd00000000 DQ 041a443fd00000000r ; 1.7e+008
CONST ENDS
; COMDAT __real@3f50624dd2f1a9fc
CONST SEGMENT
__real@3f50624dd2f1a9fc DQ 03f50624dd2f1a9fcr ; 0.001
CONST ENDS
; COMDAT __real@41f0000000000000
CONST SEGMENT
__real@41f0000000000000 DQ 041f0000000000000r ; 4.29497e+009
CONST ENDS
; COMDAT __real@416312d000000000
CONST SEGMENT
__real@416312d000000000 DQ 0416312d000000000r ; 1e+007
; Function compile flags: /Ogtpy
CONST ENDS
; COMDAT _main
_TEXT SEGMENT
tv201 = -8 ; size = 4
tv196 = -8 ; size = 4
_time$ = -8 ; size = 8
_main PROC ; COMDAT

; 6 : int main() {

push ebp
mov ebp, esp
and esp, -64 ; ffffffc0H
sub esp, 56 ; 00000038H
push esi
push edi

; 7 : unsigned int number, i, x, temp, loop, xn;
; 8 : double time, fspeed;
; 9 : clock_t start, end;
; 10 : temp = 0;

xor esi, esi

; 11 : loop = 1e7;
; 12 : xn = 17;
; 13 :
; 14 : start = clock();

call _clock

; 15 : for(i=0;i<1e7;i++) {

fld QWORD PTR __real@416312d000000000
mov edi, eax
xor edx, edx
$LN6@main:

; 16 : for(x=0;x<xn;x++) {

xor ecx, ecx
$LN3@main:

; 17 : temp += factorial(x);

test ecx, ecx
jne SHORT $LN9@main
mov eax, 1
jmp SHORT $LN10@main
$LN9@main:
lea eax, DWORD PTR [ecx-1]
push eax
call _factorial
add esp, 4
imul eax, ecx
$LN10@main:
add ecx, 1
add esi, eax
cmp ecx, 17 ; 00000011H
jb SHORT $LN3@main
add edx, 1
mov ecx, edx
test ecx, ecx
mov DWORD PTR tv201[esp+64], ecx
fild DWORD PTR tv201[esp+64]
jge SHORT $LN26@main

; 15 : for(i=0;i<1e7;i++) {

fadd QWORD PTR __real@41f0000000000000
$LN26@main:
fcomp ST(1)
fnstsw ax
test ah, 5
jnp SHORT $LN6@main
fstp ST(0)

; 18 : }
; 19 : }
; 20 : end = clock();

call _clock

; 21 :
; 22 : time = (double)(end-start) / CLOCKS_PER_SEC;

sub eax, edi
mov DWORD PTR tv196[esp+64], eax
fild DWORD PTR tv196[esp+64]

; 23 : fspeed = ((loop*xn) / time) / 1e6;
; 24 : printf("\nCalculation time: %0.3f seconds", time);

sub esp, 8
fmul QWORD PTR __real@3f50624dd2f1a9fc
fst QWORD PTR _time$[esp+72]
fstp QWORD PTR [esp]
push OFFSET $SG-4
call _printf
fld QWORD PTR __real@41a443fd00000000
fdiv QWORD PTR _time$[esp+76]

; 25 : printf("\n%0.3f million factorials per second", fspeed);

add esp, 4
fmul QWORD PTR __real@3eb0c6f7a0b5ed8d
fstp QWORD PTR [esp]
push OFFSET $SG-5
call _printf

; 26 : printf("\n\nPress enter to exit");

push OFFSET $SG-6
call _printf
add esp, 16 ; 00000010H

; 27 : getchar();

call _getchar

; 28 : return temp;
; 29 : }

pop edi
mov eax, esi
pop esi
mov esp, ebp
pop ebp
ret 0
_main ENDP
_TEXT ENDS
END