in reply to Re: Can It Be Written In Base X With Only 1s And 0s
in thread Can It Be Written In Base X With Only 1s And 0s

sub make_iter {
   my ($base) = @_;

   my $num = Math::BigInt->new(1);
   my @digits = 1;  # -1 represents zero.
   my @powers = Math::BigInt->new(1);

   return sub {
      if ($digits[-1] > 0) {
         push @digits, -1;
         push @powers, $powers[-1] * $base;
      }

      for (0..$#digits) {
         $digits[$_] = -$digits[$_];
         $num += $digits[$_] * $powers[$_];
         return $num if $digits[$_] > 0;
      }
   };
}

[download]
is probably faster as 
sub make_iter {
   my ($base) = @_;

   my $num = Math::BigInt->new(1);

   return sub {
      $num->binc;
      return Math::BigInt->new( $num->as_bin() =~ s/^0?b//r );
   };
}

[download]
with a fast back-end.

Replies are listed 'Best First'.
Re^3: Can It Be Written In Base X With Only 1s And 0s
by QM (Parson) on Jun 16, 2015 at 11:22 UTC
    I'm confused about this line: 
    return Math::BigInt->new( $num->as_bin() =~ s/^0?b//r );

    [download]

    It seems to be taking the binary representation, and making a new object in base 10, and returning that?

    -QM
    --
    Quantum Mechanics: The dreams stuff is made of

[reply]
[d/l]
      oops, yeah, that's what it does, but it should be base $base instead of base 10. And M::BI doesn't have a way of doing that.
[reply]
        How about a roll-you-own binary string to base converter? 
        our $ZERO = Math::BigInt->new(0);
our $ONE = $ZERO + 1;

# Convert a bitstring (only 1s and 0s) to a number,
# as if it were a representation of the given base.
sub bitstring_to_base {
    my $result = $ZERO;
    my $pow    = $ONE;

    for my $bit (reverse split '', $_[0]) {
        $result += $pow if $bit;
        $pow *= $_[1];
    }
    return $result;
}

# Skips over 0 and 1.
sub make_iter {
   my ($base) = @_;

   my $num = Math::BigInt->new(1);

   return sub {
      $num->binc;
      return Math::BigInt->new(
          bitstring_to_base($num->as_bin() =~ s/^0?b//r,
                            $base)
      );
   };
}

        [download]

        Also, the line in make_iter could take a value other than 1, as a power-of-ten starting point in a search: 

        my $num = Math::BigInt->new("1" . ("0" x (ARGV[1] // 0)));

        [download]

        -QM
        --
        Quantum Mechanics: The dreams stuff is made of

[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom