3v4l.org

run code in 150+ php & hhvm versions
Bugs & Features
<?php /* Sample Input 100 9999 123456 1000000000 0 Sample Output 21 356 1684 438744 */ // n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34... // opsAddCountDown 0 0 1 0 1 0 2 1 0 2 1.... // opsAddCount 1 2 2 3 3 4 4 4 5 5 5.... // opsAddFut 1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9 9 9 9 10 10 10 10 10 11... // opsAdd +1 +2 . +2 . +3 . . +3 . . +4 . . . +4 . . . +4 . . . +5 . . . . +5 . . . . +5... // sum 1 3 3 5 5 8 8 8 11 11 11 15 15 15 15 19 19 19 19 23 23 23 23 28 28 28 28 28 33 33 33 33 33 38... // goto n(sum+1) 2 4 6 9 12 16 20 24 29 34 39... /** * * @author Starson Hochschild <starsonh@gmail.com> * */ abstract class golomb { /** * V2 - implement conditional array building and count * * @param int $n * @return NULL|number */ public static function f($n) { $n = (int)$n; if($n < 1) return null; $queueOpsAddCountDown = array(); $ops = 0; $opsAdd = 0; $opsAddCountDown = 0; $opsAddFuture = 0; $opsAddDone = true; $predictSum = true; $sum = 0; $sumFuture = 0; while ($sum < $n) { $opsAddDone = $opsAddCountDown == 0; // If we're done with this $opsAdd increment it, separated from the $opsAddDone block below on purpose if($opsAddDone) { $opsAdd++; } // Cache a future $opsAddCountDown if($predictSum) { $opsAddFuture++; $queueOpsAddCountDown[] = $opsAdd; // See if this will be enough to equal or overtake $n $sumFuture += $opsAddFuture * $opsAdd; $predictSum = $sumFuture < $n; } // If we're done with this $opsAdd grab a new $opsAddCountDown from $listOpsAddCountDown if($opsAddDone) { $opsAddCountDown = array_shift($queueOpsAddCountDown); } // Do the real work $sum += $opsAdd; $ops++; $opsAddCountDown--; } return $ops; } public static function fThisList($listN) { $listN = preg_split("/[\s,]+/", $listN); $fN = array(); foreach($listN as $n) $fN[$n] = self::f($n); return $fN; } } $listN = "1 2 3 4 5 6 7 8 9 10 11 12 100 9999 123456 1000000000 2000000000 2147483647"; $fn = 0; if(isset($_GET["listN"])) { $listN = $_GET["listN"]; $start = microtime(true); $fn = golomb::fThisList($listN); $end = microtime(true); } ?> <html> <head></head> <body> <form action="" method="get"> <i>f(<textarea name="listN" rows="15"><?php echo htmlentities($listN); ?></textarea>)</i><br /> <input type="submit" value="Calculate f(n)" /><br /><br /> <i>f(n) =</i> <pre><?php var_export($fn); ?></pre><br /> <?php if(isset($end)) { ?> Combined processing time: <?php echo $end - $start ?> seconds <?php } ?> </form> This page's source:<br /> <?php htmlentities(highlight_file(__FILE__)); ?> </body> </html> <?php /** * This is here for historical purposes. It shows the progression that lead to the method above. * @author Starson Hochschild <starsonh@gmail.com> * */ abstract class golombArchive { /** * V1.1 - added some memory management * Better, but still takes a lot of memory and crashes on large(r) numbers due to running out of memory * * @param int $n * @return NULL|number */ public static function fWithCleanup($n) { $n = (int)$n; if($n < 1) return null; $listFn = array(); $ops = 0; $sum = 0; for($cn = 0; $sum < $n; $cn++) { if($sum < $cn) { $ops++; $listFn[$cn] = $ops; $sum += $listFn[$ops]; // Cleanup unset($listFn[$ops]); if($ops % 4096 == 0) gc_collect_cycles(); } else { $listFn[$cn] = $ops; } } return $ops; } /** * V1 - a simple, "brute force" type of approach * Takes a lot of memory and crashes on large numbers due to running out of memory * * @param int $n * @return NULL|number */ public static function fBrute($n) { $listFn = array(); $n = (int)$n; if($n < 1) return null; $ops = 0; $sum = 0; for($cn = 0; $sum < $n; $cn++) { if($sum < $cn) { $ops++; $listFn[$cn] = $ops; $sum += $listFn[$ops]; } else { $listFn[$cn] = $ops; } } return $ops; } } ?>

Abusive script

This script was stopped while abusing our resources