| 1 | # Copyright 2012, 2013, 2014, 2016, 2019, 2020 Kevin Ryde | ||||||||||
| 2 | |||||||||||
| 3 | # This file is part of Math-NumSeq. | ||||||||||
| 4 | # | ||||||||||
| 5 | # Math-NumSeq is free software; you can redistribute it and/or modify | ||||||||||
| 6 | # it under the terms of the GNU General Public License as published by the | ||||||||||
| 7 | # Free Software Foundation; either version 3, or (at your option) any later | ||||||||||
| 8 | # version. | ||||||||||
| 9 | # | ||||||||||
| 10 | # Math-NumSeq is distributed in the hope that it will be useful, but | ||||||||||
| 11 | # WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY | ||||||||||
| 12 | # or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | ||||||||||
| 13 | # for more details. | ||||||||||
| 14 | # | ||||||||||
| 15 | # You should have received a copy of the GNU General Public License along | ||||||||||
| 16 | # with Math-NumSeq. If not, see <http://www.gnu.org/licenses/>. | ||||||||||
| 17 | |||||||||||
| 18 | package Math::NumSeq::RadixConversion; | ||||||||||
| 19 | 1 | ▶ | use 5.004; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 20 | 1 | ▶ | use strict; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 21 | |||||||||||
| 22 | 1 | ▶ | use vars '$VERSION', '@ISA'; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 23 | 1 | $VERSION = 75; | |||||||||
| 24 | |||||||||||
| 25 | 1 | ▶ | use Math::NumSeq; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 26 | 1 | @ISA = ('Math::NumSeq'); | |||||||||
| 27 | 1 | *_is_infinite = \&Math::NumSeq::_is_infinite; | |||||||||
| 28 | 1 | *_to_bigint = \&Math::NumSeq::_to_bigint; | |||||||||
| 29 | |||||||||||
| 30 | 1 | ▶ | use Math::NumSeq::NumAronson 8; # new in v.8 | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 31 | 1 | *_round_down_pow = \&Math::NumSeq::NumAronson::_round_down_pow; | |||||||||
| 32 | |||||||||||
| 33 | # uncomment this to run the ### lines | ||||||||||
| 34 | #use Smart::Comments; | ||||||||||
| 35 | |||||||||||
| 36 | 1 | ▶ | use constant name => Math::NumSeq::__('Radix Conversion'); | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 37 | 1 | ▶ | use constant description => Math::NumSeq::__('Integers converted from one radix into another.'); | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 38 | 1 | ▶ | use constant default_i_start => 0; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 39 | 1 | ▶ | use constant characteristic_increasing => 1; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 40 | 1 | ▶ | use constant characteristic_integer => 1; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 41 | |||||||||||
| 42 | 3 | ▶ | sub values_min { | ||||||||
|
Subroutine
values_min: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||
| 43 | 3 | my ($self) = @_; | |||||||||
| 44 | 3 | return $self->ith($self->i_start); | |||||||||
| 45 | } | ||||||||||
| 46 | 0 | ▶ | sub characteristic_smaller { | ||||||||
|
Subroutine
characteristic_smaller: not called CC=1 SCAR=6.9
Pod
undocumented
| |||||||||||
| 47 | 0 | my ($self) = @_; | |||||||||
| 48 | 0 | return ($self->{'to_radix'} < $self->{'from_radix'}); | |||||||||
| 49 | } | ||||||||||
| 50 | |||||||||||
| 51 | 1 | ▶ | use constant parameter_info_array => | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 52 | [ | ||||||||||
| 53 | { name => 'from_radix', | ||||||||||
| 54 | share_key => 'radix_2', | ||||||||||
| 55 | type => 'integer', | ||||||||||
| 56 | display => Math::NumSeq::__('From Radix'), | ||||||||||
| 57 | default => 2, | ||||||||||
| 58 | minimum => 2, | ||||||||||
| 59 | width => 3, | ||||||||||
| 60 | # description => Math::NumSeq::__('...'), | ||||||||||
| 61 | }, | ||||||||||
| 62 | { name => 'to_radix', | ||||||||||
| 63 | share_key => 'radix', | ||||||||||
| 64 | type => 'integer', | ||||||||||
| 65 | display => Math::NumSeq::__('To Radix'), | ||||||||||
| 66 | default => 10, | ||||||||||
| 67 | minimum => 2, | ||||||||||
| 68 | width => 3, | ||||||||||
| 69 | # description => Math::NumSeq::__('...'), | ||||||||||
| 70 | }, | ||||||||||
| 71 | 1 | ]; | |||||||||
| 72 | |||||||||||
| 73 | |||||||||||
| 74 | #------------------------------------------------------------------------------ | ||||||||||
| 75 | # cf A136399 decimal is not entirely 0,1 digits | ||||||||||
| 76 | # A055983 a(n+1) = a(n) base 10 converted to base 12, repeated conversion | ||||||||||
| 77 | # A032917 decimal digits 1,3 only | ||||||||||
| 78 | # A199341 decimal digits 1,3,4 only | ||||||||||
| 79 | # A032940 base 5 odd positions 0, but counting from top end | ||||||||||
| 80 | # | ||||||||||
| 81 | # A099820 even numbers written in binary | ||||||||||
| 82 | # A099821 odd numbers written in binary | ||||||||||
| 83 | # A001737 squares written in binary | ||||||||||
| 84 | # A031345 primes written in 10 interpret as base 13 | ||||||||||
| 85 | # | ||||||||||
| 86 | |||||||||||
| 87 | 1 | my @oeis_anum; | |||||||||
| 88 | 1 | $oeis_anum[10]->[2] = 'A007088'; # numbers written in base 2, starting n=0 | |||||||||
| 89 | 1 | $oeis_anum[10]->[3] = 'A007089'; # numbers written in base 3, starting n=0 | |||||||||
| 90 | 1 | $oeis_anum[10]->[4] = 'A007090'; # numbers written in base 4, starting n=0 | |||||||||
| 91 | 1 | $oeis_anum[10]->[5] = 'A007091'; # numbers written in base 5, starting n=0 | |||||||||
| 92 | 1 | $oeis_anum[10]->[6] = 'A007092'; # numbers written in base 6, starting n=0 | |||||||||
| 93 | 1 | $oeis_anum[10]->[7] = 'A007093'; # numbers written in base 7, starting n=0 | |||||||||
| 94 | 1 | $oeis_anum[10]->[8] = 'A007094'; # numbers written in base 8, starting n=0 | |||||||||
| 95 | 1 | $oeis_anum[10]->[9] = 'A007095'; # numbers written in base 9, starting n=0 | |||||||||
| 96 | # OEIS-Catalogue: A007088 | ||||||||||
| 97 | # OEIS-Catalogue: A007089 from_radix=3 | ||||||||||
| 98 | # OEIS-Catalogue: A007090 from_radix=4 | ||||||||||
| 99 | # OEIS-Catalogue: A007091 from_radix=5 | ||||||||||
| 100 | # OEIS-Catalogue: A007092 from_radix=6 | ||||||||||
| 101 | # OEIS-Catalogue: A007093 from_radix=7 | ||||||||||
| 102 | # OEIS-Catalogue: A007094 from_radix=8 | ||||||||||
| 103 | # OEIS-Other: A007095 from_radix=9 # in RadixWithoutDigit | ||||||||||
| 104 | |||||||||||
| 105 | 1 | $oeis_anum[4]->[3] = 'A023717'; # base 4 no 3 OFFSET=0 | |||||||||
| 106 | # OEIS-Other: A023717 from_radix=3 to_radix=4 # in RadixWithoutDigit | ||||||||||
| 107 | |||||||||||
| 108 | # Not quite, OFFSET=1 value=0 | ||||||||||
| 109 | # $oeis_anum[5]->[4] = 'A023737'; # base 5 no 4 OFFSET=1 | ||||||||||
| 110 | # # OEIS-Other: A023737 radix=5 digit=4 # base 5 no 4, in RadixWithoutDigit | ||||||||||
| 111 | |||||||||||
| 112 | # $oeis_anum[7]->[6] = 'A020657'; # "no 7-term arithmetic progression" OFFSET=1 | ||||||||||
| 113 | |||||||||||
| 114 | # Not quite, A102489 starts OFFSET=1 value=0 | ||||||||||
| 115 | # $oeis_anum[10]->[16] = 'A102489'; # base 10 treated as base 16 | ||||||||||
| 116 | # # OEIS-Catalogue: A102489 from_radix=10 to_radix=16 | ||||||||||
| 117 | |||||||||||
| 118 | # Not quite, A005836 starts OFFSET=1 value=0 | ||||||||||
| 119 | # $oeis_anum[3]->[2] = 'A005836'; # binary in base 3, base3 without 2s | ||||||||||
| 120 | 1 | $oeis_anum[4]->[2] = 'A000695'; # binary in base 4, digits 0,1 only | |||||||||
| 121 | 1 | $oeis_anum[5]->[2] = 'A033042'; # binary in base 5 | |||||||||
| 122 | 1 | $oeis_anum[6]->[2] = 'A033043'; # binary in base 6 | |||||||||
| 123 | # $oeis_anum[7]->[2] = 'A033044'; # binary in base 7, but OFFSET=1 value=0 | ||||||||||
| 124 | 1 | $oeis_anum[8]->[2] = 'A033045'; # binary in base 8 | |||||||||
| 125 | 1 | $oeis_anum[9]->[2] = 'A033046'; # binary in base 9 | |||||||||
| 126 | 1 | $oeis_anum[11]->[2] = 'A033047'; # binary in base 11 | |||||||||
| 127 | 1 | $oeis_anum[12]->[2] = 'A033048'; # binary in base 12 | |||||||||
| 128 | 1 | $oeis_anum[13]->[2] = 'A033049'; # binary in base 13 | |||||||||
| 129 | 1 | $oeis_anum[14]->[2] = 'A033050'; # binary in base 14 | |||||||||
| 130 | 1 | $oeis_anum[15]->[2] = 'A033051'; # binary in base 15 | |||||||||
| 131 | 1 | $oeis_anum[16]->[2] = 'A033052'; # binary in base 16 | |||||||||
| 132 | # OEIS-Catalogue: A000695 to_radix=4 | ||||||||||
| 133 | # OEIS-Catalogue: A033042 to_radix=5 | ||||||||||
| 134 | # OEIS-Catalogue: A033043 to_radix=6 | ||||||||||
| 135 | # # OEIS-Catalogue: A033044 to_radix=7 # but OFFSET=1 value=0 | ||||||||||
| 136 | # OEIS-Catalogue: A033045 to_radix=8 | ||||||||||
| 137 | # OEIS-Catalogue: A033046 to_radix=9 | ||||||||||
| 138 | # OEIS-Catalogue: A033047 to_radix=11 | ||||||||||
| 139 | # OEIS-Catalogue: A033048 to_radix=12 | ||||||||||
| 140 | # OEIS-Catalogue: A033049 to_radix=13 | ||||||||||
| 141 | # OEIS-Catalogue: A033050 to_radix=14 | ||||||||||
| 142 | # OEIS-Catalogue: A033051 to_radix=15 | ||||||||||
| 143 | # OEIS-Catalogue: A033052 to_radix=16 | ||||||||||
| 144 | |||||||||||
| 145 | |||||||||||
| 146 | 3 | ▶ | sub oeis_anum { | ||||||||
|
Subroutine
oeis_anum: called CC=2 SCAR=7.6
Pod
documented
| |||||||||||
| 147 | 3 | my ($self) = @_; | |||||||||
| 148 | |||||||||||
| 149 | 3 | ▶ | if ($self->{'to_radix'} == $self->{'from_radix'}) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 150 | 0 | return 'A001477'; # all integers 0 up | |||||||||
| 151 | } | ||||||||||
| 152 | # OEIS-Other: A001477 from_radix=10 to_radix=10 | ||||||||||
| 153 | # OEIS-Other: A001477 from_radix=2 to_radix=2 | ||||||||||
| 154 | |||||||||||
| 155 | 3 | return $oeis_anum[$self->{'to_radix'}]->[$self->{'from_radix'}]; | |||||||||
| 156 | } | ||||||||||
| 157 | |||||||||||
| 158 | |||||||||||
| 159 | #------------------------------------------------------------------------------ | ||||||||||
| 160 | |||||||||||
| 161 | 3 | ▶ | sub new { | ||||||||
|
Subroutine
new: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||
| 162 | 3 | my $self = shift->SUPER::new(@_); | |||||||||
| 163 | |||||||||||
| 164 | # Round down to a power of to_radix as the UV limit. For example in | ||||||||||
| 165 | # 32-bits to_radix=10 the limit is 1_000_000_000. Usually a bigger limit | ||||||||||
| 166 | # is possible, but this round-down is an easy calculation. | ||||||||||
| 167 | # | ||||||||||
| 168 | 3 | my ($pow) = _round_down_pow (~0, $self->{'to_radix'}); | |||||||||
| 169 | 3 | $self->{'value_uv_limit'} = $pow; | |||||||||
| 170 | ### value_uv_limit: $self->{'value_uv_limit'} | ||||||||||
| 171 | |||||||||||
| 172 | 3 | return $self; | |||||||||
| 173 | } | ||||||||||
| 174 | |||||||||||
| 175 | 9 | ▶ | sub rewind { | ||||||||
|
Subroutine
rewind: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||
| 176 | 9 | my ($self) = @_; | |||||||||
| 177 | 9 | $self->{'i'} = $self->i_start; | |||||||||
| 178 | } | ||||||||||
| 179 | 108 | ▶ | sub next { | ||||||||
|
Subroutine
next: called CC=2 SCAR=7.2
Pod
documented
| |||||||||||
| 180 | 108 | my ($self) = @_; | |||||||||
| 181 | 108 | my $i = $self->{'i'}++; | |||||||||
| 182 | 108 | my $value = $self->ith($i); | |||||||||
| 183 | 108 | ▶ | if ($value == $self->{'value_uv_limit'}) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 184 | 0 | $self->{'i'} = _to_bigint($self->{'i'}); | |||||||||
| 185 | } | ||||||||||
| 186 | 108 | return ($i, $value); | |||||||||
| 187 | } | ||||||||||
| 188 | |||||||||||
| 189 | # ENHANCE-ME: BigInt use as_bin,oct.hex when to_radix decimal or likewise | ||||||||||
| 190 | # | ||||||||||
| 191 | 282 | ▶ | sub ith { | ||||||||
|
Subroutine
ith: called CC=4 SCAR=14.0
Pod
documented
| |||||||||||
| 192 | 282 | my ($self, $i) = @_; | |||||||||
| 193 | ### RadixConversion ith(): $i | ||||||||||
| 194 | |||||||||||
| 195 | 282 | ▶ | if (_is_infinite($i)) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 196 | 0 | return $i; | |||||||||
| 197 | } | ||||||||||
| 198 | |||||||||||
| 199 | 282 | my $neg; # secret undocumented support for negative i | |||||||||
| 200 | 282 | ▶ | if ($i < 0) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 201 | 9 | $neg = 1; | |||||||||
| 202 | 9 | $i = - $i; | |||||||||
| 203 | } | ||||||||||
| 204 | my $value = _digit_join_lowtohigh | ||||||||||
| 205 | (_digit_split_lowtohigh($i, $self->{'from_radix'}), | ||||||||||
| 206 | 282 | $self->{'to_radix'}); | |||||||||
| 207 | 282 | ▶ | return ($neg ? -$value : $value); | ||||||||
|
Branch: 1 branch
| |||||||||||
| 208 | } | ||||||||||
| 209 | |||||||||||
| 210 | 2629 | ▶ | sub pred { | ||||||||
|
Subroutine
pred: called CC=6 SCAR=17.9
Pod
documented
| |||||||||||
| 211 | 2629 | my ($self, $value) = @_; | |||||||||
| 212 | ### RadixConversion pred(): $value | ||||||||||
| 213 | |||||||||||
| 214 | 2629 | ▶ | if (_is_infinite($value)) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 215 | 0 | return undef; | |||||||||
| 216 | } | ||||||||||
| 217 | { | ||||||||||
| 218 | 2629 | my $int = int($value); | |||||||||
| 219 | 2629 | ▶ | if ($value != $int) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 220 | 1286 | return 0; | |||||||||
| 221 | } | ||||||||||
| 222 | 1343 | $value = $int; | |||||||||
| 223 | } | ||||||||||
| 224 | |||||||||||
| 225 | 1343 | my $from_radix = $self->{'from_radix'}; | |||||||||
| 226 | 1343 | my $to_radix = $self->{'to_radix'}; | |||||||||
| 227 | 1343 | ▶ | if ($to_radix <= $from_radix) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 228 | 44 | return 1; | |||||||||
| 229 | } | ||||||||||
| 230 | |||||||||||
| 231 | 1299 | ▶ | while ($value) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 232 | 1614 | my $digit = $value % $to_radix; | |||||||||
| 233 | 1614 | ▶ | if ($digit >= $from_radix) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 234 | 1258 | return 0; | |||||||||
| 235 | } | ||||||||||
| 236 | 356 | $value = int($value/$to_radix); | |||||||||
| 237 | } | ||||||||||
| 238 | 41 | return 1; | |||||||||
| 239 | } | ||||||||||
| 240 | |||||||||||
| 241 | #------------------------------------------------------------------------------ | ||||||||||
| 242 | # generic | ||||||||||
| 243 | |||||||||||
| 244 | # returning array[0] low digit | ||||||||||
| 245 | 282 | ▶ | sub _digit_split_lowtohigh { | ||||||||
|
Subroutine
_digit_split_lowtohigh: called CC=2 SCAR=6.9
| |||||||||||
| 246 | 282 | my ($n, $radix) = @_; | |||||||||
| 247 | ### _digit_split(): $n | ||||||||||
| 248 | 282 | my @ret; | |||||||||
| 249 | 282 | ▶ | while ($n) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 250 | 608 | push @ret, $n % $radix; | |||||||||
| 251 | 608 | $n = int($n/$radix); | |||||||||
| 252 | } | ||||||||||
| 253 | 282 | return \@ret; | |||||||||
| 254 | } | ||||||||||
| 255 | |||||||||||
| 256 | # taking $aref->[0] low digit | ||||||||||
| 257 | 282 | ▶ | sub _digit_join_lowtohigh { | ||||||||
|
Subroutine
_digit_join_lowtohigh: called CC=2 SCAR=6.9
| |||||||||||
| 258 | 282 | my ($aref, $radix) = @_; | |||||||||
| 259 | 282 | my $n = 0; | |||||||||
| 260 | 282 | ▶ | while (defined (my $digit = pop @$aref)) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 261 | 608 | $n *= $radix; | |||||||||
| 262 | 608 | $n += $digit; | |||||||||
| 263 | } | ||||||||||
| 264 | 282 | return $n; | |||||||||
| 265 | } | ||||||||||
| 266 | |||||||||||
| 267 | 1 | 1; | |||||||||
| 268 | __END__ | ||||||||||