view release on metacpan or  search on metacpan

devel/balanced-binary.pl  view on Meta::CPAN

    die "$w,$e" if $e < 0;
    die "$w,$e" if $w < 1;
    die "$w,$e" if $w<$e;
    die "$w,$e" if ($w-$e) & 1;

    if (defined $num[$w][$e]) {
      return $num[$w][$e];
    }
    # 0, num(w-1,e-1)
    # 1, num(w-1,e+1)  if w-1 >= e+1, w>=e+2
    my $num = 0;
    if ($e > 0) {
      $num += num($w-1,$e-1);
    }
    if ($w >= $e+2) {
      $num += num($w-1,$e+1);
    }
    return ($num[$w][$e] = $num);
  }

  require Math::NumSeq::Catalan;
  my $seq = Math::NumSeq::Catalan->new;

  $seq->next;
  $seq->next;
  foreach (1 .. 15) {
    my ($i, $value) = $seq->next;
    my $num = num(2*$i,0);
    print "$i $value $num\n";
  }

  foreach my $aref (@num) {
    next unless $aref;
    print join(' ',map {$_||'_'} @$aref),"\n";
  }
  exit 0;
}
{
  # monotonic

  require Math::NumSeq::Catalan;
  # my $seq = Math::NumSeq::Catalan->new;
  my $seq = Math::NumSeq::Catalan->new (values_type => 'odd');

  # require Math::NumSeq::BalancedBinary;
  # my $seq = Math::NumSeq::BalancedBinary->new;

  my $prev = -1;
  foreach (1 .. 10000) {
    my ($i, $value) = $seq->next;
    if ($value < $prev) {
      die $i;
    }
    $prev = $value;
  }
  print "$prev\n";
  exit 0;
}

{
  # formula

  require Math::NumSeq::Catalan;
  my $seq = Math::NumSeq::Catalan->new;

  my $cumul = 0;
  foreach (1 .. 20) {
    my ($i, $value) = $seq->next;

    my $formula = 0;
    foreach my $k (1 .. $i-1) {
      $formula += $seq->ith($i-$k)*$k + $seq->ith($k)
    }
    print "$i value=$value formula=$formula\n";
    $cumul += $value;
  }
  exit 0;
}

{
  # cumulative

  require Math::NumSeq::Catalan;
   my $seq = Math::NumSeq::Catalan->new;

  my $prev = 0;
  my $cumul = 0;
  foreach (1 .. 20) {
    my ($i, $value) = $seq->next;
    $cumul += $value;
    my $diff = $cumul - $prev;
    print "$i value=$value cumul=$cumul diff=$diff\n";
    $prev = $cumul;
  }
  exit 0;
}

{
  # Catalan estimate

  require Math::Symbolic;
  my $tree = Math::Symbolic->parse_from_string('4^x / sqrt(3.14*x) / (x+1)');
  print "tree: $tree\n";

  require Math::Symbolic::Derivative;
  my $deriv = Math::Symbolic::Derivative::total_derivative($tree, 'x');
  print "deriv $deriv\n";
  $deriv = $deriv->simplify;
  print "deriv $deriv\n";
  exit 0;
}

{
  # by binary width
  require Math::NumSeq::BalancedBinary;
  my $seq = Math::NumSeq::BalancedBinary->new;

  my $count = 0;
  my $target = 4;
  for (;;) {
    my ($i, $value) = $seq->next;
    if ($value >= $target) {
      print "$target  $count\n";
      $count = 0;
      $target *= 4;
    }
    $count++;
  }
  exit 0;
}

{
  # value_to_i_estimate() 2^32
  # 2**32 i=36_714_788