[Challenge ] largest factorial

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

User avatar
jazz090
Forum Contributor
Posts: 176
Joined: Sun Apr 12, 2009 3:29 pm
Location: England

[Challenge ] largest factorial

Post by jazz090 »

all right my first challenge!!!

first part (fairly easy) - write a function that will output the answer to n-factorial (n!) i.e. 5! = 1 x 2 x 3 x 4 x 5 = 120 | 4! = 1 x 2 x 3 x 4 = 24 and as always 0! = 1.

this can be done fairly easily using recursions and loops but the thing is, they usually time out when the value of n gets a little high and starts returning positive infinity or crashes all together. which brings us to the challenge:

the winner is the one whose code is cable of executing the largest n.

my personal best is n = 170 but at 171 it returns INF:

Code: Select all

<?php
function factorial($n){
    if ($n == 0){
        return 1;
    }
    else {
        return $n * factorial($n - 1);
    }
}
echo factorial(5); // 120
echo factorial(170); // 7.25741561531E+306
echo factorial(171); // INF
?>
now the key to this is that it doesn't have to be a straight forward solution, you are still a winner even if your outputs are returned as a constructed string from a series of numbers to give the answers. LONG AS IT GETS THE JOB DONE.
Mark Baker
Forum Regular
Posts: 710
Joined: Thu Oct 30, 2008 6:24 pm

Re: [Challenge ] largest factorial

Post by Mark Baker »

Code: Select all

 
function factorial($n) {
    $n = (string) $n;
    if ($n == '0') {
        return 1;
    } else {
        return bcmul($n,factorial(bcsub($n,'1')));
    }
}
 
for ($i = 170; $i <= 200; $i++) {
    echo factorial($i).'<br />';
}
 
Non-recursive version

Code: Select all

 
function factorial($n) {
    $n = (string) $n;
    if ($n == 0) {
        return 1;
    } else {
        $factorial = '1';
        while ($n > '1') {
            $factorial = bcmul($factorial,$n);
            $n = bcsub($n,'1');
        }
        return $factorial ;
    }
}
 
for ($i = 1020; $i <= 1025; $i++) {
    echo factorial($i).'<br />';
}
 
Last edited by Mark Baker on Tue Sep 01, 2009 12:21 pm, edited 1 time in total.
User avatar
John Cartwright
Site Admin
Posts: 11470
Joined: Tue Dec 23, 2003 2:10 am
Location: Toronto
Contact:

Re: [Challenge ] largest factorial

Post by John Cartwright »

Code: Select all

function factorial($input) 
{
    $input = (int)$input;
    $factorial = 1;
    
    if ($input == 0) 
        return;
 
    for ($i = 1; $i < $input + 1; $i++) 
        $factorial *= $i;
    
    return $factorial;
}
User avatar
McInfo
DevNet Resident
Posts: 1532
Joined: Wed Apr 01, 2009 1:31 pm

Re: [Challenge ] largest factorial

Post by McInfo »

Code: Select all

<?php
header('Content-Type: text/plain');
function factorial ($n, $as_float = false)
{
    if ($n > 0) {
        $i = 0;
        $f = '1';
        while ($i < $n) {
            $f = bcmul($f, (string) ++$i);
        }
    } elseif ($n == 0) {
        $f = '1';
    } else {
        $f = null;
        $as_float = false;
    }
    if ($as_float) {
        return (float) $f;
    } else {
        return $f;
    }
}
var_dump(factorial(171)); // string(310) "..."
//var_dump(factorial(171, true)); // INF
//var_dump(factorial(16000)); // This could take a while
?>
Edit: This post was recovered from search engine cache.
Last edited by McInfo on Thu Jun 17, 2010 11:39 am, edited 1 time in total.
User avatar
requinix
Spammer :|
Posts: 6617
Joined: Wed Oct 15, 2008 2:35 am
Location: WA, USA

Re: [Challenge ] largest factorial

Post by requinix »

Oy, McInfo, that was cheating :wink:

Code: Select all

define("PHP_INT_MAX_LOG10", log10(PHP_INT_MAX));
 
// multiplies as strings if PHP can't handle it
function multiply($a, $b) {
    $len = strlen($a . $b);
    if ($len <= PHP_INT_MAX_LOG10) return $a * $b;
    $a = (string)$a; $b = (string)$b;
 
    $c = str_repeat("0", $len);
    //echo "a=$a, b=$b, len=$len, c=$c\n";
    for ($i = min(strlen($a), $len - 1); $i > 0; $i--) {
        for ($j = min(strlen($b), $len - 1); $j > 0; $j--) {
            $cr = $c[$i + $j - 1] + $a[$i - 1] * $b[$j - 1];
            //echo "i=$i, j=$j, cr=$cr\n";
            for ($k = $i + $j - 1; $cr > 9; $k--) {
                //echo "loop: k=$k, cr=$cr, c=$c\n";
                $c[$k] = ($cr % 10);
                $cr = $c[$k - 1] + floor($cr / 10);
            }
            $c[$k] = $cr;
            //echo "no loop: k=$k, c=$c\n";
        }
    }
    return ltrim($c, "0");
}
 
function factorial($n) {
    $factorial = 1;
    while ($n > 1) $factorial = multiply($factorial, $n--);
    return $factorial;
}
 
echo factorial(1234);

Code: Select all

510849814664695768813061762610045987502727416246362078757583648856797838863891141199043673982149094
516168659597971900855959572160602010817908635627407113924084026061622844243479264441682937703064598
774296205499801216218800688121199228255656037500367936574284764985773168878906892848844644235224691
629246544199454969400527460669508677840847535815401481943168883038396948608703570082355250281152814
023792702794467430978688961805679014528720317341950564325765687543465282585698835268598267277358386
540822467217518196580526923962706113480130137867393202297060099407810255860388094930139921110304324
733215322285896361507226213603669786074846928709556917407233492272203675129943551465674759800063734
002158260779494943353705916236711420269579239376692247716171679593596504399663926730731801393765630
737065622007712412917108281320789286726933776052806983409765126226862071752591089842539799702693305
919514002658689440140017406063982207098594617099720923169536397076075090363874686552149639666253227
009328671956414665063052651222383328246778923860988730454779465704756144707356810115377629300683332
297534613111756900531902762172159381222292540116633195356685622882768145665362541399443274469237496
751568383992586552271141810671813000311912984890766801729831181211560866273603973342321749321326860
809015694963921292637065955094725419210270399475957879922095370690313795171129858042764127194913347
302477628762607535601990124243602118624660475111847971597317143303682511923078521677576152006116690
095756300755816322008970191101657384892882348458014135420900869263817566422288727293195877241206471
336954476587094660471317874675216489673751461760257755459580181498955708174630489683296928120039961
059448125384842916890757218498897976475548548340501325923175038614220780779328413962507723058923783
049604210248458150479282296693428182189602435794731809869968834861646135862246777824053636757329403
864365601599929614625502185299212142235562889432768600006314224498453655109869326114141123861785734
471342361645024103462545164218128253501523839079252991993710939023931263175903373403711992883806036
945170356626658272873520235631287564025160817497053257051964777693153111640297330674192821352142326
056078891597390389235797326308165481354721238129688294665134284846837608887319006852053080164955332
520557181901426443200096830326771636097446146297306314548981674629662653878717255800835145656237192
706356836622686633339990298834293314628728489952297141157090239737711264689138736480615312234287495
762670790845346569235149314967438425596693866385098847093071661872051614458198282636792701126140123
785422738372964270440212520778637069635144862181838064918687911747854245063378105504530638978662811
270602008667540111819068098703720329533545286990940961451209978420751090578592261208441764541753937
812540043820913509941019594065901754020866988745836115819373470034234495212232451666657922572521604
623577330009252322921576831001795573597939262980075883704740682303209219874599760426062835660051582
025728000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000
Mark Baker
Forum Regular
Posts: 710
Joined: Thu Oct 30, 2008 6:24 pm

Re: [Challenge ] largest factorial

Post by Mark Baker »

Won't generate anything larger than 170!, but it's quick:

Code: Select all

 
function factorial($n) {
    if ($n == 0) {
        return 1;
    } else {
        return exp(array_sum(array_map('log',range(1,$n))));
    }
}
 
User avatar
jazz090
Forum Contributor
Posts: 176
Joined: Sun Apr 12, 2009 3:29 pm
Location: England

Re: [Challenge ] largest factorial

Post by jazz090 »

what mcinfo did wasn't technically cheating like i said, long as it gets the job done but tasairis very nice function!
User avatar
VladSun
DevNet Master
Posts: 4313
Joined: Wed Jun 27, 2007 9:44 am
Location: Sofia, Bulgaria

Re: [Challenge ] largest factorial

Post by VladSun »

Mark Baker wrote:Won't generate anything larger than 170!, but it's quick:
quicker but approximate (and for very large $n):

Code: Select all

 
function factorial($n) 
{
    return sqrt(2*M_PI*$n)*pow($n/exp(1), $n);
}
WIKI :)
There are 10 types of people in this world, those who understand binary and those who don't
User avatar
jazz090
Forum Contributor
Posts: 176
Joined: Sun Apr 12, 2009 3:29 pm
Location: England

Re: [Challenge ] largest factorial

Post by jazz090 »

VladSun wrote:quicker but approximate
what's the point of that?
Mark Baker
Forum Regular
Posts: 710
Joined: Thu Oct 30, 2008 6:24 pm

Re: [Challenge ] largest factorial

Post by Mark Baker »

jazz090 wrote:
VladSun wrote:quicker but approximate
what's the point of that?
Depends on the level of precision you want.

Code: Select all

 
function StieltjesFactorial($x) {
    $y = $x + 1;
    $p = 1;
    while ($y < 7) {
        $p *= $y++;
    }
    $r = exp($y * log($y) - $y + 1 / (12 * $y + 2 / (5 * $y + 53 / (42 * $y))));
    if ($x < 7) {
        $r = $r / $p;
    }
    return round($r * sqrt(2 * M_PI / $y));
}
 
Not quite as fast as VladSun's implementation of the Stirling approximation, but faster than most other methods and more accurate than Stirling for the lower ranges: 100% accurate for integer factorials up to 170!. This is still an approximation.
User avatar
jazz090
Forum Contributor
Posts: 176
Joined: Sun Apr 12, 2009 3:29 pm
Location: England

Re: [Challenge ] largest factorial

Post by jazz090 »

its not about being fast, its about getting the job done.
User avatar
VladSun
DevNet Master
Posts: 4313
Joined: Wed Jun 27, 2007 9:44 am
Location: Sofia, Bulgaria

Re: [Challenge ] largest factorial

Post by VladSun »

jazz090 wrote:its not about being fast, its about getting the job done.
Sometimes, "getting the job done" means that it should be done in "realtime" at the expense of some accuracy loss.
There are 10 types of people in this world, those who understand binary and those who don't
Mark Baker
Forum Regular
Posts: 710
Joined: Thu Oct 30, 2008 6:24 pm

Re: [Challenge ] largest factorial

Post by Mark Baker »

jazz090 wrote:its not about being fast, its about getting the job done.
32768! = can't figure out what extension to use for the 131k file containing the result, or won't phpdn allow file attachments that large?
Call time for factorialLoopBC() was 140.6867 seconds

If it's all about who has the biggest, then I do expect you to prove that all calculations are correct.

You could get up to 2147483647! running from the command line with timeout set to 0.
Combining higher range factorials without needing to worry about timeouts is the real challenge (for me at least)
User avatar
Eran
DevNet Master
Posts: 3549
Joined: Fri Jan 18, 2008 12:36 am
Location: Israel, ME

Re: [Challenge ] largest factorial

Post by Eran »

Sometimes, "getting the job done" means that it should be done in "realtime" at the expense of some accuracy loss.
Completely agree with this. You should define the acceptable error margin and work within that.
User avatar
jazz090
Forum Contributor
Posts: 176
Joined: Sun Apr 12, 2009 3:29 pm
Location: England

Re: [Challenge ] largest factorial

Post by jazz090 »

pytrin wrote:
Sometimes, "getting the job done" means that it should be done in "realtime" at the expense of some accuracy loss.
Completely agree with this. You should define the acceptable error margin and work within that.
no no no, you are taking this out of context, yes if i am making an application for a multi-corporate business then yes, time is of an essence, but this is just a challenge boys and girls nothing more. no need to make it more complicated.
Post Reply