3v4l.org

run code in 300+ PHP versions simultaneously
<?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; } } ?>
Finding entry points
Branch analysis from position: 0
2 jumps found. (Code = 43) Position 1 = 5, Position 2 = 20
Branch analysis from position: 5
2 jumps found. (Code = 43) Position 1 = 32, Position 2 = 36
Branch analysis from position: 32
1 jumps found. (Code = 62) Position 1 = -2
Branch analysis from position: 36
Branch analysis from position: 20
filename:       /in/MZN0e
function name:  (null)
number of ops:  45
compiled vars:  !0 = $listN, !1 = $fn, !2 = $start, !3 = $end
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
  101     0  E >   ASSIGN                                                   !0, '1%0A2%0A3%0A4%0A5%0A6%0A7%0A8%0A9%0A10%0A11%0A12%0A100%0A9999%0A123456%0A1000000000%0A2000000000%0A2147483647'
  119     1        ASSIGN                                                   !1, 0
  120     2        FETCH_IS                                         ~6      '_GET'
          3        ISSET_ISEMPTY_DIM_OBJ                         0          ~6, 'listN'
          4      > JMPZ                                                     ~7, ->20
  122     5    >   FETCH_R                      global              ~8      '_GET'
          6        FETCH_DIM_R                                      ~9      ~8, 'listN'
          7        ASSIGN                                                   !0, ~9
  123     8        INIT_FCALL                                               'microtime'
          9        SEND_VAL                                                 <true>
         10        DO_ICALL                                         $11     
         11        ASSIGN                                                   !2, $11
  124    12        INIT_STATIC_METHOD_CALL                                  'golomb', 'fThisList'
         13        SEND_VAR                                                 !0
         14        DO_FCALL                                      0  $13     
         15        ASSIGN                                                   !1, $13
  125    16        INIT_FCALL                                               'microtime'
         17        SEND_VAL                                                 <true>
         18        DO_ICALL                                         $15     
         19        ASSIGN                                                   !3, $15
  128    20    >   ECHO                                                     '%3Chtml%3E%0A%3Chead%3E%3C%2Fhead%3E%0A%3Cbody%3E%0A%3Cform+action%3D%22%22+method%3D%22get%22%3E%0A%3Ci%3Ef%28%3Ctextarea+name%3D%22listN%22+rows%3D%2215%22%3E'
  132    21        INIT_FCALL                                               'htmlentities'
         22        SEND_VAR                                                 !0
         23        DO_ICALL                                         $17     
         24        ECHO                                                     $17
         25        ECHO                                                     '%3C%2Ftextarea%3E%29%3C%2Fi%3E%3Cbr+%2F%3E%0A%3Cinput+type%3D%22submit%22+value%3D%22Calculate+f%28n%29%22+%2F%3E%3Cbr+%2F%3E%3Cbr+%2F%3E%0A%3Ci%3Ef%28n%29+%3D%3C%2Fi%3E%0A%3Cpre%3E'
  135    26        INIT_FCALL                                               'var_export'
         27        SEND_VAR                                                 !1
         28        DO_ICALL                                                 
         29        ECHO                                                     '%3C%2Fpre%3E%3Cbr+%2F%3E%0A'
  137    30        ISSET_ISEMPTY_CV                                         !3
         31      > JMPZ                                                     ~19, ->36
  139    32    >   ECHO                                                     'Combined+processing+time%3A+'
         33        SUB                                              ~20     !3, !2
         34        ECHO                                                     ~20
         35        ECHO                                                     '+seconds%0A'
  142    36    >   ECHO                                                     '%3C%2Fform%3E%0AThis+page%27s+source%3A%3Cbr+%2F%3E%0A'
  145    37        INIT_FCALL                                               'htmlentities'
         38        INIT_FCALL                                               'highlight_file'
         39        SEND_VAL                                                 '%2Fin%2FMZN0e'
         40        DO_ICALL                                         $21     
         41        SEND_VAR                                                 $21
         42        DO_ICALL                                                 
  147    43        ECHO                                                     '%3C%2Fbody%3E%0A%3C%2Fhtml%3E%0A'
  228    44      > RETURN                                                   1

Class golomb:
Function f:
Finding entry points
Branch analysis from position: 0
2 jumps found. (Code = 43) Position 1 = 5, Position 2 = 6
Branch analysis from position: 5
1 jumps found. (Code = 62) Position 1 = -2
Branch analysis from position: 6
1 jumps found. (Code = 42) Position 1 = 36
Branch analysis from position: 36
2 jumps found. (Code = 44) Position 1 = 38, Position 2 = 16
Branch analysis from position: 38
1 jumps found. (Code = 62) Position 1 = -2
Branch analysis from position: 16
2 jumps found. (Code = 43) Position 1 = 19, Position 2 = 20
Branch analysis from position: 19
2 jumps found. (Code = 43) Position 1 = 21, Position 2 = 28
Branch analysis from position: 21
2 jumps found. (Code = 43) Position 1 = 29, Position 2 = 33
Branch analysis from position: 29
2 jumps found. (Code = 44) Position 1 = 38, Position 2 = 16
Branch analysis from position: 38
Branch analysis from position: 16
Branch analysis from position: 33
Branch analysis from position: 28
Branch analysis from position: 20
filename:       /in/MZN0e
function name:  f
number of ops:  40
compiled vars:  !0 = $n, !1 = $queueOpsAddCountDown, !2 = $ops, !3 = $opsAdd, !4 = $opsAddCountDown, !5 = $opsAddFuture, !6 = $opsAddDone, !7 = $predictSum, !8 = $sum, !9 = $sumFuture
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
   38     0  E >   RECV                                             !0      
   40     1        CAST                                          4  ~10     !0
          2        ASSIGN                                                   !0, ~10
   41     3        IS_SMALLER                                               !0, 1
          4      > JMPZ                                                     ~12, ->6
   42     5    > > RETURN                                                   null
   44     6    >   ASSIGN                                                   !1, <array>
   45     7        ASSIGN                                                   !2, 0
   46     8        ASSIGN                                                   !3, 0
   47     9        ASSIGN                                                   !4, 0
   48    10        ASSIGN                                                   !5, 0
   49    11        ASSIGN                                                   !6, <true>
   50    12        ASSIGN                                                   !7, <true>
   51    13        ASSIGN                                                   !8, 0
   52    14        ASSIGN                                                   !9, 0
   54    15      > JMP                                                      ->36
   56    16    >   IS_EQUAL                                         ~22     !4, 0
         17        ASSIGN                                                   !6, ~22
   58    18      > JMPZ                                                     !6, ->20
   60    19    >   PRE_INC                                                  !3
   64    20    > > JMPZ                                                     !7, ->28
   66    21    >   PRE_INC                                                  !5
   67    22        ASSIGN_DIM                                               !1
         23        OP_DATA                                                  !3
   69    24        MUL                                              ~27     !5, !3
         25        ASSIGN_OP                                     1          !9, ~27
   70    26        IS_SMALLER                                       ~29     !9, !0
         27        ASSIGN                                                   !7, ~29
   74    28    > > JMPZ                                                     !6, ->33
   76    29    >   INIT_FCALL                                               'array_shift'
         30        SEND_REF                                                 !1
         31        DO_ICALL                                         $31     
         32        ASSIGN                                                   !4, $31
   80    33    >   ASSIGN_OP                                     1          !8, !3
   81    34        PRE_INC                                                  !2
   82    35        PRE_DEC                                                  !4
   54    36    >   IS_SMALLER                                               !8, !0
         37      > JMPNZ                                                    ~36, ->16
   85    38    > > RETURN                                                   !2
   86    39*     > RETURN                                                   null

End of function f

Function fthislist:
Finding entry points
Branch analysis from position: 0
2 jumps found. (Code = 77) Position 1 = 8, Position 2 = 15
Branch analysis from position: 8
2 jumps found. (Code = 78) Position 1 = 9, Position 2 = 15
Branch analysis from position: 9
1 jumps found. (Code = 42) Position 1 = 8
Branch analysis from position: 8
Branch analysis from position: 15
1 jumps found. (Code = 62) Position 1 = -2
Branch analysis from position: 15
filename:       /in/MZN0e
function name:  fThisList
number of ops:  18
compiled vars:  !0 = $listN, !1 = $fN, !2 = $n
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
   88     0  E >   RECV                                             !0      
   90     1        INIT_FCALL                                               'preg_split'
          2        SEND_VAL                                                 '%2F%5B%5Cs%2C%5D%2B%2F'
          3        SEND_VAR                                                 !0
          4        DO_ICALL                                         $3      
          5        ASSIGN                                                   !0, $3
   92     6        ASSIGN                                                   !1, <array>
   94     7      > FE_RESET_R                                       $6      !0, ->15
          8    > > FE_FETCH_R                                               $6, !2, ->15
   95     9    >   INIT_STATIC_METHOD_CALL                                  'f'
         10        SEND_VAR                                                 !2
         11        DO_FCALL                                      0  $8      
         12        ASSIGN_DIM                                               !1, !2
         13        OP_DATA                                                  $8
   94    14      > JMP                                                      ->8
         15    >   FE_FREE                                                  $6
   97    16      > RETURN                                                   !1
   98    17*     > RETURN                                                   null

End of function fthislist

End of class golomb.

Class golombArchive:
Function fwithcleanup:
Finding entry points
Branch analysis from position: 0
2 jumps found. (Code = 43) Position 1 = 5, Position 2 = 6
Branch analysis from position: 5
1 jumps found. (Code = 62) Position 1 = -2
Branch analysis from position: 6
1 jumps found. (Code = 42) Position 1 = 28
Branch analysis from position: 28
2 jumps found. (Code = 44) Position 1 = 30, Position 2 = 11
Branch analysis from position: 30
1 jumps found. (Code = 62) Position 1 = -2
Branch analysis from position: 11
2 jumps found. (Code = 43) Position 1 = 13, Position 2 = 25
Branch analysis from position: 13
2 jumps found. (Code = 43) Position 1 = 22, Position 2 = 24
Branch analysis from position: 22
1 jumps found. (Code = 42) Position 1 = 27
Branch analysis from position: 27
2 jumps found. (Code = 44) Position 1 = 30, Position 2 = 11
Branch analysis from position: 30
Branch analysis from position: 11
Branch analysis from position: 24
Branch analysis from position: 25
2 jumps found. (Code = 44) Position 1 = 30, Position 2 = 11
Branch analysis from position: 30
Branch analysis from position: 11
filename:       /in/MZN0e
function name:  fWithCleanup
number of ops:  32
compiled vars:  !0 = $n, !1 = $listFn, !2 = $ops, !3 = $sum, !4 = $cn
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
  164     0  E >   RECV                                             !0      
  166     1        CAST                                          4  ~5      !0
          2        ASSIGN                                                   !0, ~5
  167     3        IS_SMALLER                                               !0, 1
          4      > JMPZ                                                     ~7, ->6
  168     5    > > RETURN                                                   null
  170     6    >   ASSIGN                                                   !1, <array>
  171     7        ASSIGN                                                   !2, 0
  172     8        ASSIGN                                                   !3, 0
  173     9        ASSIGN                                                   !4, 0
         10      > JMP                                                      ->28
  175    11    >   IS_SMALLER                                               !3, !4
         12      > JMPZ                                                     ~12, ->25
  177    13    >   PRE_INC                                                  !2
  178    14        ASSIGN_DIM                                               !1, !4
         15        OP_DATA                                                  !2
  179    16        FETCH_DIM_R                                      ~15     !1, !2
         17        ASSIGN_OP                                     1          !3, ~15
  182    18        UNSET_DIM                                                !1, !2
  183    19        MOD                                              ~17     !2, 4096
         20        IS_EQUAL                                                 ~17, 0
         21      > JMPZ                                                     ~18, ->24
  184    22    >   INIT_FCALL                                               'gc_collect_cycles'
         23        DO_ICALL                                                 
         24    > > JMP                                                      ->27
  188    25    >   ASSIGN_DIM                                               !1, !4
         26        OP_DATA                                                  !2
  173    27    >   PRE_INC                                                  !4
         28    >   IS_SMALLER                                               !3, !0
         29      > JMPNZ                                                    ~22, ->11
  192    30    > > RETURN                                                   !2
  193    31*     > RETURN                                                   null

End of function fwithcleanup

Function fbrute:
Finding entry points
Branch analysis from position: 0
2 jumps found. (Code = 43) Position 1 = 6, Position 2 = 7
Branch analysis from position: 6
1 jumps found. (Code = 62) Position 1 = -2
Branch analysis from position: 7
1 jumps found. (Code = 42) Position 1 = 22
Branch analysis from position: 22
2 jumps found. (Code = 44) Position 1 = 24, Position 2 = 11
Branch analysis from position: 24
1 jumps found. (Code = 62) Position 1 = -2
Branch analysis from position: 11
2 jumps found. (Code = 43) Position 1 = 13, Position 2 = 19
Branch analysis from position: 13
1 jumps found. (Code = 42) Position 1 = 21
Branch analysis from position: 21
2 jumps found. (Code = 44) Position 1 = 24, Position 2 = 11
Branch analysis from position: 24
Branch analysis from position: 11
Branch analysis from position: 19
2 jumps found. (Code = 44) Position 1 = 24, Position 2 = 11
Branch analysis from position: 24
Branch analysis from position: 11
filename:       /in/MZN0e
function name:  fBrute
number of ops:  26
compiled vars:  !0 = $n, !1 = $listFn, !2 = $ops, !3 = $sum, !4 = $cn
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
  202     0  E >   RECV                                             !0      
  204     1        ASSIGN                                                   !1, <array>
  205     2        CAST                                          4  ~6      !0
          3        ASSIGN                                                   !0, ~6
  206     4        IS_SMALLER                                               !0, 1
          5      > JMPZ                                                     ~8, ->7
  207     6    > > RETURN                                                   null
  209     7    >   ASSIGN                                                   !2, 0
  210     8        ASSIGN                                                   !3, 0
  211     9        ASSIGN                                                   !4, 0
         10      > JMP                                                      ->22
  213    11    >   IS_SMALLER                                               !3, !4
         12      > JMPZ                                                     ~12, ->19
  215    13    >   PRE_INC                                                  !2
  216    14        ASSIGN_DIM                                               !1, !4
         15        OP_DATA                                                  !2
  217    16        FETCH_DIM_R                                      ~15     !1, !2
         17        ASSIGN_OP                                     1          !3, ~15
         18      > JMP                                                      ->21
  221    19    >   ASSIGN_DIM                                               !1, !4
         20        OP_DATA                                                  !2
  211    21    >   PRE_INC                                                  !4
         22    >   IS_SMALLER                                               !3, !0
         23      > JMPNZ                                                    ~19, ->11
  225    24    > > RETURN                                                   !2
  226    25*     > RETURN                                                   null

End of function fbrute

End of class golombArchive.

Generated using Vulcan Logic Dumper, using php 8.0.0


preferences:
151.88 ms | 1417 KiB | 27 Q