File Coverage

blib/lib/Math/PlanePath/Base/Digits.pm

Criterion	Covered	Total	%
statement	95	97	97.9
branch	40	44	90.9
condition	11	15	73.3
subroutine	12	12	100.0
pod	5	5	100.0
total	163	173	94.2

# Copyright 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018 Kevin Ryde

# This file is part of Math-PlanePath.
#
# Math-PlanePath is free software; you can redistribute it and/or modify it
# under the terms of the GNU General Public License as published by the Free
# Software Foundation; either version 3, or (at your option) any later
# version.
#
# Math-PlanePath is distributed in the hope that it will be useful, but
# WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
# or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
# for more details.
#
# You should have received a copy of the GNU General Public License along
# with Math-PlanePath.  If not, see .


#
# bit_join_lowtohigh


package Math::PlanePath::Base::Digits;
use 5.004;
use strict;

use vars '$VERSION','@ISA','@EXPORT_OK';
$VERSION = 127;

use Exporter;
@ISA = ('Exporter');
@EXPORT_OK = ('parameter_info_array',
              'bit_split_lowtohigh',
              'digit_split_lowtohigh',
              'digit_join_lowtohigh',
              'round_down_pow',
              'round_up_pow');

# uncomment this to run the ### lines
# use Smart::Comments;


use constant parameter_info_radix2 => { name      => 'radix',
                                        share_key => 'radix_2',
                                        display   => 'Radix',
                                        type      => 'integer',
                                        minimum   => 2,
                                        default   => 2,
                                        width     => 3,
                                        description => 'Radix (number base).',
                                      };
use constant parameter_info_array => [ parameter_info_radix2() ];


#------------------------------------------------------------------------------

# ENHANCE-ME: Sometimes the $pow value is not wanted,
# eg. SierpinskiArrowhead, though that tends to be approximation code rather
# than exact range calculations etc.
#
sub round_down_pow {
  my ($n, $base) = @_;
  ### round_down_pow(): "$n base $base"

  # only for integer bases
  ### assert: $base == int($base)

  if ($n < $base) {
    return (1, 0);
  }

  # Math::BigInt and Math::BigRat overloaded log() return NaN, use integer
  # based blog()
  if (ref $n) {
    if ($n->isa('Math::BigRat')) {
      $n = int($n);
    }
    if ($n->isa('Math::BigInt') || $n->isa('Math::BigInt::Lite')) {
      ### use blog() ...
      my $exp = $n->copy->blog($base);
      ### exp: "$exp"
      return (Math::BigInt->new(1)->blsft($exp,$base),
              $exp);
    }
  }

  my $exp = int(log($n)/log($base));
  my $pow = $base**$exp;
  ### n:   ref($n)."  $n"
  ### exp: ref($exp)."  $exp"
  ### pow: ref($pow)."  $pow"

  # check how $pow actually falls against $n, not sure should trust float
  # rounding in log()/log($base)
  # Crib: $n as first arg in case $n==BigFloat and $pow==BigInt
  if ($n < $pow) {
    ### hmm, int(log) too big, decrease ...
    $exp -= 1;
    $pow = $base**$exp;
  } elsif ($n >= $base*$pow) {
    ### hmm, int(log) too small, increase ...
    $exp += 1;
    $pow *= $base;
  }

  ### result ...
  ### pow: "$pow"
  ### exp: "$exp"
  ### $exp
  return ($pow, $exp);
}

sub round_up_pow {
  my ($n, $base) = @_;
  ### round_up_pow(): "$n base $base"

  # only for integer bases
  ### assert: $base == int($base)

  if ($n < 1) {
    return (1, 0);
  }

  # Math::BigInt and Math::BigRat overloaded log() return NaN, use integer
  # based blog()
  if (ref $n) {
    ### $n
    if ($n->isa('Math::BigRat')) {
      $n = int($n);
    }
    if ($n->isa('Math::BigInt') || $n->isa('Math::BigInt::Lite')) {
      ### use blog(): ref $n
      my $exp = $n->copy->blog($base);
      ### exp: $exp

      my $pow = (ref $n)->new(1)->blsft($exp,$base);
      # Crib: must have $n first to have Math::BigInt::Lite method preferred
      if ($n > $pow) {
        ### blog too small, increase ...
        $pow *= $base;
        $exp += 1;
      }
      return ($pow, $exp);
    }
  }

  my $exp = int(log($n)/log($base) + 1);
  my $pow = $base**$exp;
  ### n:   ref($n)."  $n"
  ### exp: ref($exp)."  $exp"
  ### pow: ref($pow)."  $pow"

  # check how $pow actually falls against $n, not sure should trust float
  # rounding in log()/log($base)
  # Crib: $n as first arg in case $n==BigFloat and $pow==BigInt
  if ($exp > 0 && $n <= $pow/$base) {
    ### hmm, int(log) too big, decrease...
    $exp -= 1;
    $pow = $base**$exp;
  } elsif ($n > $pow) {
    ### hmm, int(log)+1 too small, increase...
    $exp += 1;
    $pow *= $base;
  }
  return ($pow, $exp);
}

#------------------------------------------------------------------------------
{
  my %binary_to_base4 = ('00' => '0',
                         '01' => '1',
                         '10' => '2',
                         '11' => '3');
  my @bigint_coderef;
  $bigint_coderef[4] = sub {
    (my $str = $_[0]->as_bin) =~ s/^0b//; # strip leading 0b
    if (length($str) & 1) {
      $str = "0$str";
    }
    $str =~ s/(..)/$binary_to_base4{$1}/ge;
    return reverse split //, $str;
  };
  $bigint_coderef[8] = sub {
    (my $str = $_[0]->as_oct) =~ s/^0//;  # strip leading 0
    return reverse split //, $str;
  };
  $bigint_coderef[10] = sub {
    return reverse split //, $_[0]->bstr;
  };
  $bigint_coderef[16] = sub {
    (my $str = $_[0]->as_hex) =~ s/^0x//;  # strip leading 0x
    return reverse map {hex} split //, $str;
  };

  # In _divrem() and _digit_split_lowtohigh() divide using rem=n%d then
  # q=(n-rem)/d so that quotient is an exact division.  If it's not exact
  # then goes to float and loses precision if UV=64bit NV=53bit.

  sub digit_split_lowtohigh {
    my ($n, $radix) = @_;
    ### _digit_split_lowtohigh(): $n

    $n || return; # don't return '0' from BigInt stringize
    if ($radix == 2) {
      return bit_split_lowtohigh($n);
    }

    my @ret;
    if (ref $n && $n->isa('Math::BigInt')) {
      if (my $coderef = $bigint_coderef[$radix]) {
        return $coderef->($_[0]);
      }
      $n = $n->copy; # for bdiv() modification
      do {
        (undef, my $digit) = $n->bdiv($radix);
        push @ret, $digit;
      } while ($n);
      if ($radix < 1_000_000) {  # plain scalars if fit
        foreach (@ret) {
          $_ = $_->numify;  # mutate array
        }
      }

    } else {
      do {
        my $digit = $n % $radix;
        push @ret, $digit;
        $n = int(($n - $digit) / $radix);
      } while ($n > 0);
    }

    return @ret;   # array[0] low digit
  }
}

# 2**32 on a 32-bit UV, or 2**64 on 64-bit
use constant 1.02 _UV_MAX_PLUS_1 => ((~0 >> 1) + 1) * 2.0;

sub bit_split_lowtohigh {
  my ($n) = @_;
  my @ret;
  if ($n >= 1) {
    if (ref $n && $n->isa('Math::BigInt')) {
      (my $str = $n->as_bin) =~ s/^0b//;  # strip leading 0b
      return reverse split //, $str;
    }
    if ($n <= _UV_MAX_PLUS_1) {
      return reverse split //, sprintf('%b',$n);
    }
    do {
      my $digit = $n % 2;
      push @ret, $digit;
      $n = int(($n - $digit) / 2);
    } while ($n);
  }
  return @ret;   # array[0] low digit
}


#------------------------------------------------------------------------------
# $aref->[0] low digit
# ENHANCE-ME: BigInt new(), from_bin(), from_oct(), from_hex()

sub digit_join_lowtohigh {
  my ($aref, $radix, $zero) = @_;

  ### digit_join_lowtohigh() ...
  ### $aref
  ### $radix
  ### $zero

  my $n = (defined $zero ? $zero : 0);
  foreach my $digit (reverse @$aref) { # high to low
    ### $n
    $n *= $radix;
    $n += $digit;
  }
  ### $n
  return $n;
}


1;
__END__