lib/Math/BigInt.pm

   1 package Math::BigInt;
   2
   3 #
   4 # "Mike had an infinite amount to do and a negative amount of time in which
   5 # to do it." - Before and After
   6 #
   7
   8 # The following hash values are used:
   9 #   value: unsigned int with actual value (as a Math::BigInt::Calc or similiar)
  10 #   sign : +,-,NaN,+inf,-inf
  11 #   _a   : accuracy
  12 #   _p   : precision
  13 #   _f   : flags, used by MBF to flag parts of a float as untouchable
  14
  15 # Remember not to take shortcuts ala $xs = $x->{value}; $CALC->foo($xs); since
  16 # underlying lib might change the reference!
  17
  18 my $class = "Math::BigInt";
  19 require 5.005;
  20
  21 $VERSION = '1.63';
  22 use Exporter;
  23 @ISA =       qw( Exporter );
  24 @EXPORT_OK = qw( objectify _swap bgcd blcm);
  25 use vars qw/$round_mode $accuracy $precision $div_scale $rnd_mode/;
  26 use vars qw/$upgrade $downgrade/;
  27 use strict;
  28
  29 # Inside overload, the first arg is always an object. If the original code had
  30 # it reversed (like $x = 2 * $y), then the third paramater indicates this
  31 # swapping. To make it work, we use a helper routine which not only reswaps the
  32 # params, but also makes a new object in this case. See _swap() for details,
  33 # especially the cases of operators with different classes.
  34
  35 # For overloaded ops with only one argument we simple use $_[0]->copy() to
  36 # preserve the argument.
  37
  38 # Thus inheritance of overload operators becomes possible and transparent for
  39 # our subclasses without the need to repeat the entire overload section there.
  40
  41 use overload
  42 '='     =>      sub { $_[0]->copy(); },
  43
  44 # '+' and '-' do not use _swap, since it is a triffle slower. If you want to
  45 # override _swap (if ever), then override overload of '+' and '-', too!
  46 # for sub it is a bit tricky to keep b: b-a => -a+b
  47 '-'     =>      sub { my $c = $_[0]->copy; $_[2] ?
  48                    $c->bneg()->badd($_[1]) :
  49                    $c->bsub( $_[1]) },
  50 '+'     =>      sub { $_[0]->copy()->badd($_[1]); },
  51
  52 # some shortcuts for speed (assumes that reversed order of arguments is routed
  53 # to normal '+' and we thus can always modify first arg. If this is changed,
  54 # this breaks and must be adjusted.)
  55 '+='    =>      sub { $_[0]->badd($_[1]); },
  56 '-='    =>      sub { $_[0]->bsub($_[1]); },
  57 '*='    =>      sub { $_[0]->bmul($_[1]); },
  58 '/='    =>      sub { scalar $_[0]->bdiv($_[1]); },
  59 '%='    =>      sub { $_[0]->bmod($_[1]); },
  60 '^='    =>      sub { $_[0]->bxor($_[1]); },
  61 '&='    =>      sub { $_[0]->band($_[1]); },
  62 '|='    =>      sub { $_[0]->bior($_[1]); },
  63 '**='   =>      sub { $_[0]->bpow($_[1]); },
  64
  65 # not supported by Perl yet
  66 '..'    =>      \&_pointpoint,
  67
  68 '<=>'   =>      sub { $_[2] ?
  69                       ref($_[0])->bcmp($_[1],$_[0]) :
  70                       $_[0]->bcmp($_[1])},
  71 'cmp'   =>      sub {
  72          $_[2] ?
  73                "$_[1]" cmp $_[0]->bstr() :
  74                $_[0]->bstr() cmp "$_[1]" },
  75
  76 'log'   =>      sub { $_[0]->copy()->blog(); },
  77 'int'   =>      sub { $_[0]->copy(); },
  78 'neg'   =>      sub { $_[0]->copy()->bneg(); },
  79 'abs'   =>      sub { $_[0]->copy()->babs(); },
  80 'sqrt'  =>      sub { $_[0]->copy()->bsqrt(); },
  81 '~'     =>      sub { $_[0]->copy()->bnot(); },
  82
  83 '*'     =>      sub { my @a = ref($_[0])->_swap(@_); $a[0]->bmul($a[1]); },
  84 '/'     =>      sub { my @a = ref($_[0])->_swap(@_);scalar $a[0]->bdiv($a[1]);},
  85 '%'     =>      sub { my @a = ref($_[0])->_swap(@_); $a[0]->bmod($a[1]); },
  86 '**'    =>      sub { my @a = ref($_[0])->_swap(@_); $a[0]->bpow($a[1]); },
  87 '<<'    =>      sub { my @a = ref($_[0])->_swap(@_); $a[0]->blsft($a[1]); },
  88 '>>'    =>      sub { my @a = ref($_[0])->_swap(@_); $a[0]->brsft($a[1]); },
  89
  90 '&'     =>      sub { my @a = ref($_[0])->_swap(@_); $a[0]->band($a[1]); },
  91 '|'     =>      sub { my @a = ref($_[0])->_swap(@_); $a[0]->bior($a[1]); },
  92 '^'     =>      sub { my @a = ref($_[0])->_swap(@_); $a[0]->bxor($a[1]); },
  93
  94 # can modify arg of ++ and --, so avoid a new-copy for speed, but don't
  95 # use $_[0]->__one(), it modifies $_[0] to be 1!
  96 '++'    =>      sub { $_[0]->binc() },
  97 '--'    =>      sub { $_[0]->bdec() },
  98
  99 # if overloaded, O(1) instead of O(N) and twice as fast for small numbers
 100 'bool'  =>      sub {
 101   # this kludge is needed for perl prior 5.6.0 since returning 0 here fails :-/
 102   # v5.6.1 dumps on that: return !$_[0]->is_zero() || undef;                :-(
 103   my $t = !$_[0]->is_zero();
 104   undef $t if $t == 0;
 105   $t;
 106   },
 107
 108 # the original qw() does not work with the TIESCALAR below, why?
 109 # Order of arguments unsignificant
 110 '""' => sub { $_[0]->bstr(); },
 111 '0+' => sub { $_[0]->numify(); }
 112 ;
 113
 114 ##############################################################################
 115 # global constants, flags and accessory
 116
 117 use constant MB_NEVER_ROUND => 0x0001;
 118
 119 my $NaNOK=1;                            # are NaNs ok?
 120 my $nan = 'NaN';                        # constants for easier life
 121
 122 my $CALC = 'Math::BigInt::Calc';        # module to do low level math
 123 my $IMPORT = 0;                         # did import() yet?
 124
 125 $round_mode = 'even'; # one of 'even', 'odd', '+inf', '-inf', 'zero' or 'trunc'
 126 $accuracy   = undef;
 127 $precision  = undef;
 128 $div_scale  = 40;
 129
 130 $upgrade = undef;                       # default is no upgrade
 131 $downgrade = undef;                     # default is no downgrade
 132
 133 ##############################################################################
 134 # the old code had $rnd_mode, so we need to support it, too
 135
 136 $rnd_mode   = 'even';
 137 sub TIESCALAR  { my ($class) = @_; bless \$round_mode, $class; }
 138 sub FETCH      { return $round_mode; }
 139 sub STORE      { $rnd_mode = $_[0]->round_mode($_[1]); }
 140
 141 BEGIN { tie $rnd_mode, 'Math::BigInt'; }
 142
 143 ##############################################################################
 144
 145 sub round_mode
 146   {
 147   no strict 'refs';
 148   # make Class->round_mode() work
 149   my $self = shift;
 150   my $class = ref($self) || $self || __PACKAGE__;
 151   if (defined $_[0])
 152     {
 153     my $m = shift;
 154     die "Unknown round mode $m"
 155      if $m !~ /^(even|odd|\+inf|\-inf|zero|trunc)$/;
 156     return ${"${class}::round_mode"} = $m;
 157     }
 158   return ${"${class}::round_mode"};
 159   }
 160
 161 sub upgrade
 162   {
 163   no strict 'refs';
 164   # make Class->upgrade() work
 165   my $self = shift;
 166   my $class = ref($self) || $self || __PACKAGE__;
 167   # need to set new value?
 168   if (@_ > 0)
 169     {
 170     my $u = shift;
 171     return ${"${class}::upgrade"} = $u;
 172     }
 173   return ${"${class}::upgrade"};
 174   }
 175
 176 sub downgrade
 177   {
 178   no strict 'refs';
 179   # make Class->downgrade() work
 180   my $self = shift;
 181   my $class = ref($self) || $self || __PACKAGE__;
 182   # need to set new value?
 183   if (@_ > 0)
 184     {
 185     my $u = shift;
 186     return ${"${class}::downgrade"} = $u;
 187     }
 188   return ${"${class}::downgrade"};
 189   }
 190
 191 sub div_scale
 192   {
 193   no strict 'refs';
 194   # make Class->round_mode() work
 195   my $self = shift;
 196   my $class = ref($self) || $self || __PACKAGE__;
 197   if (defined $_[0])
 198     {
 199     die ('div_scale must be greater than zero') if $_[0] < 0;
 200     ${"${class}::div_scale"} = shift;
 201     }
 202   return ${"${class}::div_scale"};
 203   }
 204
 205 sub accuracy
 206   {
 207   # $x->accuracy($a);           ref($x) $a
 208   # $x->accuracy();             ref($x)
 209   # Class->accuracy();          class
 210   # Class->accuracy($a);        class $a
 211
 212   my $x = shift;
 213   my $class = ref($x) || $x || __PACKAGE__;
 214
 215   no strict 'refs';
 216   # need to set new value?
 217   if (@_ > 0)
 218     {
 219     my $a = shift;
 220     die ('accuracy must not be zero') if defined $a && $a == 0;
 221     if (ref($x))
 222       {
 223       # $object->accuracy() or fallback to global
 224       $x->bround($a) if defined $a;
 225       $x->{_a} = $a;                    # set/overwrite, even if not rounded
 226       $x->{_p} = undef;                 # clear P
 227       }
 228     else
 229       {
 230       # set global
 231       ${"${class}::accuracy"} = $a;
 232       ${"${class}::precision"} = undef; # clear P
 233       }
 234     return $a;                          # shortcut
 235     }
 236
 237   my $r;
 238   # $object->accuracy() or fallback to global
 239   $r = $x->{_a} if ref($x);
 240   # but don't return global undef, when $x's accuracy is 0!
 241   $r = ${"${class}::accuracy"} if !defined $r;
 242   $r;
 243   }
 244
 245 sub precision
 246   {
 247   # $x->precision($p);          ref($x) $p
 248   # $x->precision();            ref($x)
 249   # Class->precision();         class
 250   # Class->precision($p);       class $p
 251
 252   my $x = shift;
 253   my $class = ref($x) || $x || __PACKAGE__;
 254
 255   no strict 'refs';
 256   # need to set new value?
 257   if (@_ > 0)
 258     {
 259     my $p = shift;
 260     if (ref($x))
 261       {
 262       # $object->precision() or fallback to global
 263       $x->bfround($p) if defined $p;
 264       $x->{_p} = $p;                    # set/overwrite, even if not rounded
 265       $x->{_a} = undef;                 # clear A
 266       }
 267     else
 268       {
 269       # set global
 270       ${"${class}::precision"} = $p;
 271       ${"${class}::accuracy"} = undef;  # clear A
 272       }
 273     return $p;                          # shortcut
 274     }
 275
 276   my $r;
 277   # $object->precision() or fallback to global
 278   $r = $x->{_p} if ref($x);
 279   # but don't return global undef, when $x's precision is 0!
 280   $r = ${"${class}::precision"} if !defined $r;
 281   $r;
 282   }
 283
 284 sub config
 285   {
 286   # return (later set?) configuration data as hash ref
 287   my $class = shift || 'Math::BigInt';
 288
 289   no strict 'refs';
 290   my $lib = $CALC;
 291   my $cfg = {
 292     lib => $lib,
 293     lib_version => ${"${lib}::VERSION"},
 294     class => $class,
 295     };
 296   foreach (
 297    qw/upgrade downgrade precision accuracy round_mode VERSION div_scale/)
 298     {
 299     $cfg->{lc($_)} = ${"${class}::$_"};
 300     };
 301   $cfg;
 302   }
 303
 304 sub _scale_a
 305   {
 306   # select accuracy parameter based on precedence,
 307   # used by bround() and bfround(), may return undef for scale (means no op)
 308   my ($x,$s,$m,$scale,$mode) = @_;
 309   $scale = $x->{_a} if !defined $scale;
 310   $scale = $s if (!defined $scale);
 311   $mode = $m if !defined $mode;
 312   return ($scale,$mode);
 313   }
 314
 315 sub _scale_p
 316   {
 317   # select precision parameter based on precedence,
 318   # used by bround() and bfround(), may return undef for scale (means no op)
 319   my ($x,$s,$m,$scale,$mode) = @_;
 320   $scale = $x->{_p} if !defined $scale;
 321   $scale = $s if (!defined $scale);
 322   $mode = $m if !defined $mode;
 323   return ($scale,$mode);
 324   }
 325
 326 ##############################################################################
 327 # constructors
 328
 329 sub copy
 330   {
 331   my ($c,$x);
 332   if (@_ > 1)
 333     {
 334     # if two arguments, the first one is the class to "swallow" subclasses
 335     ($c,$x) = @_;
 336     }
 337   else
 338     {
 339     $x = shift;
 340     $c = ref($x);
 341     }
 342   return unless ref($x); # only for objects
 343
 344   my $self = {}; bless $self,$c;
 345   my $r;
 346   foreach my $k (keys %$x)
 347     {
 348     if ($k eq 'value')
 349       {
 350       $self->{value} = $CALC->_copy($x->{value}); next;
 351       }
 352     if (!($r = ref($x->{$k})))
 353       {
 354       $self->{$k} = $x->{$k}; next;
 355       }
 356     if ($r eq 'SCALAR')
 357       {
 358       $self->{$k} = \${$x->{$k}};
 359       }
 360     elsif ($r eq 'ARRAY')
 361       {
 362       $self->{$k} = [ @{$x->{$k}} ];
 363       }
 364     elsif ($r eq 'HASH')
 365       {
 366       # only one level deep!
 367       foreach my $h (keys %{$x->{$k}})
 368         {
 369         $self->{$k}->{$h} = $x->{$k}->{$h};
 370         }
 371       }
 372     else # normal ref
 373       {
 374       my $xk = $x->{$k};
 375       if ($xk->can('copy'))
 376         {
 377         $self->{$k} = $xk->copy();
 378         }
 379       else
 380         {
 381         $self->{$k} = $xk->new($xk);
 382         }
 383       }
 384     }
 385   $self;
 386   }
 387
 388 sub new
 389   {
 390   # create a new BigInt object from a string or another BigInt object.
 391   # see hash keys documented at top
 392
 393   # the argument could be an object, so avoid ||, && etc on it, this would
 394   # cause costly overloaded code to be called. The only allowed ops are
 395   # ref() and defined.
 396
 397   my ($class,$wanted,$a,$p,$r) = @_;
 398
 399   # avoid numify-calls by not using || on $wanted!
 400   return $class->bzero($a,$p) if !defined $wanted;      # default to 0
 401   return $class->copy($wanted,$a,$p,$r)
 402    if ref($wanted) && $wanted->isa($class);             # MBI or subclass
 403
 404   $class->import() if $IMPORT == 0;             # make require work
 405
 406   my $self = bless {}, $class;
 407
 408   # shortcut for "normal" numbers
 409   if ((!ref $wanted) && ($wanted =~ /^([+-]?)[1-9][0-9]*\z/))
 410     {
 411     $self->{sign} = $1 || '+';
 412     my $ref = \$wanted;
 413     if ($wanted =~ /^[+-]/)
 414      {
 415       # remove sign without touching wanted to make it work with constants
 416       my $t = $wanted; $t =~ s/^[+-]//; $ref = \$t;
 417       }
 418     $self->{value} = $CALC->_new($ref);
 419     no strict 'refs';
 420     if ( (defined $a) || (defined $p)
 421         || (defined ${"${class}::precision"})
 422         || (defined ${"${class}::accuracy"})
 423        )
 424       {
 425       $self->round($a,$p,$r) unless (@_ == 4 && !defined $a && !defined $p);
 426       }
 427     return $self;
 428     }
 429
 430   # handle '+inf', '-inf' first
 431   if ($wanted =~ /^[+-]?inf$/)
 432     {
 433     $self->{value} = $CALC->_zero();
 434     $self->{sign} = $wanted; $self->{sign} = '+inf' if $self->{sign} eq 'inf';
 435     return $self;
 436     }
 437   # split str in m mantissa, e exponent, i integer, f fraction, v value, s sign
 438   my ($mis,$miv,$mfv,$es,$ev) = _split(\$wanted);
 439   if (!ref $mis)
 440     {
 441     die "$wanted is not a number initialized to $class" if !$NaNOK;
 442     #print "NaN 1\n";
 443     $self->{value} = $CALC->_zero();
 444     $self->{sign} = $nan;
 445     return $self;
 446     }
 447   if (!ref $miv)
 448     {
 449     # _from_hex or _from_bin
 450     $self->{value} = $mis->{value};
 451     $self->{sign} = $mis->{sign};
 452     return $self;       # throw away $mis
 453     }
 454   # make integer from mantissa by adjusting exp, then convert to bigint
 455   $self->{sign} = $$mis;                        # store sign
 456   $self->{value} = $CALC->_zero();              # for all the NaN cases
 457   my $e = int("$$es$$ev");                      # exponent (avoid recursion)
 458   if ($e > 0)
 459     {
 460     my $diff = $e - CORE::length($$mfv);
 461     if ($diff < 0)                              # Not integer
 462       {
 463       #print "NOI 1\n";
 464       return $upgrade->new($wanted,$a,$p,$r) if defined $upgrade;
 465       $self->{sign} = $nan;
 466       }
 467     else                                        # diff >= 0
 468       {
 469       # adjust fraction and add it to value
 470       # print "diff > 0 $$miv\n";
 471       $$miv = $$miv . ($$mfv . '0' x $diff);
 472       }
 473     }
 474   else
 475     {
 476     if ($$mfv ne '')                            # e <= 0
 477       {
 478       # fraction and negative/zero E => NOI
 479       #print "NOI 2 \$\$mfv '$$mfv'\n";
 480       return $upgrade->new($wanted,$a,$p,$r) if defined $upgrade;
 481       $self->{sign} = $nan;
 482       }
 483     elsif ($e < 0)
 484       {
 485       # xE-y, and empty mfv
 486       #print "xE-y\n";
 487       $e = abs($e);
 488       if ($$miv !~ s/0{$e}$//)          # can strip so many zero's?
 489         {
 490         #print "NOI 3\n";
 491         return $upgrade->new($wanted,$a,$p,$r) if defined $upgrade;
 492         $self->{sign} = $nan;
 493         }
 494       }
 495     }
 496   $self->{sign} = '+' if $$miv eq '0';                  # normalize -0 => +0
 497   $self->{value} = $CALC->_new($miv) if $self->{sign} =~ /^[+-]$/;
 498   # if any of the globals is set, use them to round and store them inside $self
 499   # do not round for new($x,undef,undef) since that is used by MBF to signal
 500   # no rounding
 501   $self->round($a,$p,$r) unless @_ == 4 && !defined $a && !defined $p;
 502   $self;
 503   }
 504
 505 sub bnan
 506   {
 507   # create a bigint 'NaN', if given a BigInt, set it to 'NaN'
 508   my $self = shift;
 509   $self = $class if !defined $self;
 510   if (!ref($self))
 511     {
 512     my $c = $self; $self = {}; bless $self, $c;
 513     }
 514   $self->import() if $IMPORT == 0;              # make require work
 515   return if $self->modify('bnan');
 516   my $c = ref($self);
 517   if ($self->can('_bnan'))
 518     {
 519     # use subclass to initialize
 520     $self->_bnan();
 521     }
 522   else
 523     {
 524     # otherwise do our own thing
 525     $self->{value} = $CALC->_zero();
 526     }
 527   $self->{sign} = $nan;
 528   delete $self->{_a}; delete $self->{_p};       # rounding NaN is silly
 529   return $self;
 530   }
 531
 532 sub binf
 533   {
 534   # create a bigint '+-inf', if given a BigInt, set it to '+-inf'
 535   # the sign is either '+', or if given, used from there
 536   my $self = shift;
 537   my $sign = shift; $sign = '+' if !defined $sign || $sign !~ /^-(inf)?$/;
 538   $self = $class if !defined $self;
 539   if (!ref($self))
 540     {
 541     my $c = $self; $self = {}; bless $self, $c;
 542     }
 543   $self->import() if $IMPORT == 0;              # make require work
 544   return if $self->modify('binf');
 545   my $c = ref($self);
 546   if ($self->can('_binf'))
 547     {
 548     # use subclass to initialize
 549     $self->_binf();
 550     }
 551   else
 552     {
 553     # otherwise do our own thing
 554     $self->{value} = $CALC->_zero();
 555     }
 556   $sign = $sign . 'inf' if $sign !~ /inf$/;     # - => -inf
 557   $self->{sign} = $sign;
 558   ($self->{_a},$self->{_p}) = @_;               # take over requested rounding
 559   return $self;
 560   }
 561
 562 sub bzero
 563   {
 564   # create a bigint '+0', if given a BigInt, set it to 0
 565   my $self = shift;
 566   $self = $class if !defined $self;
 567
 568   if (!ref($self))
 569     {
 570     my $c = $self; $self = {}; bless $self, $c;
 571     }
 572   $self->import() if $IMPORT == 0;              # make require work
 573   return if $self->modify('bzero');
 574
 575   if ($self->can('_bzero'))
 576     {
 577     # use subclass to initialize
 578     $self->_bzero();
 579     }
 580   else
 581     {
 582     # otherwise do our own thing
 583     $self->{value} = $CALC->_zero();
 584     }
 585   $self->{sign} = '+';
 586   if (@_ > 0)
 587     {
 588     if (@_ > 3)
 589       {
 590       # call like: $x->bzero($a,$p,$r,$y);
 591       ($self,$self->{_a},$self->{_p}) = $self->_find_round_parameters(@_);
 592       }
 593     else
 594       {
 595       $self->{_a} = $_[0]
 596        if ( (!defined $self->{_a}) || (defined $_[0] && $_[0] > $self->{_a}));
 597       $self->{_p} = $_[1]
 598        if ( (!defined $self->{_p}) || (defined $_[1] && $_[1] > $self->{_p}));
 599       }
 600     }
 601   $self;
 602   }
 603
 604 sub bone
 605   {
 606   # create a bigint '+1' (or -1 if given sign '-'),
 607   # if given a BigInt, set it to +1 or -1, respecively
 608   my $self = shift;
 609   my $sign = shift; $sign = '+' if !defined $sign || $sign ne '-';
 610   $self = $class if !defined $self;
 611
 612   if (!ref($self))
 613     {
 614     my $c = $self; $self = {}; bless $self, $c;
 615     }
 616   $self->import() if $IMPORT == 0;              # make require work
 617   return if $self->modify('bone');
 618
 619   if ($self->can('_bone'))
 620     {
 621     # use subclass to initialize
 622     $self->_bone();
 623     }
 624   else
 625     {
 626     # otherwise do our own thing
 627     $self->{value} = $CALC->_one();
 628     }
 629   $self->{sign} = $sign;
 630   if (@_ > 0)
 631     {
 632     if (@_ > 3)
 633       {
 634       # call like: $x->bone($sign,$a,$p,$r,$y);
 635       ($self,$self->{_a},$self->{_p}) = $self->_find_round_parameters(@_);
 636       }
 637     else
 638       {
 639       $self->{_a} = $_[0]
 640        if ( (!defined $self->{_a}) || (defined $_[0] && $_[0] > $self->{_a}));
 641       $self->{_p} = $_[1]
 642        if ( (!defined $self->{_p}) || (defined $_[1] && $_[1] > $self->{_p}));
 643       }
 644     }
 645   $self;
 646   }
 647
 648 ##############################################################################
 649 # string conversation
 650
 651 sub bsstr
 652   {
 653   # (ref to BFLOAT or num_str ) return num_str
 654   # Convert number from internal format to scientific string format.
 655   # internal format is always normalized (no leading zeros, "-0E0" => "+0E0")
 656   my $x = shift; $class = ref($x) || $x; $x = $class->new(shift) if !ref($x);
 657   # my ($self,$x) = ref($_[0]) ? (ref($_[0]),$_[0]) : objectify(1,@_);
 658
 659   if ($x->{sign} !~ /^[+-]$/)
 660     {
 661     return $x->{sign} unless $x->{sign} eq '+inf';      # -inf, NaN
 662     return 'inf';                                       # +inf
 663     }
 664   my ($m,$e) = $x->parts();
 665   my $sign = 'e+'; # e can only be positive
 666   return $m->bstr().$sign.$e->bstr();
 667   }
 668
 669 sub bstr
 670   {
 671   # make a string from bigint object
 672   my $x = shift; $class = ref($x) || $x; $x = $class->new(shift) if !ref($x);
 673   # my ($self,$x) = ref($_[0]) ? (ref($_[0]),$_[0]) : objectify(1,@_);
 674
 675   if ($x->{sign} !~ /^[+-]$/)
 676     {
 677     return $x->{sign} unless $x->{sign} eq '+inf';      # -inf, NaN
 678     return 'inf';                                       # +inf
 679     }
 680   my $es = ''; $es = $x->{sign} if $x->{sign} eq '-';
 681   return $es.${$CALC->_str($x->{value})};
 682   }
 683
 684 sub numify
 685   {
 686   # Make a "normal" scalar from a BigInt object
 687   my $x = shift; $x = $class->new($x) unless ref $x;
 688
 689   return $x->bstr() if $x->{sign} !~ /^[+-]$/;
 690   my $num = $CALC->_num($x->{value});
 691   return -$num if $x->{sign} eq '-';
 692   $num;
 693   }
 694
 695 ##############################################################################
 696 # public stuff (usually prefixed with "b")
 697
 698 sub sign
 699   {
 700   # return the sign of the number: +/-/-inf/+inf/NaN
 701   my ($self,$x) = ref($_[0]) ? (ref($_[0]),$_[0]) : objectify(1,@_);
 702
 703   $x->{sign};
 704   }
 705
 706 sub _find_round_parameters
 707   {
 708   # After any operation or when calling round(), the result is rounded by
 709   # regarding the A & P from arguments, local parameters, or globals.
 710
 711   # This procedure finds the round parameters, but it is for speed reasons
 712   # duplicated in round. Otherwise, it is tested by the testsuite and used
 713   # by fdiv().
 714
 715   my ($self,$a,$p,$r,@args) = @_;
 716   # $a accuracy, if given by caller
 717   # $p precision, if given by caller
 718   # $r round_mode, if given by caller
 719   # @args all 'other' arguments (0 for unary, 1 for binary ops)
 720
 721   # leave bigfloat parts alone
 722   return ($self) if exists $self->{_f} && $self->{_f} & MB_NEVER_ROUND != 0;
 723
 724   my $c = ref($self);                           # find out class of argument(s)
 725   no strict 'refs';
 726
 727   # now pick $a or $p, but only if we have got "arguments"
 728   if (!defined $a)
 729     {
 730     foreach ($self,@args)
 731       {
 732       # take the defined one, or if both defined, the one that is smaller
 733       $a = $_->{_a} if (defined $_->{_a}) && (!defined $a || $_->{_a} < $a);
 734       }
 735     }
 736   if (!defined $p)
 737     {
 738     # even if $a is defined, take $p, to signal error for both defined
 739     foreach ($self,@args)
 740       {
 741       # take the defined one, or if both defined, the one that is bigger
 742       # -2 > -3, and 3 > 2
 743       $p = $_->{_p} if (defined $_->{_p}) && (!defined $p || $_->{_p} > $p);
 744       }
 745     }
 746   # if still none defined, use globals (#2)
 747   $a = ${"$c\::accuracy"} unless defined $a;
 748   $p = ${"$c\::precision"} unless defined $p;
 749
 750   # no rounding today?
 751   return ($self) unless defined $a || defined $p;               # early out
 752
 753   # set A and set P is an fatal error
 754   return ($self->bnan()) if defined $a && defined $p;
 755
 756   $r = ${"$c\::round_mode"} unless defined $r;
 757   die "Unknown round mode '$r'" if $r !~ /^(even|odd|\+inf|\-inf|zero|trunc)$/;
 758
 759   return ($self,$a,$p,$r);
 760   }
 761
 762 sub round
 763   {
 764   # Round $self according to given parameters, or given second argument's
 765   # parameters or global defaults
 766
 767   # for speed reasons, _find_round_parameters is embeded here:
 768
 769   my ($self,$a,$p,$r,@args) = @_;
 770   # $a accuracy, if given by caller
 771   # $p precision, if given by caller
 772   # $r round_mode, if given by caller
 773   # @args all 'other' arguments (0 for unary, 1 for binary ops)
 774
 775   # leave bigfloat parts alone
 776   return ($self) if exists $self->{_f} && $self->{_f} & MB_NEVER_ROUND != 0;
 777
 778   my $c = ref($self);                           # find out class of argument(s)
 779   no strict 'refs';
 780
 781   # now pick $a or $p, but only if we have got "arguments"
 782   if (!defined $a)
 783     {
 784     foreach ($self,@args)
 785       {
 786       # take the defined one, or if both defined, the one that is smaller
 787       $a = $_->{_a} if (defined $_->{_a}) && (!defined $a || $_->{_a} < $a);
 788       }
 789     }
 790   if (!defined $p)
 791     {
 792     # even if $a is defined, take $p, to signal error for both defined
 793     foreach ($self,@args)
 794       {
 795       # take the defined one, or if both defined, the one that is bigger
 796       # -2 > -3, and 3 > 2
 797       $p = $_->{_p} if (defined $_->{_p}) && (!defined $p || $_->{_p} > $p);
 798       }
 799     }
 800   # if still none defined, use globals (#2)
 801   $a = ${"$c\::accuracy"} unless defined $a;
 802   $p = ${"$c\::precision"} unless defined $p;
 803
 804   # no rounding today?
 805   return $self unless defined $a || defined $p;         # early out
 806
 807   # set A and set P is an fatal error
 808   return $self->bnan() if defined $a && defined $p;
 809
 810   $r = ${"$c\::round_mode"} unless defined $r;
 811   die "Unknown round mode '$r'" if $r !~ /^(even|odd|\+inf|\-inf|zero|trunc)$/;
 812
 813   # now round, by calling either fround or ffround:
 814   if (defined $a)
 815     {
 816     $self->bround($a,$r) if !defined $self->{_a} || $self->{_a} >= $a;
 817     }
 818   else # both can't be undefined due to early out
 819     {
 820     $self->bfround($p,$r) if !defined $self->{_p} || $self->{_p} <= $p;
 821     }
 822   $self->bnorm();                       # after round, normalize
 823   }
 824
 825 sub bnorm
 826   {
 827   # (numstr or BINT) return BINT
 828   # Normalize number -- no-op here
 829   my ($self,$x) = ref($_[0]) ? (ref($_[0]),$_[0]) : objectify(1,@_);
 830   $x;
 831   }
 832
 833 sub babs
 834   {
 835   # (BINT or num_str) return BINT
 836   # make number absolute, or return absolute BINT from string
 837   my ($self,$x) = ref($_[0]) ? (ref($_[0]),$_[0]) : objectify(1,@_);
 838
 839   return $x if $x->modify('babs');
 840   # post-normalized abs for internal use (does nothing for NaN)
 841   $x->{sign} =~ s/^-/+/;
 842   $x;
 843   }
 844
 845 sub bneg
 846   {
 847   # (BINT or num_str) return BINT
 848   # negate number or make a negated number from string
 849   my ($self,$x) = ref($_[0]) ? (ref($_[0]),$_[0]) : objectify(1,@_);
 850
 851   return $x if $x->modify('bneg');
 852
 853   # for +0 dont negate (to have always normalized)
 854   $x->{sign} =~ tr/+-/-+/ if !$x->is_zero();    # does nothing for NaN
 855   $x;
 856   }
 857
 858 sub bcmp
 859   {
 860   # Compares 2 values.  Returns one of undef, <0, =0, >0. (suitable for sort)
 861   # (BINT or num_str, BINT or num_str) return cond_code
 862
 863   # set up parameters
 864   my ($self,$x,$y) = (ref($_[0]),@_);
 865
 866   # objectify is costly, so avoid it
 867   if ((!ref($_[0])) || (ref($_[0]) ne ref($_[1])))
 868     {
 869     ($self,$x,$y) = objectify(2,@_);
 870     }
 871
 872   return $upgrade->bcmp($x,$y) if defined $upgrade &&
 873     ((!$x->isa($self)) || (!$y->isa($self)));
 874
 875   if (($x->{sign} !~ /^[+-]$/) || ($y->{sign} !~ /^[+-]$/))
 876     {
 877     # handle +-inf and NaN
 878     return undef if (($x->{sign} eq $nan) || ($y->{sign} eq $nan));
 879     return 0 if $x->{sign} eq $y->{sign} && $x->{sign} =~ /^[+-]inf$/;
 880     return +1 if $x->{sign} eq '+inf';
 881     return -1 if $x->{sign} eq '-inf';
 882     return -1 if $y->{sign} eq '+inf';
 883     return +1;
 884     }
 885   # check sign for speed first
 886   return 1 if $x->{sign} eq '+' && $y->{sign} eq '-';   # does also 0 <=> -y
 887   return -1 if $x->{sign} eq '-' && $y->{sign} eq '+';  # does also -x <=> 0
 888
 889   # have same sign, so compare absolute values. Don't make tests for zero here
 890   # because it's actually slower than testin in Calc (especially w/ Pari et al)
 891
 892   # post-normalized compare for internal use (honors signs)
 893   if ($x->{sign} eq '+')
 894     {
 895     # $x and $y both > 0
 896     return $CALC->_acmp($x->{value},$y->{value});
 897     }
 898
 899   # $x && $y both < 0
 900   $CALC->_acmp($y->{value},$x->{value});        # swaped (lib returns 0,1,-1)
 901   }
 902
 903 sub bacmp
 904   {
 905   # Compares 2 values, ignoring their signs.
 906   # Returns one of undef, <0, =0, >0. (suitable for sort)
 907   # (BINT, BINT) return cond_code
 908
 909   # set up parameters
 910   my ($self,$x,$y) = (ref($_[0]),@_);
 911   # objectify is costly, so avoid it
 912   if ((!ref($_[0])) || (ref($_[0]) ne ref($_[1])))
 913     {
 914     ($self,$x,$y) = objectify(2,@_);
 915     }
 916
 917   return $upgrade->bacmp($x,$y) if defined $upgrade &&
 918     ((!$x->isa($self)) || (!$y->isa($self)));
 919
 920   if (($x->{sign} !~ /^[+-]$/) || ($y->{sign} !~ /^[+-]$/))
 921     {
 922     # handle +-inf and NaN
 923     return undef if (($x->{sign} eq $nan) || ($y->{sign} eq $nan));
 924     return 0 if $x->{sign} =~ /^[+-]inf$/ && $y->{sign} =~ /^[+-]inf$/;
 925     return +1;  # inf is always bigger
 926     }
 927   $CALC->_acmp($x->{value},$y->{value});        # lib does only 0,1,-1
 928   }
 929
 930 sub badd
 931   {
 932   # add second arg (BINT or string) to first (BINT) (modifies first)
 933   # return result as BINT
 934
 935   # set up parameters
 936   my ($self,$x,$y,@r) = (ref($_[0]),@_);
 937   # objectify is costly, so avoid it
 938   if ((!ref($_[0])) || (ref($_[0]) ne ref($_[1])))
 939     {
 940     ($self,$x,$y,@r) = objectify(2,@_);
 941     }
 942
 943   return $x if $x->modify('badd');
 944   return $upgrade->badd($x,$y,@r) if defined $upgrade &&
 945     ((!$x->isa($self)) || (!$y->isa($self)));
 946
 947   $r[3] = $y;                           # no push!
 948   # inf and NaN handling
 949   if (($x->{sign} !~ /^[+-]$/) || ($y->{sign} !~ /^[+-]$/))
 950     {
 951     # NaN first
 952     return $x->bnan() if (($x->{sign} eq $nan) || ($y->{sign} eq $nan));
 953     # inf handling
 954     if (($x->{sign} =~ /^[+-]inf$/) && ($y->{sign} =~ /^[+-]inf$/))
 955       {
 956       # +inf++inf or -inf+-inf => same, rest is NaN
 957       return $x if $x->{sign} eq $y->{sign};
 958       return $x->bnan();
 959       }
 960     # +-inf + something => +inf
 961     # something +-inf => +-inf
 962     $x->{sign} = $y->{sign}, return $x if $y->{sign} =~ /^[+-]inf$/;
 963     return $x;
 964     }
 965
 966   my ($sx, $sy) = ( $x->{sign}, $y->{sign} ); # get signs
 967
 968   if ($sx eq $sy)
 969     {
 970     $x->{value} = $CALC->_add($x->{value},$y->{value}); # same sign, abs add
 971     $x->{sign} = $sx;
 972     }
 973   else
 974     {
 975     my $a = $CALC->_acmp ($y->{value},$x->{value});     # absolute compare
 976     if ($a > 0)
 977       {
 978       #print "swapped sub (a=$a)\n";
 979       $x->{value} = $CALC->_sub($y->{value},$x->{value},1); # abs sub w/ swap
 980       $x->{sign} = $sy;
 981       }
 982     elsif ($a == 0)
 983       {
 984       # speedup, if equal, set result to 0
 985       #print "equal sub, result = 0\n";
 986       $x->{value} = $CALC->_zero();
 987       $x->{sign} = '+';
 988       }
 989     else # a < 0
 990       {
 991       #print "unswapped sub (a=$a)\n";
 992       $x->{value} = $CALC->_sub($x->{value}, $y->{value}); # abs sub
 993       $x->{sign} = $sx;
 994       }
 995     }
 996   $x->round(@r) if !exists $x->{_f} || $x->{_f} & MB_NEVER_ROUND == 0;
 997   $x;
 998   }
 999
1000 sub bsub
1001   {
1002   # (BINT or num_str, BINT or num_str) return num_str
1003   # subtract second arg from first, modify first
1004
1005   # set up parameters
1006   my ($self,$x,$y,@r) = (ref($_[0]),@_);
1007   # objectify is costly, so avoid it
1008   if ((!ref($_[0])) || (ref($_[0]) ne ref($_[1])))
1009     {
1010     ($self,$x,$y,@r) = objectify(2,@_);
1011     }
1012
1013   return $x if $x->modify('bsub');
1014
1015 # upgrade done by badd():
1016 #  return $upgrade->badd($x,$y,@r) if defined $upgrade &&
1017 #   ((!$x->isa($self)) || (!$y->isa($self)));
1018
1019   if ($y->is_zero())
1020     {
1021     $x->round(@r) if !exists $x->{_f} || $x->{_f} & MB_NEVER_ROUND == 0;
1022     return $x;
1023     }
1024
1025   $y->{sign} =~ tr/+\-/-+/;     # does nothing for NaN
1026   $x->badd($y,@r);              # badd does not leave internal zeros
1027   $y->{sign} =~ tr/+\-/-+/;     # refix $y (does nothing for NaN)
1028   $x;                           # already rounded by badd() or no round necc.
1029   }
1030
1031 sub binc
1032   {
1033   # increment arg by one
1034   my ($self,$x,$a,$p,$r) = ref($_[0]) ? (ref($_[0]),@_) : objectify(1,@_);
1035   return $x if $x->modify('binc');
1036
1037   if ($x->{sign} eq '+')
1038     {
1039     $x->{value} = $CALC->_inc($x->{value});
1040     $x->round($a,$p,$r) if !exists $x->{_f} || $x->{_f} & MB_NEVER_ROUND == 0;
1041     return $x;
1042     }
1043   elsif ($x->{sign} eq '-')
1044     {
1045     $x->{value} = $CALC->_dec($x->{value});
1046     $x->{sign} = '+' if $CALC->_is_zero($x->{value}); # -1 +1 => -0 => +0
1047     $x->round($a,$p,$r) if !exists $x->{_f} || $x->{_f} & MB_NEVER_ROUND == 0;
1048     return $x;
1049     }
1050   # inf, nan handling etc
1051   $x->badd($self->__one(),$a,$p,$r);            # badd does round
1052   }
1053
1054 sub bdec
1055   {
1056   # decrement arg by one
1057   my ($self,$x,$a,$p,$r) = ref($_[0]) ? (ref($_[0]),@_) : objectify(1,@_);
1058   return $x if $x->modify('bdec');
1059
1060   my $zero = $CALC->_is_zero($x->{value}) && $x->{sign} eq '+';
1061   # <= 0
1062   if (($x->{sign} eq '-') || $zero)
1063     {
1064     $x->{value} = $CALC->_inc($x->{value});
1065     $x->{sign} = '-' if $zero;                  # 0 => 1 => -1
1066     $x->{sign} = '+' if $CALC->_is_zero($x->{value}); # -1 +1 => -0 => +0
1067     $x->round($a,$p,$r) if !exists $x->{_f} || $x->{_f} & MB_NEVER_ROUND == 0;
1068     return $x;
1069     }
1070   # > 0
1071   elsif ($x->{sign} eq '+')
1072     {
1073     $x->{value} = $CALC->_dec($x->{value});
1074     $x->round($a,$p,$r) if !exists $x->{_f} || $x->{_f} & MB_NEVER_ROUND == 0;
1075     return $x;
1076     }
1077   # inf, nan handling etc
1078   $x->badd($self->__one('-'),$a,$p,$r);                 # badd does round
1079   }
1080
1081 sub blog
1082   {
1083   # not implemented yet
1084   my ($self,$x,$base,$a,$p,$r) = ref($_[0]) ? (ref($_[0]),@_) : objectify(1,@_);
1085
1086   return $upgrade->blog($x,$base,$a,$p,$r) if defined $upgrade;
1087
1088   return $x->bnan();
1089   }
1090
1091 sub blcm
1092   {
1093   # (BINT or num_str, BINT or num_str) return BINT
1094   # does not modify arguments, but returns new object
1095   # Lowest Common Multiplicator
1096
1097   my $y = shift; my ($x);
1098   if (ref($y))
1099     {
1100     $x = $y->copy();
1101     }
1102   else
1103     {
1104     $x = $class->new($y);
1105     }
1106   while (@_) { $x = __lcm($x,shift); }
1107   $x;
1108   }
1109
1110 sub bgcd
1111   {
1112   # (BINT or num_str, BINT or num_str) return BINT
1113   # does not modify arguments, but returns new object
1114   # GCD -- Euclids algorithm, variant C (Knuth Vol 3, pg 341 ff)
1115
1116   my $y = shift;
1117   $y = __PACKAGE__->new($y) if !ref($y);
1118   my $self = ref($y);
1119   my $x = $y->copy();           # keep arguments
1120   if ($CALC->can('_gcd'))
1121     {
1122     while (@_)
1123       {
1124       $y = shift; $y = $self->new($y) if !ref($y);
1125       next if $y->is_zero();
1126       return $x->bnan() if $y->{sign} !~ /^[+-]$/;      # y NaN?
1127       $x->{value} = $CALC->_gcd($x->{value},$y->{value}); last if $x->is_one();
1128       }
1129     }
1130   else
1131     {
1132     while (@_)
1133       {
1134       $y = shift; $y = $self->new($y) if !ref($y);
1135       $x = __gcd($x,$y->copy()); last if $x->is_one();  # _gcd handles NaN
1136       }
1137     }
1138   $x->babs();
1139   }
1140
1141 sub bnot
1142   {
1143   # (num_str or BINT) return BINT
1144   # represent ~x as twos-complement number
1145   # we don't need $self, so undef instead of ref($_[0]) make it slightly faster
1146   my ($self,$x,$a,$p,$r) = ref($_[0]) ? (undef,@_) : objectify(1,@_);
1147
1148   return $x if $x->modify('bnot');
1149   $x->bneg()->bdec();                   # bdec already does round
1150   }
1151
1152 # is_foo test routines
1153
1154 sub is_zero
1155   {
1156   # return true if arg (BINT or num_str) is zero (array '+', '0')
1157   # we don't need $self, so undef instead of ref($_[0]) make it slightly faster
1158   my ($self,$x) = ref($_[0]) ? (undef,$_[0]) : objectify(1,@_);
1159
1160   return 0 if $x->{sign} !~ /^\+$/;                     # -, NaN & +-inf aren't
1161   $CALC->_is_zero($x->{value});
1162   }
1163
1164 sub is_nan
1165   {
1166   # return true if arg (BINT or num_str) is NaN
1167   my ($self,$x) = ref($_[0]) ? (ref($_[0]),$_[0]) : objectify(1,@_);
1168
1169   return 1 if $x->{sign} eq $nan;
1170   0;
1171   }
1172
1173 sub is_inf
1174   {
1175   # return true if arg (BINT or num_str) is +-inf
1176   my ($self,$x,$sign) = ref($_[0]) ? (ref($_[0]),@_) : objectify(1,@_);
1177
1178   $sign = '' if !defined $sign;
1179   return 1 if $sign eq $x->{sign};              # match ("+inf" eq "+inf")
1180   return 0 if $sign !~ /^([+-]|)$/;
1181
1182   if ($sign eq '')
1183     {
1184     return 1 if ($x->{sign} =~ /^[+-]inf$/);
1185     return 0;
1186     }
1187   $sign = quotemeta($sign.'inf');
1188   return 1 if ($x->{sign} =~ /^$sign$/);
1189   0;
1190   }
1191
1192 sub is_one
1193   {
1194   # return true if arg (BINT or num_str) is +1
1195   # or -1 if sign is given
1196   # we don't need $self, so undef instead of ref($_[0]) make it slightly faster
1197   my ($self,$x,$sign) = ref($_[0]) ? (undef,@_) : objectify(1,@_);
1198
1199   $sign = '' if !defined $sign; $sign = '+' if $sign ne '-';
1200
1201   return 0 if $x->{sign} ne $sign;      # -1 != +1, NaN, +-inf aren't either
1202   $CALC->_is_one($x->{value});
1203   }
1204
1205 sub is_odd
1206   {
1207   # return true when arg (BINT or num_str) is odd, false for even
1208   # we don't need $self, so undef instead of ref($_[0]) make it slightly faster
1209   my ($self,$x) = ref($_[0]) ? (undef,$_[0]) : objectify(1,@_);
1210
1211   return 0 if $x->{sign} !~ /^[+-]$/;                   # NaN & +-inf aren't
1212   $CALC->_is_odd($x->{value});
1213   }
1214
1215 sub is_even
1216   {
1217   # return true when arg (BINT or num_str) is even, false for odd
1218   # we don't need $self, so undef instead of ref($_[0]) make it slightly faster
1219   my ($self,$x) = ref($_[0]) ? (undef,$_[0]) : objectify(1,@_);
1220
1221   return 0 if $x->{sign} !~ /^[+-]$/;                   # NaN & +-inf aren't
1222   $CALC->_is_even($x->{value});
1223   }
1224
1225 sub is_positive
1226   {
1227   # return true when arg (BINT or num_str) is positive (>= 0)
1228   # we don't need $self, so undef instead of ref($_[0]) make it slightly faster
1229   my ($self,$x) = ref($_[0]) ? (undef,$_[0]) : objectify(1,@_);
1230
1231   return 1 if $x->{sign} =~ /^\+/;
1232   0;
1233   }
1234
1235 sub is_negative
1236   {
1237   # return true when arg (BINT or num_str) is negative (< 0)
1238   # we don't need $self, so undef instead of ref($_[0]) make it slightly faster
1239   my ($self,$x) = ref($_[0]) ? (undef,$_[0]) : objectify(1,@_);
1240
1241   return 1 if ($x->{sign} =~ /^-/);
1242   0;
1243   }
1244
1245 sub is_int
1246   {
1247   # return true when arg (BINT or num_str) is an integer
1248   # always true for BigInt, but different for Floats
1249   # we don't need $self, so undef instead of ref($_[0]) make it slightly faster
1250   my ($self,$x) = ref($_[0]) ? (undef,$_[0]) : objectify(1,@_);
1251
1252   $x->{sign} =~ /^[+-]$/ ? 1 : 0;               # inf/-inf/NaN aren't
1253   }
1254
1255 ###############################################################################
1256
1257 sub bmul
1258   {
1259   # multiply two numbers -- stolen from Knuth Vol 2 pg 233
1260   # (BINT or num_str, BINT or num_str) return BINT
1261
1262   # set up parameters
1263   my ($self,$x,$y,@r) = (ref($_[0]),@_);
1264   # objectify is costly, so avoid it
1265   if ((!ref($_[0])) || (ref($_[0]) ne ref($_[1])))
1266     {
1267     ($self,$x,$y,@r) = objectify(2,@_);
1268     }
1269
1270   return $x if $x->modify('bmul');
1271
1272   return $x->bnan() if (($x->{sign} eq $nan) || ($y->{sign} eq $nan));
1273
1274   # inf handling
1275   if (($x->{sign} =~ /^[+-]inf$/) || ($y->{sign} =~ /^[+-]inf$/))
1276     {
1277     return $x->bnan() if $x->is_zero() || $y->is_zero();
1278     # result will always be +-inf:
1279     # +inf * +/+inf => +inf, -inf * -/-inf => +inf
1280     # +inf * -/-inf => -inf, -inf * +/+inf => -inf
1281     return $x->binf() if ($x->{sign} =~ /^\+/ && $y->{sign} =~ /^\+/);
1282     return $x->binf() if ($x->{sign} =~ /^-/ && $y->{sign} =~ /^-/);
1283     return $x->binf('-');
1284     }
1285
1286   return $upgrade->bmul($x,$y,@r)
1287    if defined $upgrade && $y->isa($upgrade);
1288
1289   $r[3] = $y;                           # no push here
1290
1291   $x->{sign} = $x->{sign} eq $y->{sign} ? '+' : '-'; # +1 * +1 or -1 * -1 => +
1292
1293   $x->{value} = $CALC->_mul($x->{value},$y->{value});   # do actual math
1294   $x->{sign} = '+' if $CALC->_is_zero($x->{value});     # no -0
1295
1296   $x->round(@r) if !exists $x->{_f} || $x->{_f} & MB_NEVER_ROUND == 0;
1297   $x;
1298   }
1299
1300 sub _div_inf
1301   {
1302   # helper function that handles +-inf cases for bdiv()/bmod() to reuse code
1303   my ($self,$x,$y) = @_;
1304
1305   # NaN if x == NaN or y == NaN or x==y==0
1306   return wantarray ? ($x->bnan(),$self->bnan()) : $x->bnan()
1307    if (($x->is_nan() || $y->is_nan())   ||
1308        ($x->is_zero() && $y->is_zero()));
1309
1310   # +-inf / +-inf == NaN, reminder also NaN
1311   if (($x->{sign} =~ /^[+-]inf$/) && ($y->{sign} =~ /^[+-]inf$/))
1312     {
1313     return wantarray ? ($x->bnan(),$self->bnan()) : $x->bnan();
1314     }
1315   # x / +-inf => 0, remainder x (works even if x == 0)
1316   if ($y->{sign} =~ /^[+-]inf$/)
1317     {
1318     my $t = $x->copy();         # bzero clobbers up $x
1319     return wantarray ? ($x->bzero(),$t) : $x->bzero()
1320     }
1321
1322   # 5 / 0 => +inf, -6 / 0 => -inf
1323   # +inf / 0 = inf, inf,  and -inf / 0 => -inf, -inf
1324   # exception:   -8 / 0 has remainder -8, not 8
1325   # exception: -inf / 0 has remainder -inf, not inf
1326   if ($y->is_zero())
1327     {
1328     # +-inf / 0 => special case for -inf
1329     return wantarray ?  ($x,$x->copy()) : $x if $x->is_inf();
1330     if (!$x->is_zero() && !$x->is_inf())
1331       {
1332       my $t = $x->copy();               # binf clobbers up $x
1333       return wantarray ?
1334        ($x->binf($x->{sign}),$t) : $x->binf($x->{sign})
1335       }
1336     }
1337
1338   # last case: +-inf / ordinary number
1339   my $sign = '+inf';
1340   $sign = '-inf' if substr($x->{sign},0,1) ne $y->{sign};
1341   $x->{sign} = $sign;
1342   return wantarray ? ($x,$self->bzero()) : $x;
1343   }
1344
1345 sub bdiv
1346   {
1347   # (dividend: BINT or num_str, divisor: BINT or num_str) return
1348   # (BINT,BINT) (quo,rem) or BINT (only rem)
1349
1350   # set up parameters
1351   my ($self,$x,$y,@r) = (ref($_[0]),@_);
1352   # objectify is costly, so avoid it
1353   if ((!ref($_[0])) || (ref($_[0]) ne ref($_[1])))
1354     {
1355     ($self,$x,$y,@r) = objectify(2,@_);
1356     }
1357
1358   return $x if $x->modify('bdiv');
1359
1360   return $self->_div_inf($x,$y)
1361    if (($x->{sign} !~ /^[+-]$/) || ($y->{sign} !~ /^[+-]$/) || $y->is_zero());
1362
1363   return $upgrade->bdiv($upgrade->new($x),$y,@r)
1364    if defined $upgrade && !$y->isa($self);
1365
1366   $r[3] = $y;                                   # no push!
1367
1368   # 0 / something
1369   return
1370    wantarray ? ($x->round(@r),$self->bzero(@r)):$x->round(@r) if $x->is_zero();
1371
1372   # Is $x in the interval [0, $y) (aka $x <= $y) ?
1373   my $cmp = $CALC->_acmp($x->{value},$y->{value});
1374   if (($cmp < 0) and (($x->{sign} eq $y->{sign}) or !wantarray))
1375     {
1376     return $upgrade->bdiv($upgrade->new($x),$upgrade->new($y),@r)
1377      if defined $upgrade;
1378
1379     return $x->bzero()->round(@r) unless wantarray;
1380     my $t = $x->copy();      # make copy first, because $x->bzero() clobbers $x
1381     return ($x->bzero()->round(@r),$t);
1382     }
1383   elsif ($cmp == 0)
1384     {
1385     # shortcut, both are the same, so set to +/- 1
1386     $x->__one( ($x->{sign} ne $y->{sign} ? '-' : '+') );
1387     return $x unless wantarray;
1388     return ($x->round(@r),$self->bzero(@r));
1389     }
1390   return $upgrade->bdiv($upgrade->new($x),$upgrade->new($y),@r)
1391    if defined $upgrade;
1392
1393   # calc new sign and in case $y == +/- 1, return $x
1394   my $xsign = $x->{sign};                               # keep
1395   $x->{sign} = ($x->{sign} ne $y->{sign} ? '-' : '+');
1396   # check for / +-1 (cant use $y->is_one due to '-'
1397   if ($CALC->_is_one($y->{value}))
1398     {
1399     return wantarray ? ($x->round(@r),$self->bzero(@r)) : $x->round(@r);
1400     }
1401
1402   if (wantarray)
1403     {
1404     my $rem = $self->bzero();
1405     ($x->{value},$rem->{value}) = $CALC->_div($x->{value},$y->{value});
1406     $x->{sign} = '+' if $CALC->_is_zero($x->{value});
1407     $rem->{_a} = $x->{_a};
1408     $rem->{_p} = $x->{_p};
1409     $x->round(@r);
1410     if (! $CALC->_is_zero($rem->{value}))
1411       {
1412       $rem->{sign} = $y->{sign};
1413       $rem = $y-$rem if $xsign ne $y->{sign};   # one of them '-'
1414       }
1415     else
1416       {
1417       $rem->{sign} = '+';                       # dont leave -0
1418       }
1419     return ($x,$rem->round(@r));
1420     }
1421
1422   $x->{value} = $CALC->_div($x->{value},$y->{value});
1423   $x->{sign} = '+' if $CALC->_is_zero($x->{value});
1424
1425   $x->round(@r) if !exists $x->{_f} || $x->{_f} & MB_NEVER_ROUND == 0;
1426   $x;
1427   }
1428
1429 ###############################################################################
1430 # modulus functions
1431
1432 sub bmod
1433   {
1434   # modulus (or remainder)
1435   # (BINT or num_str, BINT or num_str) return BINT
1436
1437   # set up parameters
1438   my ($self,$x,$y,@r) = (ref($_[0]),@_);
1439   # objectify is costly, so avoid it
1440   if ((!ref($_[0])) || (ref($_[0]) ne ref($_[1])))
1441     {
1442     ($self,$x,$y,@r) = objectify(2,@_);
1443     }
1444
1445   return $x if $x->modify('bmod');
1446   $r[3] = $y;                                   # no push!
1447   if (($x->{sign} !~ /^[+-]$/) || ($y->{sign} !~ /^[+-]$/) || $y->is_zero())
1448     {
1449     my ($d,$r) = $self->_div_inf($x,$y);
1450     $x->{sign} = $r->{sign};
1451     $x->{value} = $r->{value};
1452     return $x->round(@r);
1453     }
1454
1455   if ($CALC->can('_mod'))
1456     {
1457     # calc new sign and in case $y == +/- 1, return $x
1458     $x->{value} = $CALC->_mod($x->{value},$y->{value});
1459     if (!$CALC->_is_zero($x->{value}))
1460       {
1461       my $xsign = $x->{sign};
1462       $x->{sign} = $y->{sign};
1463       if ($xsign ne $y->{sign})
1464         {
1465         my $t = $CALC->_copy($x->{value});              # copy $x
1466         $x->{value} = $CALC->_copy($y->{value});        # copy $y to $x
1467         $x->{value} = $CALC->_sub($y->{value},$t,1);    # $y-$x
1468         }
1469       }
1470     else
1471       {
1472       $x->{sign} = '+';                         # dont leave -0
1473       }
1474     $x->round(@r) if !exists $x->{_f} || $x->{_f} & MB_NEVER_ROUND == 0;
1475     return $x;
1476     }
1477   my ($t,$rem) = $self->bdiv($x->copy(),$y,@r); # slow way (also rounds)
1478   # modify in place
1479   foreach (qw/value sign _a _p/)
1480     {
1481     $x->{$_} = $rem->{$_};
1482     }
1483   $x;
1484   }
1485
1486 sub bmodinv
1487   {
1488   # Modular inverse.  given a number which is (hopefully) relatively
1489   # prime to the modulus, calculate its inverse using Euclid's
1490   # alogrithm.  If the number is not relatively prime to the modulus
1491   # (i.e. their gcd is not one) then NaN is returned.
1492
1493   # set up parameters
1494   my ($self,$x,$y,@r) = (ref($_[0]),@_);
1495   # objectify is costly, so avoid it
1496   if ((!ref($_[0])) || (ref($_[0]) ne ref($_[1])))
1497     {
1498     ($self,$x,$y,@r) = objectify(2,@_);
1499     }
1500
1501   return $x if $x->modify('bmodinv');
1502
1503   return $x->bnan()
1504         if ($y->{sign} ne '+'                           # -, NaN, +inf, -inf
1505          || $x->is_zero()                               # or num == 0
1506          || $x->{sign} !~ /^[+-]$/                      # or num NaN, inf, -inf
1507         );
1508
1509   # put least residue into $x if $x was negative, and thus make it positive
1510   $x->bmod($y) if $x->{sign} eq '-';
1511
1512   if ($CALC->can('_modinv'))
1513     {
1514     my $sign;
1515     ($x->{value},$sign) = $CALC->_modinv($x->{value},$y->{value});
1516     $x->bnan() if !defined $x->{value};                 # in case no GCD found
1517     return $x if !defined $sign;                        # already real result
1518     $x->{sign} = $sign;                                 # flip/flop see below
1519     $x->bmod($y);                                       # calc real result
1520     return $x;
1521     }
1522   my ($u, $u1) = ($self->bzero(), $self->bone());
1523   my ($a, $b) = ($y->copy(), $x->copy());
1524
1525   # first step need always be done since $num (and thus $b) is never 0
1526   # Note that the loop is aligned so that the check occurs between #2 and #1
1527   # thus saving us one step #2 at the loop end. Typical loop count is 1. Even
1528   # a case with 28 loops still gains about 3% with this layout.
1529   my $q;
1530   ($a, $q, $b) = ($b, $a->bdiv($b));                    # step #1
1531   # Euclid's Algorithm (calculate GCD of ($a,$b) in $a and also calculate
1532   # two values in $u and $u1, we use only $u1 afterwards)
1533   my $sign = 1;                                         # flip-flop
1534   while (!$b->is_zero())                                # found GCD if $b == 0
1535     {
1536     # the original algorithm had:
1537     # ($u, $u1) = ($u1, $u->bsub($u1->copy()->bmul($q))); # step #2
1538     # The following creates exact the same sequence of numbers in $u1,
1539     # except for the sign ($u1 is now always positive). Since formerly
1540     # the sign of $u1 was alternating between '-' and '+', the $sign
1541     # flip-flop will take care of that, so that at the end of the loop
1542     # we have the real sign of $u1. Keeping numbers positive gains us
1543     # speed since badd() is faster than bsub() and makes it possible
1544     # to have the algorithmn in Calc for even more speed.
1545
1546     ($u, $u1) = ($u1, $u->badd($u1->copy()->bmul($q))); # step #2
1547     $sign = - $sign;                                    # flip sign
1548
1549     ($a, $q, $b) = ($b, $a->bdiv($b));                  # step #1 again
1550     }
1551
1552   # If the gcd is not 1, then return NaN! It would be pointless to
1553   # have called bgcd to check this first, because we would then be
1554   # performing the same Euclidean Algorithm *twice*.
1555   return $x->bnan() unless $a->is_one();
1556
1557   $u1->bneg() if $sign != 1;                            # need to flip?
1558
1559   $u1->bmod($y);                                        # calc result
1560   $x->{value} = $u1->{value};                           # and copy over to $x
1561   $x->{sign} = $u1->{sign};                             # to modify in place
1562   $x;
1563   }
1564
1565 sub bmodpow
1566   {
1567   # takes a very large number to a very large exponent in a given very
1568   # large modulus, quickly, thanks to binary exponentation.  supports
1569   # negative exponents.
1570   my ($self,$num,$exp,$mod,@r) = objectify(3,@_);
1571
1572   return $num if $num->modify('bmodpow');
1573
1574   # check modulus for valid values
1575   return $num->bnan() if ($mod->{sign} ne '+'           # NaN, - , -inf, +inf
1576                        || $mod->is_zero());
1577
1578   # check exponent for valid values
1579   if ($exp->{sign} =~ /\w/)
1580     {
1581     # i.e., if it's NaN, +inf, or -inf...
1582     return $num->bnan();
1583     }
1584
1585   $num->bmodinv ($mod) if ($exp->{sign} eq '-');
1586
1587   # check num for valid values (also NaN if there was no inverse but $exp < 0)
1588   return $num->bnan() if $num->{sign} !~ /^[+-]$/;
1589
1590   if ($CALC->can('_modpow'))
1591     {
1592     # $mod is positive, sign on $exp is ignored, result also positive
1593     $num->{value} = $CALC->_modpow($num->{value},$exp->{value},$mod->{value});
1594     return $num;
1595     }
1596
1597   # in the trivial case,
1598   return $num->bzero(@r) if $mod->is_one();
1599   return $num->bone('+',@r) if $num->is_zero() or $num->is_one();
1600
1601   # $num->bmod($mod);           # if $x is large, make it smaller first
1602   my $acc = $num->copy();       # but this is not really faster...
1603
1604   $num->bone(); # keep ref to $num
1605
1606   my $expbin = $exp->as_bin(); $expbin =~ s/^[-]?0b//; # ignore sign and prefix
1607   my $len = length($expbin);
1608   while (--$len >= 0)
1609     {
1610     if( substr($expbin,$len,1) eq '1')
1611       {
1612       $num->bmul($acc)->bmod($mod);
1613       }
1614     $acc->bmul($acc)->bmod($mod);
1615     }
1616
1617   $num;
1618   }
1619
1620 ###############################################################################
1621
1622 sub bfac
1623   {
1624   # (BINT or num_str, BINT or num_str) return BINT
1625   # compute factorial numbers
1626   # modifies first argument
1627   my ($self,$x,@r) = ref($_[0]) ? (ref($_[0]),@_) : objectify(1,@_);
1628
1629   return $x if $x->modify('bfac');
1630
1631   return $x->bnan() if $x->{sign} ne '+';       # inf, NnN, <0 etc => NaN
1632   return $x->bone('+',@r) if $x->is_zero() || $x->is_one();     # 0 or 1 => 1
1633
1634   if ($CALC->can('_fac'))
1635     {
1636     $x->{value} = $CALC->_fac($x->{value});
1637     return $x->round(@r);
1638     }
1639
1640   my $n = $x->copy();
1641   $x->bone();
1642   # seems we need not to temp. clear A/P of $x since the result is the same
1643   my $f = $self->new(2);
1644   while ($f->bacmp($n) < 0)
1645     {
1646     $x->bmul($f); $f->binc();
1647     }
1648   $x->bmul($f,@r);                      # last step and also round
1649   }
1650
1651 sub bpow
1652   {
1653   # (BINT or num_str, BINT or num_str) return BINT
1654   # compute power of two numbers -- stolen from Knuth Vol 2 pg 233
1655   # modifies first argument
1656
1657   # set up parameters
1658   my ($self,$x,$y,@r) = (ref($_[0]),@_);
1659   # objectify is costly, so avoid it
1660   if ((!ref($_[0])) || (ref($_[0]) ne ref($_[1])))
1661     {
1662     ($self,$x,$y,@r) = objectify(2,@_);
1663     }
1664
1665   return $x if $x->modify('bpow');
1666
1667   return $upgrade->bpow($upgrade->new($x),$y,@r)
1668    if defined $upgrade && !$y->isa($self);
1669
1670   $r[3] = $y;                                   # no push!
1671   return $x if $x->{sign} =~ /^[+-]inf$/;       # -inf/+inf ** x
1672   return $x->bnan() if $x->{sign} eq $nan || $y->{sign} eq $nan;
1673   return $x->bone('+',@r) if $y->is_zero();
1674   return $x->round(@r) if $x->is_one() || $y->is_one();
1675   if ($x->{sign} eq '-' && $CALC->_is_one($x->{value}))
1676     {
1677     # if $x == -1 and odd/even y => +1/-1
1678     return $y->is_odd() ? $x->round(@r) : $x->babs()->round(@r);
1679     # my Casio FX-5500L has a bug here: -1 ** 2 is -1, but -1 * -1 is 1;
1680     }
1681   # 1 ** -y => 1 / (1 ** |y|)
1682   # so do test for negative $y after above's clause
1683   return $x->bnan() if $y->{sign} eq '-';
1684   return $x->round(@r) if $x->is_zero();  # 0**y => 0 (if not y <= 0)
1685
1686   if ($CALC->can('_pow'))
1687     {
1688     $x->{value} = $CALC->_pow($x->{value},$y->{value});
1689     $x->round(@r) if !exists $x->{_f} || $x->{_f} & MB_NEVER_ROUND == 0;
1690     return $x;
1691     }
1692
1693 # based on the assumption that shifting in base 10 is fast, and that mul
1694 # works faster if numbers are small: we count trailing zeros (this step is
1695 # O(1)..O(N), but in case of O(N) we save much more time due to this),
1696 # stripping them out of the multiplication, and add $count * $y zeros
1697 # afterwards like this:
1698 # 300 ** 3 == 300*300*300 == 3*3*3 . '0' x 2 * 3 == 27 . '0' x 6
1699 # creates deep recursion since brsft/blsft use bpow sometimes.
1700 #  my $zeros = $x->_trailing_zeros();
1701 #  if ($zeros > 0)
1702 #    {
1703 #    $x->brsft($zeros,10);      # remove zeros
1704 #    $x->bpow($y);              # recursion (will not branch into here again)
1705 #    $zeros = $y * $zeros;      # real number of zeros to add
1706 #    $x->blsft($zeros,10);
1707 #    return $x->round(@r);
1708 #    }
1709
1710   my $pow2 = $self->__one();
1711   my $y_bin = $y->as_bin(); $y_bin =~ s/^0b//;
1712   my $len = length($y_bin);
1713   while (--$len > 0)
1714     {
1715     $pow2->bmul($x) if substr($y_bin,$len,1) eq '1';    # is odd?
1716     $x->bmul($x);
1717     }
1718   $x->bmul($pow2);
1719   $x->round(@r) if !exists $x->{_f} || $x->{_f} & MB_NEVER_ROUND == 0;
1720   $x;
1721   }
1722
1723 sub blsft
1724   {
1725   # (BINT or num_str, BINT or num_str) return BINT
1726   # compute x << y, base n, y >= 0
1727
1728   # set up parameters
1729   my ($self,$x,$y,$n,@r) = (ref($_[0]),@_);
1730   # objectify is costly, so avoid it
1731   if ((!ref($_[0])) || (ref($_[0]) ne ref($_[1])))
1732     {
1733     ($self,$x,$y,$n,@r) = objectify(2,@_);
1734     }
1735
1736   return $x if $x->modify('blsft');
1737   return $x->bnan() if ($x->{sign} !~ /^[+-]$/ || $y->{sign} !~ /^[+-]$/);
1738   return $x->round(@r) if $y->is_zero();
1739
1740   $n = 2 if !defined $n; return $x->bnan() if $n <= 0 || $y->{sign} eq '-';
1741
1742   my $t; $t = $CALC->_lsft($x->{value},$y->{value},$n) if $CALC->can('_lsft');
1743   if (defined $t)
1744     {
1745     $x->{value} = $t; return $x->round(@r);
1746     }
1747   # fallback
1748   return $x->bmul( $self->bpow($n, $y, @r), @r );
1749   }
1750
1751 sub brsft
1752   {
1753   # (BINT or num_str, BINT or num_str) return BINT
1754   # compute x >> y, base n, y >= 0
1755
1756   # set up parameters
1757   my ($self,$x,$y,$n,@r) = (ref($_[0]),@_);
1758   # objectify is costly, so avoid it
1759   if ((!ref($_[0])) || (ref($_[0]) ne ref($_[1])))
1760     {
1761     ($self,$x,$y,$n,@r) = objectify(2,@_);
1762     }
1763
1764   return $x if $x->modify('brsft');
1765   return $x->bnan() if ($x->{sign} !~ /^[+-]$/ || $y->{sign} !~ /^[+-]$/);
1766   return $x->round(@r) if $y->is_zero();
1767   return $x->bzero(@r) if $x->is_zero();                # 0 => 0
1768
1769   $n = 2 if !defined $n; return $x->bnan() if $n <= 0 || $y->{sign} eq '-';
1770
1771    # this only works for negative numbers when shifting in base 2
1772   if (($x->{sign} eq '-') && ($n == 2))
1773     {
1774     return $x->round(@r) if $x->is_one('-');    # -1 => -1
1775     if (!$y->is_one())
1776       {
1777       # although this is O(N*N) in calc (as_bin!) it is O(N) in Pari et al
1778       # but perhaps there is a better emulation for two's complement shift...
1779       # if $y != 1, we must simulate it by doing:
1780       # convert to bin, flip all bits, shift, and be done
1781       $x->binc();                       # -3 => -2
1782       my $bin = $x->as_bin();
1783       $bin =~ s/^-0b//;                 # strip '-0b' prefix
1784       $bin =~ tr/10/01/;                # flip bits
1785       # now shift
1786       if (CORE::length($bin) <= $y)
1787         {
1788         $bin = '0';                     # shifting to far right creates -1
1789                                         # 0, because later increment makes
1790                                         # that 1, attached '-' makes it '-1'
1791                                         # because -1 >> x == -1 !
1792         }
1793       else
1794         {
1795         $bin =~ s/.{$y}$//;             # cut off at the right side
1796         $bin = '1' . $bin;              # extend left side by one dummy '1'
1797         $bin =~ tr/10/01/;              # flip bits back
1798         }
1799       my $res = $self->new('0b'.$bin);  # add prefix and convert back
1800       $res->binc();                     # remember to increment
1801       $x->{value} = $res->{value};      # take over value
1802       return $x->round(@r);             # we are done now, magic, isn't?
1803       }
1804     $x->bdec();                         # n == 2, but $y == 1: this fixes it
1805     }
1806
1807   my $t; $t = $CALC->_rsft($x->{value},$y->{value},$n) if $CALC->can('_rsft');
1808   if (defined $t)
1809     {
1810     $x->{value} = $t;
1811     return $x->round(@r);
1812     }
1813   # fallback
1814   $x->bdiv($self->bpow($n,$y, @r), @r);
1815   $x;
1816   }
1817
1818 sub band
1819   {
1820   #(BINT or num_str, BINT or num_str) return BINT
1821   # compute x & y
1822
1823   # set up parameters
1824   my ($self,$x,$y,@r) = (ref($_[0]),@_);
1825   # objectify is costly, so avoid it
1826   if ((!ref($_[0])) || (ref($_[0]) ne ref($_[1])))
1827     {
1828     ($self,$x,$y,@r) = objectify(2,@_);
1829     }
1830
1831   return $x if $x->modify('band');
1832
1833   $r[3] = $y;                           # no push!
1834   local $Math::BigInt::upgrade = undef;
1835
1836   return $x->bnan() if ($x->{sign} !~ /^[+-]$/ || $y->{sign} !~ /^[+-]$/);
1837   return $x->bzero(@r) if $y->is_zero() || $x->is_zero();
1838
1839   my $sign = 0;                                 # sign of result
1840   $sign = 1 if ($x->{sign} eq '-') && ($y->{sign} eq '-');
1841   my $sx = 1; $sx = -1 if $x->{sign} eq '-';
1842   my $sy = 1; $sy = -1 if $y->{sign} eq '-';
1843
1844   if ($CALC->can('_and') && $sx == 1 && $sy == 1)
1845     {
1846     $x->{value} = $CALC->_and($x->{value},$y->{value});
1847     return $x->round(@r);
1848     }
1849
1850   my $m = $self->bone(); my ($xr,$yr);
1851   my $x10000 = $self->new (0x1000);
1852   my $y1 = copy(ref($x),$y);                    # make copy
1853   $y1->babs();                                  # and positive
1854   my $x1 = $x->copy()->babs(); $x->bzero();     # modify x in place!
1855   use integer;                                  # need this for negative bools
1856   while (!$x1->is_zero() && !$y1->is_zero())
1857     {
1858     ($x1, $xr) = bdiv($x1, $x10000);
1859     ($y1, $yr) = bdiv($y1, $x10000);
1860     # make both op's numbers!
1861     $x->badd( bmul( $class->new(
1862        abs($sx*int($xr->numify()) & $sy*int($yr->numify()))),
1863       $m));
1864     $m->bmul($x10000);
1865     }
1866   $x->bneg() if $sign;
1867   $x->round(@r);
1868   }
1869
1870 sub bior
1871   {
1872   #(BINT or num_str, BINT or num_str) return BINT
1873   # compute x | y
1874
1875   # set up parameters
1876   my ($self,$x,$y,@r) = (ref($_[0]),@_);
1877   # objectify is costly, so avoid it
1878   if ((!ref($_[0])) || (ref($_[0]) ne ref($_[1])))
1879     {
1880     ($self,$x,$y,@r) = objectify(2,@_);
1881     }
1882
1883   return $x if $x->modify('bior');
1884   $r[3] = $y;                           # no push!
1885
1886   local $Math::BigInt::upgrade = undef;
1887
1888   return $x->bnan() if ($x->{sign} !~ /^[+-]$/ || $y->{sign} !~ /^[+-]$/);
1889   return $x->round(@r) if $y->is_zero();
1890
1891   my $sign = 0;                                 # sign of result
1892   $sign = 1 if ($x->{sign} eq '-') || ($y->{sign} eq '-');
1893   my $sx = 1; $sx = -1 if $x->{sign} eq '-';
1894   my $sy = 1; $sy = -1 if $y->{sign} eq '-';
1895
1896   # don't use lib for negative values
1897   if ($CALC->can('_or') && $sx == 1 && $sy == 1)
1898     {
1899     $x->{value} = $CALC->_or($x->{value},$y->{value});
1900     return $x->round(@r);
1901     }
1902
1903   my $m = $self->bone(); my ($xr,$yr);
1904   my $x10000 = $self->new(0x10000);
1905   my $y1 = copy(ref($x),$y);                    # make copy
1906   $y1->babs();                                  # and positive
1907   my $x1 = $x->copy()->babs(); $x->bzero();     # modify x in place!
1908   use integer;                                  # need this for negative bools
1909   while (!$x1->is_zero() || !$y1->is_zero())
1910     {
1911     ($x1, $xr) = bdiv($x1,$x10000);
1912     ($y1, $yr) = bdiv($y1,$x10000);
1913     # make both op's numbers!
1914     $x->badd( bmul( $class->new(
1915        abs($sx*int($xr->numify()) | $sy*int($yr->numify()))),
1916       $m));
1917     $m->bmul($x10000);
1918     }
1919   $x->bneg() if $sign;
1920   $x->round(@r);
1921   }
1922
1923 sub bxor
1924   {
1925   #(BINT or num_str, BINT or num_str) return BINT
1926   # compute x ^ y
1927
1928   # set up parameters
1929   my ($self,$x,$y,@r) = (ref($_[0]),@_);
1930   # objectify is costly, so avoid it
1931   if ((!ref($_[0])) || (ref($_[0]) ne ref($_[1])))
1932     {
1933     ($self,$x,$y,@r) = objectify(2,@_);
1934     }
1935
1936   return $x if $x->modify('bxor');
1937   $r[3] = $y;                           # no push!
1938
1939   local $Math::BigInt::upgrade = undef;
1940
1941   return $x->bnan() if ($x->{sign} !~ /^[+-]$/ || $y->{sign} !~ /^[+-]$/);
1942   return $x->round(@r) if $y->is_zero();
1943
1944   my $sign = 0;                                 # sign of result
1945   $sign = 1 if $x->{sign} ne $y->{sign};
1946   my $sx = 1; $sx = -1 if $x->{sign} eq '-';
1947   my $sy = 1; $sy = -1 if $y->{sign} eq '-';
1948
1949   # don't use lib for negative values
1950   if ($CALC->can('_xor') && $sx == 1 && $sy == 1)
1951     {
1952     $x->{value} = $CALC->_xor($x->{value},$y->{value});
1953     return $x->round(@r);
1954     }
1955
1956   my $m = $self->bone(); my ($xr,$yr);
1957   my $x10000 = $self->new(0x10000);
1958   my $y1 = copy(ref($x),$y);                    # make copy
1959   $y1->babs();                                  # and positive
1960   my $x1 = $x->copy()->babs(); $x->bzero();     # modify x in place!
1961   use integer;                                  # need this for negative bools
1962   while (!$x1->is_zero() || !$y1->is_zero())
1963     {
1964     ($x1, $xr) = bdiv($x1, $x10000);
1965     ($y1, $yr) = bdiv($y1, $x10000);
1966     # make both op's numbers!
1967     $x->badd( bmul( $class->new(
1968        abs($sx*int($xr->numify()) ^ $sy*int($yr->numify()))),
1969       $m));
1970     $m->bmul($x10000);
1971     }
1972   $x->bneg() if $sign;
1973   $x->round(@r);
1974   }
1975
1976 sub length
1977   {
1978   my ($self,$x) = ref($_[0]) ? (ref($_[0]),$_[0]) : objectify(1,@_);
1979
1980   my $e = $CALC->_len($x->{value});
1981   return wantarray ? ($e,0) : $e;
1982   }
1983
1984 sub digit
1985   {
1986   # return the nth decimal digit, negative values count backward, 0 is right
1987   my ($self,$x,$n) = ref($_[0]) ? (ref($_[0]),@_) : objectify(1,@_);
1988
1989   $CALC->_digit($x->{value},$n||0);
1990   }
1991
1992 sub _trailing_zeros
1993   {
1994   # return the amount of trailing zeros in $x
1995   my $x = shift;
1996   $x = $class->new($x) unless ref $x;
1997
1998   return 0 if $x->is_zero() || $x->is_odd() || $x->{sign} !~ /^[+-]$/;
1999
2000   return $CALC->_zeros($x->{value}) if $CALC->can('_zeros');
2001
2002   # if not: since we do not know underlying internal representation:
2003   my $es = "$x"; $es =~ /([0]*)$/;
2004   return 0 if !defined $1;      # no zeros
2005   CORE::length("$1");           # as string, not as +0!
2006   }
2007
2008 sub bsqrt
2009   {
2010   my ($self,$x,@r) = ref($_[0]) ? (ref($_[0]),@_) : objectify(1,@_);
2011
2012   return $x if $x->modify('bsqrt');
2013
2014   return $x->bnan() if $x->{sign} ne '+';       # -x or inf or NaN => NaN
2015   return $x->bzero(@r) if $x->is_zero();                        # 0 => 0
2016   return $x->round(@r) if $x->is_one();                 # 1 => 1
2017
2018   return $upgrade->bsqrt($x,@r) if defined $upgrade;
2019
2020   if ($CALC->can('_sqrt'))
2021     {
2022     $x->{value} = $CALC->_sqrt($x->{value});
2023     return $x->round(@r);
2024     }
2025
2026   return $x->bone('+',@r) if $x < 4;                            # 2,3 => 1
2027   my $y = $x->copy();
2028   my $l = int($x->length()/2);
2029
2030   $x->bone();                                   # keep ref($x), but modify it
2031   $x->blsft($l,10);
2032
2033   my $last = $self->bzero();
2034   my $two = $self->new(2);
2035   my $lastlast = $x+$two;
2036   while ($last != $x && $lastlast != $x)
2037     {
2038     $lastlast = $last; $last = $x->copy();
2039     $x->badd($y / $x);
2040     $x->bdiv($two);
2041     }
2042   $x->bdec() if $x * $x > $y;                           # overshot?
2043   $x->round(@r);
2044   }
2045
2046 sub exponent
2047   {
2048   # return a copy of the exponent (here always 0, NaN or 1 for $m == 0)
2049   my ($self,$x) = ref($_[0]) ? (ref($_[0]),$_[0]) : objectify(1,@_);
2050
2051   if ($x->{sign} !~ /^[+-]$/)
2052     {
2053     my $s = $x->{sign}; $s =~ s/^[+-]//;
2054     return $self->new($s);              # -inf,+inf => inf
2055     }
2056   my $e = $class->bzero();
2057   return $e->binc() if $x->is_zero();
2058   $e += $x->_trailing_zeros();
2059   $e;
2060   }
2061
2062 sub mantissa
2063   {
2064   # return the mantissa (compatible to Math::BigFloat, e.g. reduced)
2065   my ($self,$x) = ref($_[0]) ? (ref($_[0]),$_[0]) : objectify(1,@_);
2066
2067   if ($x->{sign} !~ /^[+-]$/)
2068     {
2069     return $self->new($x->{sign});              # keep + or - sign
2070     }
2071   my $m = $x->copy();
2072   # that's inefficient
2073   my $zeros = $m->_trailing_zeros();
2074   $m->brsft($zeros,10) if $zeros != 0;
2075   $m;
2076   }
2077
2078 sub parts
2079   {
2080   # return a copy of both the exponent and the mantissa
2081   my ($self,$x) = ref($_[0]) ? (ref($_[0]),$_[0]) : objectify(1,@_);
2082
2083   return ($x->mantissa(),$x->exponent());
2084   }
2085
2086 ##############################################################################
2087 # rounding functions
2088
2089 sub bfround
2090   {
2091   # precision: round to the $Nth digit left (+$n) or right (-$n) from the '.'
2092   # $n == 0 || $n == 1 => round to integer
2093   my $x = shift; $x = $class->new($x) unless ref $x;
2094   my ($scale,$mode) = $x->_scale_p($x->precision(),$x->round_mode(),@_);
2095   return $x if !defined $scale;         # no-op
2096   return $x if $x->modify('bfround');
2097
2098   # no-op for BigInts if $n <= 0
2099   if ($scale <= 0)
2100     {
2101     $x->{_a} = undef;                           # clear an eventual set A
2102     $x->{_p} = $scale; return $x;
2103     }
2104
2105   $x->bround( $x->length()-$scale, $mode);
2106   $x->{_a} = undef;                             # bround sets {_a}
2107   $x->{_p} = $scale;                            # so correct it
2108   $x;
2109   }
2110
2111 sub _scan_for_nonzero
2112   {
2113   my $x = shift;
2114   my $pad = shift;
2115   my $xs = shift;
2116
2117   my $len = $x->length();
2118   return 0 if $len == 1;                # '5' is trailed by invisible zeros
2119   my $follow = $pad - 1;
2120   return 0 if $follow > $len || $follow < 1;
2121
2122   # since we do not know underlying represention of $x, use decimal string
2123   #my $r = substr ($$xs,-$follow);
2124   my $r = substr ("$x",-$follow);
2125   return 1 if $r =~ /[^0]/;
2126   0;
2127   }
2128
2129 sub fround
2130   {
2131   # to make life easier for switch between MBF and MBI (autoload fxxx()
2132   # like MBF does for bxxx()?)
2133   my $x = shift;
2134   return $x->bround(@_);
2135   }
2136
2137 sub bround
2138   {
2139   # accuracy: +$n preserve $n digits from left,
2140   #           -$n preserve $n digits from right (f.i. for 0.1234 style in MBF)
2141   # no-op for $n == 0
2142   # and overwrite the rest with 0's, return normalized number
2143   # do not return $x->bnorm(), but $x
2144
2145   my $x = shift; $x = $class->new($x) unless ref $x;
2146   my ($scale,$mode) = $x->_scale_a($x->accuracy(),$x->round_mode(),@_);
2147   return $x if !defined $scale;                 # no-op
2148   return $x if $x->modify('bround');
2149
2150   if ($x->is_zero() || $scale == 0)
2151     {
2152     $x->{_a} = $scale if !defined $x->{_a} || $x->{_a} > $scale; # 3 > 2
2153     return $x;
2154     }
2155   return $x if $x->{sign} !~ /^[+-]$/;          # inf, NaN
2156
2157   # we have fewer digits than we want to scale to
2158   my $len = $x->length();
2159   # convert $scale to a scalar in case it is an object (put's a limit on the
2160   # number length, but this would already limited by memory constraints), makes
2161   # it faster
2162   $scale = $scale->numify() if ref ($scale);
2163
2164   # scale < 0, but > -len (not >=!)
2165   if (($scale < 0 && $scale < -$len-1) || ($scale >= $len))
2166     {
2167     $x->{_a} = $scale if !defined $x->{_a} || $x->{_a} > $scale; # 3 > 2
2168     return $x;
2169     }
2170
2171   # count of 0's to pad, from left (+) or right (-): 9 - +6 => 3, or |-6| => 6
2172   my ($pad,$digit_round,$digit_after);
2173   $pad = $len - $scale;
2174   $pad = abs($scale-1) if $scale < 0;
2175
2176   # do not use digit(), it is costly for binary => decimal
2177
2178   my $xs = $CALC->_str($x->{value});
2179   my $pl = -$pad-1;
2180
2181   # pad:   123: 0 => -1, at 1 => -2, at 2 => -3, at 3 => -4
2182   # pad+1: 123: 0 => 0,  at 1 => -1, at 2 => -2, at 3 => -3
2183   $digit_round = '0'; $digit_round = substr($$xs,$pl,1) if $pad <= $len;
2184   $pl++; $pl ++ if $pad >= $len;
2185   $digit_after = '0'; $digit_after = substr($$xs,$pl,1) if $pad > 0;
2186
2187   # in case of 01234 we round down, for 6789 up, and only in case 5 we look
2188   # closer at the remaining digits of the original $x, remember decision
2189   my $round_up = 1;                                     # default round up
2190   $round_up -- if
2191     ($mode eq 'trunc')                          ||      # trunc by round down
2192     ($digit_after =~ /[01234]/)                 ||      # round down anyway,
2193                                                         # 6789 => round up
2194     ($digit_after eq '5')                       &&      # not 5000...0000
2195     ($x->_scan_for_nonzero($pad,$xs) == 0)              &&
2196     (
2197      ($mode eq 'even') && ($digit_round =~ /[24680]/) ||
2198      ($mode eq 'odd')  && ($digit_round =~ /[13579]/) ||
2199      ($mode eq '+inf') && ($x->{sign} eq '-')   ||
2200      ($mode eq '-inf') && ($x->{sign} eq '+')   ||
2201      ($mode eq 'zero')          # round down if zero, sign adjusted below
2202     );
2203   my $put_back = 0;                                     # not yet modified
2204
2205   if (($pad > 0) && ($pad <= $len))
2206     {
2207     substr($$xs,-$pad,$pad) = '0' x $pad;
2208     $put_back = 1;
2209     }
2210   elsif ($pad > $len)
2211     {
2212     $x->bzero();                                        # round to '0'
2213     }
2214
2215   if ($round_up)                                        # what gave test above?
2216     {
2217     $put_back = 1;
2218     $pad = $len, $$xs = '0' x $pad if $scale < 0;       # tlr: whack 0.51=>1.0
2219
2220     # we modify directly the string variant instead of creating a number and
2221     # adding it, since that is faster (we already have the string)
2222     my $c = 0; $pad ++;                         # for $pad == $len case
2223     while ($pad <= $len)
2224       {
2225       $c = substr($$xs,-$pad,1) + 1; $c = '0' if $c eq '10';
2226       substr($$xs,-$pad,1) = $c; $pad++;
2227       last if $c != 0;                          # no overflow => early out
2228       }
2229     $$xs = '1'.$$xs if $c == 0;
2230
2231     }
2232   $x->{value} = $CALC->_new($xs) if $put_back == 1;     # put back in if needed
2233
2234   $x->{_a} = $scale if $scale >= 0;
2235   if ($scale < 0)
2236     {
2237     $x->{_a} = $len+$scale;
2238     $x->{_a} = 0 if $scale < -$len;
2239     }
2240   $x;
2241   }
2242
2243 sub bfloor
2244   {
2245   # return integer less or equal then number, since it is already integer,
2246   # always returns $self
2247   my ($self,$x,@r) = ref($_[0]) ? (ref($_[0]),@_) : objectify(1,@_);
2248
2249   $x->round(@r);
2250   }
2251
2252 sub bceil
2253   {
2254   # return integer greater or equal then number, since it is already integer,
2255   # always returns $self
2256   my ($self,$x,@r) = ref($_[0]) ? (ref($_[0]),@_) : objectify(1,@_);
2257
2258   $x->round(@r);
2259   }
2260
2261 ##############################################################################
2262 # private stuff (internal use only)
2263
2264 sub __one
2265   {
2266   # internal speedup, set argument to 1, or create a +/- 1
2267   my $self = shift;
2268   my $x = $self->bone(); # $x->{value} = $CALC->_one();
2269   $x->{sign} = shift || '+';
2270   $x;
2271   }
2272
2273 sub _swap
2274   {
2275   # Overload will swap params if first one is no object ref so that the first
2276   # one is always an object ref. In this case, third param is true.
2277   # This routine is to overcome the effect of scalar,$object creating an object
2278   # of the class of this package, instead of the second param $object. This
2279   # happens inside overload, when the overload section of this package is
2280   # inherited by sub classes.
2281   # For overload cases (and this is used only there), we need to preserve the
2282   # args, hence the copy().
2283   # You can override this method in a subclass, the overload section will call
2284   # $object->_swap() to make sure it arrives at the proper subclass, with some
2285   # exceptions like '+' and '-'. To make '+' and '-' work, you also need to
2286   # specify your own overload for them.
2287
2288   # object, (object|scalar) => preserve first and make copy
2289   # scalar, object          => swapped, re-swap and create new from first
2290   #                            (using class of second object, not $class!!)
2291   my $self = shift;                     # for override in subclass
2292   if ($_[2])
2293     {
2294     my $c = ref ($_[0]) || $class;      # fallback $class should not happen
2295     return ( $c->new($_[1]), $_[0] );
2296     }
2297   return ( $_[0]->copy(), $_[1] );
2298   }
2299
2300 sub objectify
2301   {
2302   # check for strings, if yes, return objects instead
2303
2304   # the first argument is number of args objectify() should look at it will
2305   # return $count+1 elements, the first will be a classname. This is because
2306   # overloaded '""' calls bstr($object,undef,undef) and this would result in
2307   # useless objects beeing created and thrown away. So we cannot simple loop
2308   # over @_. If the given count is 0, all arguments will be used.
2309
2310   # If the second arg is a ref, use it as class.
2311   # If not, try to use it as classname, unless undef, then use $class
2312   # (aka Math::BigInt). The latter shouldn't happen,though.
2313
2314   # caller:                        gives us:
2315   # $x->badd(1);                => ref x, scalar y
2316   # Class->badd(1,2);           => classname x (scalar), scalar x, scalar y
2317   # Class->badd( Class->(1),2); => classname x (scalar), ref x, scalar y
2318   # Math::BigInt::badd(1,2);    => scalar x, scalar y
2319   # In the last case we check number of arguments to turn it silently into
2320   # $class,1,2. (We can not take '1' as class ;o)
2321   # badd($class,1) is not supported (it should, eventually, try to add undef)
2322   # currently it tries 'Math::BigInt' + 1, which will not work.
2323
2324   # some shortcut for the common cases
2325   # $x->unary_op();
2326   return (ref($_[1]),$_[1]) if (@_ == 2) && ($_[0]||0 == 1) && ref($_[1]);
2327
2328   my $count = abs(shift || 0);
2329
2330   my (@a,$k,$d);                # resulting array, temp, and downgrade
2331   if (ref $_[0])
2332     {
2333     # okay, got object as first
2334     $a[0] = ref $_[0];
2335     }
2336   else
2337     {
2338     # nope, got 1,2 (Class->xxx(1) => Class,1 and not supported)
2339     $a[0] = $class;
2340     $a[0] = shift if $_[0] =~ /^[A-Z].*::/;     # classname as first?
2341     }
2342
2343   no strict 'refs';
2344   # disable downgrading, because Math::BigFLoat->foo('1.0','2.0') needs floats
2345   if (defined ${"$a[0]::downgrade"})
2346     {
2347     $d = ${"$a[0]::downgrade"};
2348     ${"$a[0]::downgrade"} = undef;
2349     }
2350
2351   my $up = ${"$a[0]::upgrade"};
2352   # print "Now in objectify, my class is today $a[0]\n";
2353   if ($count == 0)
2354     {
2355     while (@_)
2356       {
2357       $k = shift;
2358       if (!ref($k))
2359         {
2360         $k = $a[0]->new($k);
2361         }
2362       elsif (!defined $up && ref($k) ne $a[0])
2363         {
2364         # foreign object, try to convert to integer
2365         $k->can('as_number') ?  $k = $k->as_number() : $k = $a[0]->new($k);
2366         }
2367       push @a,$k;
2368       }
2369     }
2370   else
2371     {
2372     while ($count > 0)
2373       {
2374       $count--;
2375       $k = shift;
2376       if (!ref($k))
2377         {
2378         $k = $a[0]->new($k);
2379         }
2380       elsif (!defined $up && ref($k) ne $a[0])
2381         {
2382         # foreign object, try to convert to integer
2383         $k->can('as_number') ?  $k = $k->as_number() : $k = $a[0]->new($k);
2384         }
2385       push @a,$k;
2386       }
2387     push @a,@_;         # return other params, too
2388     }
2389   die "$class objectify needs list context" unless wantarray;
2390   ${"$a[0]::downgrade"} = $d;
2391   @a;
2392   }
2393
2394 sub import
2395   {
2396   my $self = shift;
2397
2398   $IMPORT++;
2399   my @a; my $l = scalar @_;
2400   for ( my $i = 0; $i < $l ; $i++ )
2401     {
2402     if ($_[$i] eq ':constant')
2403       {
2404       # this causes overlord er load to step in
2405       overload::constant integer => sub { $self->new(shift) };
2406       overload::constant binary => sub { $self->new(shift) };
2407       }
2408     elsif ($_[$i] eq 'upgrade')
2409       {
2410       # this causes upgrading
2411       $upgrade = $_[$i+1];              # or undef to disable
2412       $i++;
2413       }
2414     elsif ($_[$i] =~ /^lib$/i)
2415       {
2416       # this causes a different low lib to take care...
2417       $CALC = $_[$i+1] || '';
2418       $i++;
2419       }
2420     else
2421       {
2422       push @a, $_[$i];
2423       }
2424     }
2425   # any non :constant stuff is handled by our parent, Exporter
2426   # even if @_ is empty, to give it a chance
2427   $self->SUPER::import(@a);                     # need it for subclasses
2428   $self->export_to_level(1,$self,@a);           # need it for MBF
2429
2430   # try to load core math lib
2431   my @c = split /\s*,\s*/,$CALC;
2432   push @c,'Calc';                               # if all fail, try this
2433   $CALC = '';                                   # signal error
2434   foreach my $lib (@c)
2435     {
2436     next if ($lib || '') eq '';
2437     $lib = 'Math::BigInt::'.$lib if $lib !~ /^Math::BigInt/i;
2438     $lib =~ s/\.pm$//;
2439     if ($] < 5.006)
2440       {
2441       # Perl < 5.6.0 dies with "out of memory!" when eval() and ':constant' is
2442       # used in the same script, or eval inside import().
2443       my @parts = split /::/, $lib;             # Math::BigInt => Math BigInt
2444       my $file = pop @parts; $file .= '.pm';    # BigInt => BigInt.pm
2445       require File::Spec;
2446       $file = File::Spec->catfile (@parts, $file);
2447       eval { require "$file"; $lib->import( @c ); }
2448       }
2449     else
2450       {
2451       eval "use $lib qw/@c/;";
2452       }
2453     $CALC = $lib, last if $@ eq '';     # no error in loading lib?
2454     }
2455   die "Couldn't load any math lib, not even the default" if $CALC eq '';
2456   }
2457
2458 sub __from_hex
2459   {
2460   # convert a (ref to) big hex string to BigInt, return undef for error
2461   my $hs = shift;
2462
2463   my $x = Math::BigInt->bzero();
2464
2465   # strip underscores
2466   $$hs =~ s/([0-9a-fA-F])_([0-9a-fA-F])/$1$2/g;
2467   $$hs =~ s/([0-9a-fA-F])_([0-9a-fA-F])/$1$2/g;
2468
2469   return $x->bnan() if $$hs !~ /^[\-\+]?0x[0-9A-Fa-f]+$/;
2470
2471   my $sign = '+'; $sign = '-' if ($$hs =~ /^-/);
2472
2473   $$hs =~ s/^[+-]//;                    # strip sign
2474   if ($CALC->can('_from_hex'))
2475     {
2476     $x->{value} = $CALC->_from_hex($hs);
2477     }
2478   else
2479     {
2480     # fallback to pure perl
2481     my $mul = Math::BigInt->bzero(); $mul++;
2482     my $x65536 = Math::BigInt->new(65536);
2483     my $len = CORE::length($$hs)-2;
2484     $len = int($len/4);                 # 4-digit parts, w/o '0x'
2485     my $val; my $i = -4;
2486     while ($len >= 0)
2487       {
2488       $val = substr($$hs,$i,4);
2489       $val =~ s/^[+-]?0x// if $len == 0;        # for last part only because
2490       $val = hex($val);                         # hex does not like wrong chars
2491       $i -= 4; $len --;
2492       $x += $mul * $val if $val != 0;
2493       $mul *= $x65536 if $len >= 0;             # skip last mul
2494       }
2495     }
2496   $x->{sign} = $sign unless $CALC->_is_zero($x->{value});       # no '-0'
2497   $x;
2498   }
2499
2500 sub __from_bin
2501   {
2502   # convert a (ref to) big binary string to BigInt, return undef for error
2503   my $bs = shift;
2504
2505   my $x = Math::BigInt->bzero();
2506   # strip underscores
2507   $$bs =~ s/([01])_([01])/$1$2/g;
2508   $$bs =~ s/([01])_([01])/$1$2/g;
2509   return $x->bnan() if $$bs !~ /^[+-]?0b[01]+$/;
2510
2511   my $sign = '+'; $sign = '-' if ($$bs =~ /^\-/);
2512   $$bs =~ s/^[+-]//;                            # strip sign
2513   if ($CALC->can('_from_bin'))
2514     {
2515     $x->{value} = $CALC->_from_bin($bs);
2516     }
2517   else
2518     {
2519     my $mul = Math::BigInt->bzero(); $mul++;
2520     my $x256 = Math::BigInt->new(256);
2521     my $len = CORE::length($$bs)-2;
2522     $len = int($len/8);                         # 8-digit parts, w/o '0b'
2523     my $val; my $i = -8;
2524     while ($len >= 0)
2525       {
2526       $val = substr($$bs,$i,8);
2527       $val =~ s/^[+-]?0b// if $len == 0;        # for last part only
2528       #$val = oct('0b'.$val);   # does not work on Perl prior to 5.6.0
2529       # slower:
2530       # $val = ('0' x (8-CORE::length($val))).$val if CORE::length($val) < 8;
2531       $val = ord(pack('B8',substr('00000000'.$val,-8,8)));
2532       $i -= 8; $len --;
2533       $x += $mul * $val if $val != 0;
2534       $mul *= $x256 if $len >= 0;               # skip last mul
2535       }
2536     }
2537   $x->{sign} = $sign unless $CALC->_is_zero($x->{value});       # no '-0'
2538   $x;
2539   }
2540
2541 sub _split
2542   {
2543   # (ref to num_str) return num_str
2544   # internal, take apart a string and return the pieces
2545   # strip leading/trailing whitespace, leading zeros, underscore and reject
2546   # invalid input
2547   my $x = shift;
2548
2549   # strip white space at front, also extranous leading zeros
2550   $$x =~ s/^\s*([-]?)0*([0-9])/$1$2/g;  # will not strip '  .2'
2551   $$x =~ s/^\s+//;                      # but this will
2552   $$x =~ s/\s+$//g;                     # strip white space at end
2553
2554   # shortcut, if nothing to split, return early
2555   if ($$x =~ /^[+-]?\d+\z/)
2556     {
2557     $$x =~ s/^([+-])0*([0-9])/$2/; my $sign = $1 || '+';
2558     return (\$sign, $x, \'', \'', \0);
2559     }
2560
2561   # invalid starting char?
2562   return if $$x !~ /^[+-]?(\.?[0-9]|0b[0-1]|0x[0-9a-fA-F])/;
2563
2564   return __from_hex($x) if $$x =~ /^[\-\+]?0x/; # hex string
2565   return __from_bin($x) if $$x =~ /^[\-\+]?0b/; # binary string
2566
2567   # strip underscores between digits
2568   $$x =~ s/(\d)_(\d)/$1$2/g;
2569   $$x =~ s/(\d)_(\d)/$1$2/g;            # do twice for 1_2_3
2570
2571   # some possible inputs:
2572   # 2.1234 # 0.12        # 1          # 1E1 # 2.134E1 # 434E-10 # 1.02009E-2
2573   # .2     # 1_2_3.4_5_6 # 1.4E1_2_3  # 1e3 # +.2
2574
2575   #return if $$x =~ /[Ee].*[Ee]/;       # more than one E => error
2576
2577   my ($m,$e,$last) = split /[Ee]/,$$x;
2578   return if defined $last;              # last defined => 1e2E3 or others
2579   $e = '0' if !defined $e || $e eq "";
2580
2581   # sign,value for exponent,mantint,mantfrac
2582   my ($es,$ev,$mis,$miv,$mfv);
2583   # valid exponent?
2584   if ($e =~ /^([+-]?)0*(\d+)$/) # strip leading zeros
2585     {
2586     $es = $1; $ev = $2;
2587     # valid mantissa?
2588     return if $m eq '.' || $m eq '';
2589     my ($mi,$mf,$lastf) = split /\./,$m;
2590     return if defined $lastf;           # last defined => 1.2.3 or others
2591     $mi = '0' if !defined $mi;
2592     $mi .= '0' if $mi =~ /^[\-\+]?$/;
2593     $mf = '0' if !defined $mf || $mf eq '';
2594     if ($mi =~ /^([+-]?)0*(\d+)$/) # strip leading zeros
2595       {
2596       $mis = $1||'+'; $miv = $2;
2597       return unless ($mf =~ /^(\d*?)0*$/);      # strip trailing zeros
2598       $mfv = $1;
2599       return (\$mis,\$miv,\$mfv,\$es,\$ev);
2600       }
2601     }
2602   return; # NaN, not a number
2603   }
2604
2605 sub as_number
2606   {
2607   # an object might be asked to return itself as bigint on certain overloaded
2608   # operations, this does exactly this, so that sub classes can simple inherit
2609   # it or override with their own integer conversion routine
2610   my $self = shift;
2611
2612   $self->copy();
2613   }
2614
2615 sub as_hex
2616   {
2617   # return as hex string, with prefixed 0x
2618   my $x = shift; $x = $class->new($x) if !ref($x);
2619
2620   return $x->bstr() if $x->{sign} !~ /^[+-]$/;  # inf, nan etc
2621   return '0x0' if $x->is_zero();
2622
2623   my $es = ''; my $s = '';
2624   $s = $x->{sign} if $x->{sign} eq '-';
2625   if ($CALC->can('_as_hex'))
2626     {
2627     $es = ${$CALC->_as_hex($x->{value})};
2628     }
2629   else
2630     {
2631     my $x1 = $x->copy()->babs(); my ($xr,$x10000,$h);
2632     if ($] >= 5.006)
2633       {
2634       $x10000 = Math::BigInt->new (0x10000); $h = 'h4';
2635       }
2636     else
2637       {
2638       $x10000 = Math::BigInt->new (0x1000); $h = 'h3';
2639       }
2640     while (!$x1->is_zero())
2641       {
2642       ($x1, $xr) = bdiv($x1,$x10000);
2643       $es .= unpack($h,pack('v',$xr->numify()));
2644       }
2645     $es = reverse $es;
2646     $es =~ s/^[0]+//;   # strip leading zeros
2647     $s .= '0x';
2648     }
2649   $s . $es;
2650   }
2651
2652 sub as_bin
2653   {
2654   # return as binary string, with prefixed 0b
2655   my $x = shift; $x = $class->new($x) if !ref($x);
2656
2657   return $x->bstr() if $x->{sign} !~ /^[+-]$/;  # inf, nan etc
2658   return '0b0' if $x->is_zero();
2659
2660   my $es = ''; my $s = '';
2661   $s = $x->{sign} if $x->{sign} eq '-';
2662   if ($CALC->can('_as_bin'))
2663     {
2664     $es = ${$CALC->_as_bin($x->{value})};
2665     }
2666   else
2667     {
2668     my $x1 = $x->copy()->babs(); my ($xr,$x10000,$b);
2669     if ($] >= 5.006)
2670       {
2671       $x10000 = Math::BigInt->new (0x10000); $b = 'b16';
2672       }
2673     else
2674       {
2675       $x10000 = Math::BigInt->new (0x1000); $b = 'b12';
2676       }
2677     while (!$x1->is_zero())
2678       {
2679       ($x1, $xr) = bdiv($x1,$x10000);
2680       $es .= unpack($b,pack('v',$xr->numify()));
2681       }
2682     $es = reverse $es;
2683     $es =~ s/^[0]+//;   # strip leading zeros
2684     $s .= '0b';
2685     }
2686   $s . $es;
2687   }
2688
2689 ##############################################################################
2690 # internal calculation routines (others are in Math::BigInt::Calc etc)
2691
2692 sub __lcm
2693   {
2694   # (BINT or num_str, BINT or num_str) return BINT
2695   # does modify first argument
2696   # LCM
2697
2698   my $x = shift; my $ty = shift;
2699   return $x->bnan() if ($x->{sign} eq $nan) || ($ty->{sign} eq $nan);
2700   return $x * $ty / bgcd($x,$ty);
2701   }
2702
2703 sub __gcd
2704   {
2705   # (BINT or num_str, BINT or num_str) return BINT
2706   # does modify both arguments
2707   # GCD -- Euclids algorithm E, Knuth Vol 2 pg 296
2708   my ($x,$ty) = @_;
2709
2710   return $x->bnan() if $x->{sign} !~ /^[+-]$/ || $ty->{sign} !~ /^[+-]$/;
2711
2712   while (!$ty->is_zero())
2713     {
2714     ($x, $ty) = ($ty,bmod($x,$ty));
2715     }
2716   $x;
2717   }
2718
2719 ###############################################################################
2720 # this method return 0 if the object can be modified, or 1 for not
2721 # We use a fast use constant statement here, to avoid costly calls. Subclasses
2722 # may override it with special code (f.i. Math::BigInt::Constant does so)
2723
2724 sub modify () { 0; }
2725
2726 1;
2727 __END__
2728
2729 =head1 NAME
2730
2731 Math::BigInt - Arbitrary size integer math package
2732
2733 =head1 SYNOPSIS
2734
2735   use Math::BigInt;
2736
2737   # Number creation
2738   $x = Math::BigInt->new($str);         # defaults to 0
2739   $nan  = Math::BigInt->bnan();         # create a NotANumber
2740   $zero = Math::BigInt->bzero();        # create a +0
2741   $inf = Math::BigInt->binf();          # create a +inf
2742   $inf = Math::BigInt->binf('-');       # create a -inf
2743   $one = Math::BigInt->bone();          # create a +1
2744   $one = Math::BigInt->bone('-');       # create a -1
2745
2746   # Testing (don't modify their arguments)
2747   # (return true if the condition is met, otherwise false)
2748
2749   $x->is_zero();        # if $x is +0
2750   $x->is_nan();         # if $x is NaN
2751   $x->is_one();         # if $x is +1
2752   $x->is_one('-');      # if $x is -1
2753   $x->is_odd();         # if $x is odd
2754   $x->is_even();        # if $x is even
2755   $x->is_positive();    # if $x >= 0
2756   $x->is_negative();    # if $x <  0
2757   $x->is_inf(sign);     # if $x is +inf, or -inf (sign is default '+')
2758   $x->is_int();         # if $x is an integer (not a float)
2759
2760   # comparing and digit/sign extration
2761   $x->bcmp($y);         # compare numbers (undef,<0,=0,>0)
2762   $x->bacmp($y);        # compare absolutely (undef,<0,=0,>0)
2763   $x->sign();           # return the sign, either +,- or NaN
2764   $x->digit($n);        # return the nth digit, counting from right
2765   $x->digit(-$n);       # return the nth digit, counting from left
2766
2767   # The following all modify their first argument:
2768
2769   $x->bzero();          # set $x to 0
2770   $x->bnan();           # set $x to NaN
2771   $x->bone();           # set $x to +1
2772   $x->bone('-');        # set $x to -1
2773   $x->binf();           # set $x to inf
2774   $x->binf('-');        # set $x to -inf
2775
2776   $x->bneg();           # negation
2777   $x->babs();           # absolute value
2778   $x->bnorm();          # normalize (no-op in BigInt)
2779   $x->bnot();           # two's complement (bit wise not)
2780   $x->binc();           # increment $x by 1
2781   $x->bdec();           # decrement $x by 1
2782
2783   $x->badd($y);         # addition (add $y to $x)
2784   $x->bsub($y);         # subtraction (subtract $y from $x)
2785   $x->bmul($y);         # multiplication (multiply $x by $y)
2786   $x->bdiv($y);         # divide, set $x to quotient
2787                         # return (quo,rem) or quo if scalar
2788
2789   $x->bmod($y);            # modulus (x % y)
2790   $x->bmodpow($exp,$mod);  # modular exponentation (($num**$exp) % $mod))
2791   $x->bmodinv($mod);       # the inverse of $x in the given modulus $mod
2792
2793   $x->bpow($y);            # power of arguments (x ** y)
2794   $x->blsft($y);           # left shift
2795   $x->brsft($y);           # right shift
2796   $x->blsft($y,$n);        # left shift, by base $n (like 10)
2797   $x->brsft($y,$n);        # right shift, by base $n (like 10)
2798
2799   $x->band($y);            # bitwise and
2800   $x->bior($y);            # bitwise inclusive or
2801   $x->bxor($y);            # bitwise exclusive or
2802   $x->bnot();              # bitwise not (two's complement)
2803
2804   $x->bsqrt();             # calculate square-root
2805   $x->bfac();              # factorial of $x (1*2*3*4*..$x)
2806
2807   $x->round($A,$P,$mode);  # round to accuracy or precision using mode $r
2808   $x->bround($N);          # accuracy: preserve $N digits
2809   $x->bfround($N);         # round to $Nth digit, no-op for BigInts
2810
2811   # The following do not modify their arguments in BigInt,
2812   # but do so in BigFloat:
2813
2814   $x->bfloor();            # return integer less or equal than $x
2815   $x->bceil();             # return integer greater or equal than $x
2816
2817   # The following do not modify their arguments:
2818
2819   bgcd(@values);           # greatest common divisor (no OO style)
2820   blcm(@values);           # lowest common multiplicator (no OO style)
2821
2822   $x->length();            # return number of digits in number
2823   ($x,$f) = $x->length();  # length of number and length of fraction part,
2824                            # latter is always 0 digits long for BigInt's
2825
2826   $x->exponent();          # return exponent as BigInt
2827   $x->mantissa();          # return (signed) mantissa as BigInt
2828   $x->parts();             # return (mantissa,exponent) as BigInt
2829   $x->copy();              # make a true copy of $x (unlike $y = $x;)
2830   $x->as_number();         # return as BigInt (in BigInt: same as copy())
2831
2832   # conversation to string (do not modify their argument)
2833   $x->bstr();              # normalized string
2834   $x->bsstr();             # normalized string in scientific notation
2835   $x->as_hex();            # as signed hexadecimal string with prefixed 0x
2836   $x->as_bin();            # as signed binary string with prefixed 0b
2837
2838
2839   # precision and accuracy (see section about rounding for more)
2840   $x->precision();         # return P of $x (or global, if P of $x undef)
2841   $x->precision($n);       # set P of $x to $n
2842   $x->accuracy();          # return A of $x (or global, if A of $x undef)
2843   $x->accuracy($n);        # set A $x to $n
2844
2845   # Global methods
2846   Math::BigInt->precision(); # get/set global P for all BigInt objects
2847   Math::BigInt->accuracy();  # get/set global A for all BigInt objects
2848   Math::BigInt->config();    # return hash containing configuration
2849
2850 =head1 DESCRIPTION
2851
2852 All operators (inlcuding basic math operations) are overloaded if you
2853 declare your big integers as
2854
2855   $i = new Math::BigInt '123_456_789_123_456_789';
2856
2857 Operations with overloaded operators preserve the arguments which is
2858 exactly what you expect.
2859
2860 =over 2
2861
2862 =item Canonical notation
2863
2864 Big integer values are strings of the form C</^[+-]\d+$/> with leading
2865 zeros suppressed.
2866
2867    '-0'                            canonical value '-0', normalized '0'
2868    '   -123_123_123'               canonical value '-123123123'
2869    '1_23_456_7890'                 canonical value '1234567890'
2870
2871 =item Input
2872
2873 Input values to these routines may be either Math::BigInt objects or
2874 strings of the form C</^\s*[+-]?[\d]+\.?[\d]*E?[+-]?[\d]*$/>.
2875
2876 You can include one underscore between any two digits.
2877
2878 This means integer values like 1.01E2 or even 1000E-2 are also accepted.
2879 Non integer values result in NaN.
2880
2881 Math::BigInt::new() defaults to 0, while Math::BigInt::new('') results
2882 in 'NaN'.
2883
2884 bnorm() on a BigInt object is now effectively a no-op, since the numbers
2885 are always stored in normalized form. On a string, it creates a BigInt
2886 object.
2887
2888 =item Output
2889
2890 Output values are BigInt objects (normalized), except for bstr(), which
2891 returns a string in normalized form.
2892 Some routines (C<is_odd()>, C<is_even()>, C<is_zero()>, C<is_one()>,
2893 C<is_nan()>) return true or false, while others (C<bcmp()>, C<bacmp()>)
2894 return either undef, <0, 0 or >0 and are suited for sort.
2895
2896 =back
2897
2898 =head1 METHODS
2899
2900 Each of the methods below (except config(), accuracy() and precision())
2901 accepts three additional parameters. These arguments $A, $P and $R are
2902 accuracy, precision and round_mode. Please see the section about
2903 L<ACCURACY and PRECISION> for more information.
2904
2905 =head2 config
2906
2907         use Data::Dumper;
2908
2909         print Dumper ( Math::BigInt->config() );
2910         print Math::BigInt->config()->{lib},"\n";
2911
2912 Returns a hash containing the configuration, e.g. the version number, lib
2913 loaded etc. The following hash keys are currently filled in with the
2914 appropriate information.
2915
2916         key             Description
2917                         Example
2918         ============================================================
2919         lib             Name of the Math library
2920                         Math::BigInt::Calc
2921         lib_version     Version of 'lib'
2922                         0.30
2923         class           The class of config you just called
2924                         Math::BigInt
2925         upgrade         To which class numbers are upgraded
2926                         Math::BigFloat
2927         downgrade       To which class numbers are downgraded
2928                         undef
2929         precision       Global precision
2930                         undef
2931         accuracy        Global accuracy
2932                         undef
2933         round_mode      Global round mode
2934                         even
2935         version         version number of the class you used
2936                         1.61
2937         div_scale       Fallback acccuracy for div
2938                         40
2939
2940 It is currently not supported to set the configuration parameters by passing
2941 a hash ref to C<config()>.
2942
2943 =head2 accuracy
2944
2945         $x->accuracy(5);                # local for $x
2946         CLASS->accuracy(5);             # global for all members of CLASS
2947         $A = $x->accuracy();            # read out
2948         $A = CLASS->accuracy();         # read out
2949
2950 Set or get the global or local accuracy, aka how many significant digits the
2951 results have.
2952
2953 Please see the section about L<ACCURACY AND PRECISION> for further details.
2954
2955 Value must be greater than zero. Pass an undef value to disable it:
2956
2957         $x->accuracy(undef);
2958         Math::BigInt->accuracy(undef);
2959
2960 Returns the current accuracy. For C<$x->accuracy()> it will return either the
2961 local accuracy, or if not defined, the global. This means the return value
2962 represents the accuracy that will be in effect for $x:
2963
2964         $y = Math::BigInt->new(1234567);        # unrounded
2965         print Math::BigInt->accuracy(4),"\n";   # set 4, print 4
2966         $x = Math::BigInt->new(123456);         # will be automatically rounded
2967         print "$x $y\n";                        # '123500 1234567'
2968         print $x->accuracy(),"\n";              # will be 4
2969         print $y->accuracy(),"\n";              # also 4, since global is 4
2970         print Math::BigInt->accuracy(5),"\n";   # set to 5, print 5
2971         print $x->accuracy(),"\n";              # still 4
2972         print $y->accuracy(),"\n";              # 5, since global is 5
2973
2974 Note: Works also for subclasses like Math::BigFloat. Each class has it's own
2975 globals separated from Math::BigInt, but it is possible to subclass
2976 Math::BigInt and make the globals of the subclass aliases to the ones from
2977 Math::BigInt.
2978
2979 =head2 precision
2980
2981         $x->precision(-2);              # local for $x, round right of the dot
2982         $x->precision(2);               # ditto, but round left of the dot
2983         CLASS->accuracy(5);             # global for all members of CLASS
2984         CLASS->precision(-5);           # ditto
2985         $P = CLASS->precision();        # read out
2986         $P = $x->precision();           # read out
2987
2988 Set or get the global or local precision, aka how many digits the result has
2989 after the dot (or where to round it when passing a positive number). In
2990 Math::BigInt, passing a negative number precision has no effect since no
2991 numbers have digits after the dot.
2992
2993 Please see the section about L<ACCURACY AND PRECISION> for further details.
2994
2995 Value must be greater than zero. Pass an undef value to disable it:
2996
2997         $x->precision(undef);
2998         Math::BigInt->precision(undef);
2999
3000 Returns the current precision. For C<$x->precision()> it will return either the
3001 local precision of $x, or if not defined, the global. This means the return
3002 value represents the accuracy that will be in effect for $x:
3003
3004         $y = Math::BigInt->new(1234567);        # unrounded
3005         print Math::BigInt->precision(4),"\n";  # set 4, print 4
3006         $x = Math::BigInt->new(123456);         # will be automatically rounded
3007
3008 Note: Works also for subclasses like Math::BigFloat. Each class has it's own
3009 globals separated from Math::BigInt, but it is possible to subclass
3010 Math::BigInt and make the globals of the subclass aliases to the ones from
3011 Math::BigInt.
3012
3013 =head2 brsft
3014
3015         $x->brsft($y,$n);
3016
3017 Shifts $x right by $y in base $n. Default is base 2, used are usually 10 and
3018 2, but others work, too.
3019
3020 Right shifting usually amounts to dividing $x by $n ** $y and truncating the
3021 result:
3022
3023
3024         $x = Math::BigInt->new(10);
3025         $x->brsft(1);                   # same as $x >> 1: 5
3026         $x = Math::BigInt->new(1234);
3027         $x->brsft(2,10);                # result 12
3028
3029 There is one exception, and that is base 2 with negative $x:
3030
3031
3032         $x = Math::BigInt->new(-5);
3033         print $x->brsft(1);
3034
3035 This will print -3, not -2 (as it would if you divide -5 by 2 and truncate the
3036 result).
3037
3038 =head2 new
3039
3040         $x = Math::BigInt->new($str,$A,$P,$R);
3041
3042 Creates a new BigInt object from a string or another BigInt object. The
3043 input is accepted as decimal, hex (with leading '0x') or binary (with leading
3044 '0b').
3045
3046 =head2 bnan
3047
3048         $x = Math::BigInt->bnan();
3049
3050 Creates a new BigInt object representing NaN (Not A Number).
3051 If used on an object, it will set it to NaN:
3052
3053         $x->bnan();
3054
3055 =head2 bzero
3056
3057         $x = Math::BigInt->bzero();
3058
3059 Creates a new BigInt object representing zero.
3060 If used on an object, it will set it to zero:
3061
3062         $x->bzero();
3063
3064 =head2 binf
3065
3066         $x = Math::BigInt->binf($sign);
3067
3068 Creates a new BigInt object representing infinity. The optional argument is
3069 either '-' or '+', indicating whether you want infinity or minus infinity.
3070 If used on an object, it will set it to infinity:
3071
3072         $x->binf();
3073         $x->binf('-');
3074
3075 =head2 bone
3076
3077         $x = Math::BigInt->binf($sign);
3078
3079 Creates a new BigInt object representing one. The optional argument is
3080 either '-' or '+', indicating whether you want one or minus one.
3081 If used on an object, it will set it to one:
3082
3083         $x->bone();             # +1
3084         $x->bone('-');          # -1
3085
3086 =head2 is_one()/is_zero()/is_nan()/is_inf()
3087
3088
3089         $x->is_zero();                  # true if arg is +0
3090         $x->is_nan();                   # true if arg is NaN
3091         $x->is_one();                   # true if arg is +1
3092         $x->is_one('-');                # true if arg is -1
3093         $x->is_inf();                   # true if +inf
3094         $x->is_inf('-');                # true if -inf (sign is default '+')
3095
3096 These methods all test the BigInt for beeing one specific value and return
3097 true or false depending on the input. These are faster than doing something
3098 like:
3099
3100         if ($x == 0)
3101
3102 =head2 is_positive()/is_negative()
3103
3104         $x->is_positive();              # true if >= 0
3105         $x->is_negative();              # true if <  0
3106
3107 The methods return true if the argument is positive or negative, respectively.
3108 C<NaN> is neither positive nor negative, while C<+inf> counts as positive, and
3109 C<-inf> is negative. A C<zero> is positive.
3110
3111 These methods are only testing the sign, and not the value.
3112
3113 =head2 is_odd()/is_even()/is_int()
3114
3115         $x->is_odd();                   # true if odd, false for even
3116         $x->is_even();                  # true if even, false for odd
3117         $x->is_int();                   # true if $x is an integer
3118
3119 The return true when the argument satisfies the condition. C<NaN>, C<+inf>,
3120 C<-inf> are not integers and are neither odd nor even.
3121
3122 =head2 bcmp
3123
3124         $x->bcmp($y);
3125
3126 Compares $x with $y and takes the sign into account.
3127 Returns -1, 0, 1 or undef.
3128
3129 =head2 bacmp
3130
3131         $x->bacmp($y);
3132
3133 Compares $x with $y while ignoring their. Returns -1, 0, 1 or undef.
3134
3135 =head2 sign
3136
3137         $x->sign();
3138
3139 Return the sign, of $x, meaning either C<+>, C<->, C<-inf>, C<+inf> or NaN.
3140
3141 =head2 bcmp
3142
3143   $x->digit($n);                # return the nth digit, counting from right
3144
3145 =head2 bneg
3146
3147         $x->bneg();
3148
3149 Negate the number, e.g. change the sign between '+' and '-', or between '+inf'
3150 and '-inf', respectively. Does nothing for NaN or zero.
3151
3152 =head2 babs
3153
3154         $x->babs();
3155
3156 Set the number to it's absolute value, e.g. change the sign from '-' to '+'
3157 and from '-inf' to '+inf', respectively. Does nothing for NaN or positive
3158 numbers.
3159
3160 =head2 bnorm
3161
3162         $x->bnorm();                    # normalize (no-op)
3163
3164 =head2 bnot
3165
3166         $x->bnot();                     # two's complement (bit wise not)
3167
3168 =head2 binc
3169
3170         $x->binc();                     # increment x by 1
3171
3172 =head2 bdec
3173
3174         $x->bdec();                     # decrement x by 1
3175
3176 =head2 badd
3177
3178         $x->badd($y);                   # addition (add $y to $x)
3179
3180 =head2 bsub
3181
3182         $x->bsub($y);                   # subtraction (subtract $y from $x)
3183
3184 =head2 bmul
3185
3186         $x->bmul($y);                   # multiplication (multiply $x by $y)
3187
3188 =head2 bdiv
3189
3190         $x->bdiv($y);                   # divide, set $x to quotient
3191                                         # return (quo,rem) or quo if scalar
3192
3193 =head2 bmod
3194
3195         $x->bmod($y);                   # modulus (x % y)
3196
3197 =head2 bmodinv
3198
3199         num->bmodinv($mod);             # modular inverse
3200
3201 Returns the inverse of C<$num> in the given modulus C<$mod>.  'C<NaN>' is
3202 returned unless C<$num> is relatively prime to C<$mod>, i.e. unless
3203 C<bgcd($num, $mod)==1>.
3204
3205 =head2 bmodpow
3206
3207         $num->bmodpow($exp,$mod);       # modular exponentation
3208                                         # ($num**$exp % $mod)
3209
3210 Returns the value of C<$num> taken to the power C<$exp> in the modulus
3211 C<$mod> using binary exponentation.  C<bmodpow> is far superior to
3212 writing
3213
3214         $num ** $exp % $mod
3215
3216 because C<bmodpow> is much faster--it reduces internal variables into
3217 the modulus whenever possible, so it operates on smaller numbers.
3218
3219 C<bmodpow> also supports negative exponents.
3220
3221         bmodpow($num, -1, $mod)
3222
3223 is exactly equivalent to
3224
3225         bmodinv($num, $mod)
3226
3227 =head2 bpow
3228
3229         $x->bpow($y);                   # power of arguments (x ** y)
3230
3231 =head2 blsft
3232
3233         $x->blsft($y);          # left shift
3234         $x->blsft($y,$n);       # left shift, in base $n (like 10)
3235
3236 =head2 brsft
3237
3238         $x->brsft($y);          # right shift
3239         $x->brsft($y,$n);       # right shift, in base $n (like 10)
3240
3241 =head2 band
3242
3243         $x->band($y);                   # bitwise and
3244
3245 =head2 bior
3246
3247         $x->bior($y);                   # bitwise inclusive or
3248
3249 =head2 bxor
3250
3251         $x->bxor($y);                   # bitwise exclusive or
3252
3253 =head2 bnot
3254
3255         $x->bnot();                     # bitwise not (two's complement)
3256
3257 =head2 bsqrt
3258
3259         $x->bsqrt();                    # calculate square-root
3260
3261 =head2 bfac
3262
3263         $x->bfac();                     # factorial of $x (1*2*3*4*..$x)
3264
3265 =head2 round
3266
3267         $x->round($A,$P,$round_mode);
3268
3269 Round $x to accuracy C<$A> or precision C<$P> using the round mode
3270 C<$round_mode>.
3271
3272 =head2 bround
3273
3274         $x->bround($N);               # accuracy: preserve $N digits
3275
3276 =head2 bfround
3277
3278         $x->bfround($N);              # round to $Nth digit, no-op for BigInts
3279
3280 =head2 bfloor
3281
3282         $x->bfloor();
3283
3284 Set $x to the integer less or equal than $x. This is a no-op in BigInt, but
3285 does change $x in BigFloat.
3286
3287 =head2 bceil
3288
3289         $x->bceil();
3290
3291 Set $x to the integer greater or equal than $x. This is a no-op in BigInt, but
3292 does change $x in BigFloat.
3293
3294 =head2 bgcd
3295
3296         bgcd(@values);          # greatest common divisor (no OO style)
3297
3298 =head2 blcm
3299
3300         blcm(@values);          # lowest common multiplicator (no OO style)
3301
3302 head2 length
3303
3304         $x->length();
3305         ($xl,$fl) = $x->length();
3306
3307 Returns the number of digits in the decimal representation of the number.
3308 In list context, returns the length of the integer and fraction part. For
3309 BigInt's, the length of the fraction part will always be 0.
3310
3311 =head2 exponent
3312
3313         $x->exponent();
3314
3315 Return the exponent of $x as BigInt.
3316
3317 =head2 mantissa
3318
3319         $x->mantissa();
3320
3321 Return the signed mantissa of $x as BigInt.
3322
3323 =head2 parts
3324
3325         $x->parts();            # return (mantissa,exponent) as BigInt
3326
3327 =head2 copy
3328
3329         $x->copy();             # make a true copy of $x (unlike $y = $x;)
3330
3331 =head2 as_number
3332
3333         $x->as_number();        # return as BigInt (in BigInt: same as copy())
3334
3335 =head2 bsrt
3336
3337         $x->bstr();             # return normalized string
3338
3339 =head2 bsstr
3340
3341         $x->bsstr();            # normalized string in scientific notation
3342
3343 =head2 as_hex
3344
3345         $x->as_hex();           # as signed hexadecimal string with prefixed 0x
3346
3347 =head2 as_bin
3348
3349         $x->as_bin();           # as signed binary string with prefixed 0b
3350
3351 =head1 ACCURACY and PRECISION
3352
3353 Since version v1.33, Math::BigInt and Math::BigFloat have full support for
3354 accuracy and precision based rounding, both automatically after every
3355 operation as well as manually.
3356
3357 This section describes the accuracy/precision handling in Math::Big* as it
3358 used to be and as it is now, complete with an explanation of all terms and
3359 abbreviations.
3360
3361 Not yet implemented things (but with correct description) are marked with '!',
3362 things that need to be answered are marked with '?'.
3363
3364 In the next paragraph follows a short description of terms used here (because
3365 these may differ from terms used by others people or documentation).
3366
3367 During the rest of this document, the shortcuts A (for accuracy), P (for
3368 precision), F (fallback) and R (rounding mode) will be used.
3369
3370 =head2 Precision P
3371
3372 A fixed number of digits before (positive) or after (negative)
3373 the decimal point. For example, 123.45 has a precision of -2. 0 means an
3374 integer like 123 (or 120). A precision of 2 means two digits to the left
3375 of the decimal point are zero, so 123 with P = 1 becomes 120. Note that
3376 numbers with zeros before the decimal point may have different precisions,
3377 because 1200 can have p = 0, 1 or 2 (depending on what the inital value
3378 was). It could also have p < 0, when the digits after the decimal point
3379 are zero.
3380
3381 The string output (of floating point numbers) will be padded with zeros:
3382
3383         Initial value   P       A       Result          String
3384         ------------------------------------------------------------
3385         1234.01         -3              1000            1000
3386         1234            -2              1200            1200
3387         1234.5          -1              1230            1230
3388         1234.001        1               1234            1234.0
3389         1234.01         0               1234            1234
3390         1234.01         2               1234.01         1234.01
3391         1234.01         5               1234.01         1234.01000
3392
3393 For BigInts, no padding occurs.
3394
3395 =head2 Accuracy A
3396
3397 Number of significant digits. Leading zeros are not counted. A
3398 number may have an accuracy greater than the non-zero digits
3399 when there are zeros in it or trailing zeros. For example, 123.456 has
3400 A of 6, 10203 has 5, 123.0506 has 7, 123.450000 has 8 and 0.000123 has 3.
3401
3402 The string output (of floating point numbers) will be padded with zeros:
3403
3404         Initial value   P       A       Result          String
3405         ------------------------------------------------------------
3406         1234.01                 3       1230            1230
3407         1234.01                 6       1234.01         1234.01
3408         1234.1                  8       1234.1          1234.1000
3409
3410 For BigInts, no padding occurs.
3411
3412 =head2 Fallback F
3413
3414 When both A and P are undefined, this is used as a fallback accuracy when
3415 dividing numbers.
3416
3417 =head2 Rounding mode R
3418
3419 When rounding a number, different 'styles' or 'kinds'
3420 of rounding are possible. (Note that random rounding, as in
3421 Math::Round, is not implemented.)
3422
3423 =over 2
3424
3425 =item 'trunc'
3426
3427 truncation invariably removes all digits following the
3428 rounding place, replacing them with zeros. Thus, 987.65 rounded
3429 to tens (P=1) becomes 980, and rounded to the fourth sigdig
3430 becomes 987.6 (A=4). 123.456 rounded to the second place after the
3431 decimal point (P=-2) becomes 123.46.
3432
3433 All other implemented styles of rounding attempt to round to the
3434 "nearest digit." If the digit D immediately to the right of the
3435 rounding place (skipping the decimal point) is greater than 5, the
3436 number is incremented at the rounding place (possibly causing a
3437 cascade of incrementation): e.g. when rounding to units, 0.9 rounds
3438 to 1, and -19.9 rounds to -20. If D < 5, the number is similarly
3439 truncated at the rounding place: e.g. when rounding to units, 0.4
3440 rounds to 0, and -19.4 rounds to -19.
3441
3442 However the results of other styles of rounding differ if the
3443 digit immediately to the right of the rounding place (skipping the
3444 decimal point) is 5 and if there are no digits, or no digits other
3445 than 0, after that 5. In such cases:
3446
3447 =item 'even'
3448
3449 rounds the digit at the rounding place to 0, 2, 4, 6, or 8
3450 if it is not already. E.g., when rounding to the first sigdig, 0.45
3451 becomes 0.4, -0.55 becomes -0.6, but 0.4501 becomes 0.5.
3452
3453 =item 'odd'
3454
3455 rounds the digit at the rounding place to 1, 3, 5, 7, or 9 if
3456 it is not already. E.g., when rounding to the first sigdig, 0.45
3457 becomes 0.5, -0.55 becomes -0.5, but 0.5501 becomes 0.6.
3458
3459 =item '+inf'
3460
3461 round to plus infinity, i.e. always round up. E.g., when
3462 rounding to the first sigdig, 0.45 becomes 0.5, -0.55 becomes -0.5,
3463 and 0.4501 also becomes 0.5.
3464
3465 =item '-inf'
3466
3467 round to minus infinity, i.e. always round down. E.g., when
3468 rounding to the first sigdig, 0.45 becomes 0.4, -0.55 becomes -0.6,
3469 but 0.4501 becomes 0.5.
3470
3471 =item 'zero'
3472
3473 round to zero, i.e. positive numbers down, negative ones up.
3474 E.g., when rounding to the first sigdig, 0.45 becomes 0.4, -0.55
3475 becomes -0.5, but 0.4501 becomes 0.5.
3476
3477 =back
3478
3479 The handling of A & P in MBI/MBF (the old core code shipped with Perl
3480 versions <= 5.7.2) is like this:
3481
3482 =over 2
3483
3484 =item Precision
3485
3486   * ffround($p) is able to round to $p number of digits after the decimal
3487     point
3488   * otherwise P is unused
3489
3490 =item Accuracy (significant digits)
3491
3492   * fround($a) rounds to $a significant digits
3493   * only fdiv() and fsqrt() take A as (optional) paramater
3494     + other operations simply create the same number (fneg etc), or more (fmul)
3495       of digits
3496     + rounding/truncating is only done when explicitly calling one of fround
3497       or ffround, and never for BigInt (not implemented)
3498   * fsqrt() simply hands its accuracy argument over to fdiv.
3499   * the documentation and the comment in the code indicate two different ways
3500     on how fdiv() determines the maximum number of digits it should calculate,
3501     and the actual code does yet another thing
3502     POD:
3503       max($Math::BigFloat::div_scale,length(dividend)+length(divisor))
3504     Comment:
3505       result has at most max(scale, length(dividend), length(divisor)) digits
3506     Actual code:
3507       scale = max(scale, length(dividend)-1,length(divisor)-1);
3508       scale += length(divisior) - length(dividend);
3509     So for lx = 3, ly = 9, scale = 10, scale will actually be 16 (10+9-3).
3510     Actually, the 'difference' added to the scale is calculated from the
3511     number of "significant digits" in dividend and divisor, which is derived
3512     by looking at the length of the mantissa. Which is wrong, since it includes
3513     the + sign (oups) and actually gets 2 for '+100' and 4 for '+101'. Oups
3514     again. Thus 124/3 with div_scale=1 will get you '41.3' based on the strange
3515     assumption that 124 has 3 significant digits, while 120/7 will get you
3516     '17', not '17.1' since 120 is thought to have 2 significant digits.
3517     The rounding after the division then uses the remainder and $y to determine
3518     wether it must round up or down.
3519  ?  I have no idea which is the right way. That's why I used a slightly more
3520  ?  simple scheme and tweaked the few failing testcases to match it.
3521
3522 =back
3523
3524 This is how it works now:
3525
3526 =over 2
3527
3528 =item Setting/Accessing
3529
3530   * You can set the A global via Math::BigInt->accuracy() or
3531     Math::BigFloat->accuracy() or whatever class you are using.
3532   * You can also set P globally by using Math::SomeClass->precision() likewise.
3533   * Globals are classwide, and not inherited by subclasses.
3534   * to undefine A, use Math::SomeCLass->accuracy(undef);
3535   * to undefine P, use Math::SomeClass->precision(undef);
3536   * Setting Math::SomeClass->accuracy() clears automatically
3537     Math::SomeClass->precision(), and vice versa.
3538   * To be valid, A must be > 0, P can have any value.
3539   * If P is negative, this means round to the P'th place to the right of the
3540     decimal point; positive values mean to the left of the decimal point.
3541     P of 0 means round to integer.
3542   * to find out the current global A, take Math::SomeClass->accuracy()
3543   * to find out the current global P, take Math::SomeClass->precision()
3544   * use $x->accuracy() respective $x->precision() for the local setting of $x.
3545   * Please note that $x->accuracy() respecive $x->precision() fall back to the
3546     defined globals, when $x's A or P is not set.
3547
3548 =item Creating numbers
3549
3550   * When you create a number, you can give it's desired A or P via:
3551     $x = Math::BigInt->new($number,$A,$P);
3552   * Only one of A or P can be defined, otherwise the result is NaN
3553   * If no A or P is give ($x = Math::BigInt->new($number) form), then the
3554     globals (if set) will be used. Thus changing the global defaults later on
3555     will not change the A or P of previously created numbers (i.e., A and P of
3556     $x will be what was in effect when $x was created)
3557   * If given undef for A and P, B<no> rounding will occur, and the globals will
3558     B<not> be used. This is used by subclasses to create numbers without
3559     suffering rounding in the parent. Thus a subclass is able to have it's own
3560     globals enforced upon creation of a number by using
3561     $x = Math::BigInt->new($number,undef,undef):
3562
3563         use Math::Bigint::SomeSubclass;
3564         use Math::BigInt;
3565
3566         Math::BigInt->accuracy(2);
3567         Math::BigInt::SomeSubClass->accuracy(3);
3568         $x = Math::BigInt::SomeSubClass->new(1234);
3569
3570     $x is now 1230, and not 1200. A subclass might choose to implement
3571     this otherwise, e.g. falling back to the parent's A and P.
3572
3573 =item Usage
3574
3575   * If A or P are enabled/defined, they are used to round the result of each
3576     operation according to the rules below
3577   * Negative P is ignored in Math::BigInt, since BigInts never have digits
3578     after the decimal point
3579   * Math::BigFloat uses Math::BigInts internally, but setting A or P inside
3580     Math::BigInt as globals should not tamper with the parts of a BigFloat.
3581     Thus a flag is used to mark all Math::BigFloat numbers as 'never round'
3582
3583 =item Precedence
3584
3585   * It only makes sense that a number has only one of A or P at a time.
3586     Since you can set/get both A and P, there is a rule that will practically
3587     enforce only A or P to be in effect at a time, even if both are set.
3588     This is called precedence.
3589   * If two objects are involved in an operation, and one of them has A in
3590     effect, and the other P, this results in an error (NaN).
3591   * A takes precendence over P (Hint: A comes before P). If A is defined, it
3592     is used, otherwise P is used. If neither of them is defined, nothing is
3593     used, i.e. the result will have as many digits as it can (with an
3594     exception for fdiv/fsqrt) and will not be rounded.
3595   * There is another setting for fdiv() (and thus for fsqrt()). If neither of
3596     A or P is defined, fdiv() will use a fallback (F) of $div_scale digits.
3597     If either the dividend's or the divisor's mantissa has more digits than
3598     the value of F, the higher value will be used instead of F.
3599     This is to limit the digits (A) of the result (just consider what would
3600     happen with unlimited A and P in the case of 1/3 :-)
3601   * fdiv will calculate (at least) 4 more digits than required (determined by
3602     A, P or F), and, if F is not used, round the result
3603     (this will still fail in the case of a result like 0.12345000000001 with A
3604     or P of 5, but this can not be helped - or can it?)
3605   * Thus you can have the math done by on Math::Big* class in three modes:
3606     + never round (this is the default):
3607       This is done by setting A and P to undef. No math operation
3608       will round the result, with fdiv() and fsqrt() as exceptions to guard
3609       against overflows. You must explicitely call bround(), bfround() or
3610       round() (the latter with parameters).
3611       Note: Once you have rounded a number, the settings will 'stick' on it
3612       and 'infect' all other numbers engaged in math operations with it, since
3613       local settings have the highest precedence. So, to get SaferRound[tm],
3614       use a copy() before rounding like this:
3615
3616         $x = Math::BigFloat->new(12.34);
3617         $y = Math::BigFloat->new(98.76);
3618         $z = $x * $y;                           # 1218.6984
3619         print $x->copy()->fround(3);            # 12.3 (but A is now 3!)
3620         $z = $x * $y;                           # still 1218.6984, without
3621                                                 # copy would have been 1210!
3622
3623     + round after each op:
3624       After each single operation (except for testing like is_zero()), the
3625       method round() is called and the result is rounded appropriately. By
3626       setting proper values for A and P, you can have all-the-same-A or
3627       all-the-same-P modes. For example, Math::Currency might set A to undef,
3628       and P to -2, globally.
3629
3630  ?Maybe an extra option that forbids local A & P settings would be in order,
3631  ?so that intermediate rounding does not 'poison' further math?
3632
3633 =item Overriding globals
3634
3635   * you will be able to give A, P and R as an argument to all the calculation
3636     routines; the second parameter is A, the third one is P, and the fourth is
3637     R (shift right by one for binary operations like badd). P is used only if
3638     the first parameter (A) is undefined. These three parameters override the
3639     globals in the order detailed as follows, i.e. the first defined value
3640     wins:
3641     (local: per object, global: global default, parameter: argument to sub)
3642       + parameter A
3643       + parameter P
3644       + local A (if defined on both of the operands: smaller one is taken)
3645       + local P (if defined on both of the operands: bigger one is taken)
3646       + global A
3647       + global P
3648       + global F
3649   * fsqrt() will hand its arguments to fdiv(), as it used to, only now for two
3650     arguments (A and P) instead of one
3651
3652 =item Local settings
3653
3654   * You can set A and P locally by using $x->accuracy() and $x->precision()
3655     and thus force different A and P for different objects/numbers.
3656   * Setting A or P this way immediately rounds $x to the new value.
3657   * $x->accuracy() clears $x->precision(), and vice versa.
3658
3659 =item Rounding
3660
3661   * the rounding routines will use the respective global or local settings.
3662     fround()/bround() is for accuracy rounding, while ffround()/bfround()
3663     is for precision
3664   * the two rounding functions take as the second parameter one of the
3665     following rounding modes (R):
3666     'even', 'odd', '+inf', '-inf', 'zero', 'trunc'
3667   * you can set and get the global R by using Math::SomeClass->round_mode()
3668     or by setting $Math::SomeClass::round_mode
3669   * after each operation, $result->round() is called, and the result may
3670     eventually be rounded (that is, if A or P were set either locally,
3671     globally or as parameter to the operation)
3672   * to manually round a number, call $x->round($A,$P,$round_mode);
3673     this will round the number by using the appropriate rounding function
3674     and then normalize it.
3675   * rounding modifies the local settings of the number:
3676
3677         $x = Math::BigFloat->new(123.456);
3678         $x->accuracy(5);
3679         $x->bround(4);
3680
3681     Here 4 takes precedence over 5, so 123.5 is the result and $x->accuracy()
3682     will be 4 from now on.
3683
3684 =item Default values
3685
3686   * R: 'even'
3687   * F: 40
3688   * A: undef
3689   * P: undef
3690
3691 =item Remarks
3692
3693   * The defaults are set up so that the new code gives the same results as
3694     the old code (except in a few cases on fdiv):
3695     + Both A and P are undefined and thus will not be used for rounding
3696       after each operation.
3697     + round() is thus a no-op, unless given extra parameters A and P
3698
3699 =back
3700
3701 =head1 INTERNALS
3702
3703 The actual numbers are stored as unsigned big integers (with seperate sign).
3704 You should neither care about nor depend on the internal representation; it
3705 might change without notice. Use only method calls like C<< $x->sign(); >>
3706 instead relying on the internal hash keys like in C<< $x->{sign}; >>.
3707
3708 =head2 MATH LIBRARY
3709
3710 Math with the numbers is done (by default) by a module called
3711 Math::BigInt::Calc. This is equivalent to saying:
3712
3713         use Math::BigInt lib => 'Calc';
3714
3715 You can change this by using:
3716
3717         use Math::BigInt lib => 'BitVect';
3718
3719 The following would first try to find Math::BigInt::Foo, then
3720 Math::BigInt::Bar, and when this also fails, revert to Math::BigInt::Calc:
3721
3722         use Math::BigInt lib => 'Foo,Math::BigInt::Bar';
3723
3724 Calc.pm uses as internal format an array of elements of some decimal base
3725 (usually 1e5 or 1e7) with the least significant digit first, while BitVect.pm
3726 uses a bit vector of base 2, most significant bit first. Other modules might
3727 use even different means of representing the numbers. See the respective
3728 module documentation for further details.
3729
3730 =head2 SIGN
3731
3732 The sign is either '+', '-', 'NaN', '+inf' or '-inf' and stored seperately.
3733
3734 A sign of 'NaN' is used to represent the result when input arguments are not
3735 numbers or as a result of 0/0. '+inf' and '-inf' represent plus respectively
3736 minus infinity. You will get '+inf' when dividing a positive number by 0, and
3737 '-inf' when dividing any negative number by 0.
3738
3739 =head2 mantissa(), exponent() and parts()
3740
3741 C<mantissa()> and C<exponent()> return the said parts of the BigInt such
3742 that:
3743
3744         $m = $x->mantissa();
3745         $e = $x->exponent();
3746         $y = $m * ( 10 ** $e );
3747         print "ok\n" if $x == $y;
3748
3749 C<< ($m,$e) = $x->parts() >> is just a shortcut that gives you both of them
3750 in one go. Both the returned mantissa and exponent have a sign.
3751
3752 Currently, for BigInts C<$e> will be always 0, except for NaN, +inf and -inf,
3753 where it will be NaN; and for $x == 0, where it will be 1
3754 (to be compatible with Math::BigFloat's internal representation of a zero as
3755 C<0E1>).
3756
3757 C<$m> will always be a copy of the original number. The relation between $e
3758 and $m might change in the future, but will always be equivalent in a
3759 numerical sense, e.g. $m might get minimized.
3760
3761 =head1 EXAMPLES
3762
3763   use Math::BigInt;
3764
3765   sub bint { Math::BigInt->new(shift); }
3766
3767   $x = Math::BigInt->bstr("1234")       # string "1234"
3768   $x = "$x";                            # same as bstr()
3769   $x = Math::BigInt->bneg("1234");      # Bigint "-1234"
3770   $x = Math::BigInt->babs("-12345");    # Bigint "12345"
3771   $x = Math::BigInt->bnorm("-0 00");    # BigInt "0"
3772   $x = bint(1) + bint(2);               # BigInt "3"
3773   $x = bint(1) + "2";                   # ditto (auto-BigIntify of "2")
3774   $x = bint(1);                         # BigInt "1"
3775   $x = $x + 5 / 2;                      # BigInt "3"
3776   $x = $x ** 3;                         # BigInt "27"
3777   $x *= 2;                              # BigInt "54"
3778   $x = Math::BigInt->new(0);            # BigInt "0"
3779   $x--;                                 # BigInt "-1"
3780   $x = Math::BigInt->badd(4,5)          # BigInt "9"
3781   print $x->bsstr();                    # 9e+0
3782
3783 Examples for rounding:
3784
3785   use Math::BigFloat;
3786   use Test;
3787
3788   $x = Math::BigFloat->new(123.4567);
3789   $y = Math::BigFloat->new(123.456789);
3790   Math::BigFloat->accuracy(4);          # no more A than 4
3791
3792   ok ($x->copy()->fround(),123.4);      # even rounding
3793   print $x->copy()->fround(),"\n";      # 123.4
3794   Math::BigFloat->round_mode('odd');    # round to odd
3795   print $x->copy()->fround(),"\n";      # 123.5
3796   Math::BigFloat->accuracy(5);          # no more A than 5
3797   Math::BigFloat->round_mode('odd');    # round to odd
3798   print $x->copy()->fround(),"\n";      # 123.46
3799   $y = $x->copy()->fround(4),"\n";      # A = 4: 123.4
3800   print "$y, ",$y->accuracy(),"\n";     # 123.4, 4
3801
3802   Math::BigFloat->accuracy(undef);      # A not important now
3803   Math::BigFloat->precision(2);         # P important
3804   print $x->copy()->bnorm(),"\n";       # 123.46
3805   print $x->copy()->fround(),"\n";      # 123.46
3806
3807 Examples for converting:
3808
3809   my $x = Math::BigInt->new('0b1'.'01' x 123);
3810   print "bin: ",$x->as_bin()," hex:",$x->as_hex()," dec: ",$x,"\n";
3811
3812 =head1 Autocreating constants
3813
3814 After C<use Math::BigInt ':constant'> all the B<integer> decimal, hexadecimal
3815 and binary constants in the given scope are converted to C<Math::BigInt>.
3816 This conversion happens at compile time.
3817
3818 In particular,
3819
3820   perl -MMath::BigInt=:constant -e 'print 2**100,"\n"'
3821
3822 prints the integer value of C<2**100>. Note that without conversion of
3823 constants the expression 2**100 will be calculated as perl scalar.
3824
3825 Please note that strings and floating point constants are not affected,
3826 so that
3827
3828         use Math::BigInt qw/:constant/;
3829
3830         $x = 1234567890123456789012345678901234567890
3831                 + 123456789123456789;
3832         $y = '1234567890123456789012345678901234567890'
3833                 + '123456789123456789';
3834
3835 do not work. You need an explicit Math::BigInt->new() around one of the
3836 operands. You should also quote large constants to protect loss of precision:
3837
3838         use Math::Bigint;
3839
3840         $x = Math::BigInt->new('1234567889123456789123456789123456789');
3841
3842 Without the quotes Perl would convert the large number to a floating point
3843 constant at compile time and then hand the result to BigInt, which results in
3844 an truncated result or a NaN.
3845
3846 This also applies to integers that look like floating point constants:
3847
3848         use Math::BigInt ':constant';
3849
3850         print ref(123e2),"\n";
3851         print ref(123.2e2),"\n";
3852
3853 will print nothing but newlines. Use either L<bignum> or L<Math::BigFloat>
3854 to get this to work.
3855
3856 =head1 PERFORMANCE
3857
3858 Using the form $x += $y; etc over $x = $x + $y is faster, since a copy of $x
3859 must be made in the second case. For long numbers, the copy can eat up to 20%
3860 of the work (in the case of addition/subtraction, less for
3861 multiplication/division). If $y is very small compared to $x, the form
3862 $x += $y is MUCH faster than $x = $x + $y since making the copy of $x takes
3863 more time then the actual addition.
3864
3865 With a technique called copy-on-write, the cost of copying with overload could
3866 be minimized or even completely avoided. A test implementation of COW did show
3867 performance gains for overloaded math, but introduced a performance loss due
3868 to a constant overhead for all other operatons.
3869
3870 The rewritten version of this module is slower on certain operations, like
3871 new(), bstr() and numify(). The reason are that it does now more work and
3872 handles more cases. The time spent in these operations is usually gained in
3873 the other operations so that programs on the average should get faster. If
3874 they don't, please contect the author.
3875
3876 Some operations may be slower for small numbers, but are significantly faster
3877 for big numbers. Other operations are now constant (O(1), like bneg(), babs()
3878 etc), instead of O(N) and thus nearly always take much less time. These
3879 optimizations were done on purpose.
3880
3881 If you find the Calc module to slow, try to install any of the replacement
3882 modules and see if they help you.
3883
3884 =head2 Alternative math libraries
3885
3886 You can use an alternative library to drive Math::BigInt via:
3887
3888         use Math::BigInt lib => 'Module';
3889
3890 See L<MATH LIBRARY> for more information.
3891
3892 For more benchmark results see L<http://bloodgate.com/perl/benchmarks.html>.
3893
3894 =head2 SUBCLASSING
3895
3896 =head1 Subclassing Math::BigInt
3897
3898 The basic design of Math::BigInt allows simple subclasses with very little
3899 work, as long as a few simple rules are followed:
3900
3901 =over 2
3902
3903 =item *
3904
3905 The public API must remain consistent, i.e. if a sub-class is overloading
3906 addition, the sub-class must use the same name, in this case badd(). The
3907 reason for this is that Math::BigInt is optimized to call the object methods
3908 directly.
3909
3910 =item *
3911
3912 The private object hash keys like C<$x->{sign}> may not be changed, but
3913 additional keys can be added, like C<$x->{_custom}>.
3914
3915 =item *
3916
3917 Accessor functions are available for all existing object hash keys and should
3918 be used instead of directly accessing the internal hash keys. The reason for
3919 this is that Math::BigInt itself has a pluggable interface which permits it
3920 to support different storage methods.
3921
3922 =back
3923
3924 More complex sub-classes may have to replicate more of the logic internal of
3925 Math::BigInt if they need to change more basic behaviors. A subclass that
3926 needs to merely change the output only needs to overload C<bstr()>.
3927
3928 All other object methods and overloaded functions can be directly inherited
3929 from the parent class.
3930
3931 At the very minimum, any subclass will need to provide it's own C<new()> and can
3932 store additional hash keys in the object. There are also some package globals
3933 that must be defined, e.g.:
3934
3935   # Globals
3936   $accuracy = undef;
3937   $precision = -2;       # round to 2 decimal places
3938   $round_mode = 'even';
3939   $div_scale = 40;
3940
3941 Additionally, you might want to provide the following two globals to allow
3942 auto-upgrading and auto-downgrading to work correctly:
3943
3944   $upgrade = undef;
3945   $downgrade = undef;
3946
3947 This allows Math::BigInt to correctly retrieve package globals from the
3948 subclass, like C<$SubClass::precision>.  See t/Math/BigInt/Subclass.pm or
3949 t/Math/BigFloat/SubClass.pm completely functional subclass examples.
3950
3951 Don't forget to
3952
3953         use overload;
3954
3955 in your subclass to automatically inherit the overloading from the parent. If
3956 you like, you can change part of the overloading, look at Math::String for an
3957 example.
3958
3959 =head1 UPGRADING
3960
3961 When used like this:
3962
3963         use Math::BigInt upgrade => 'Foo::Bar';
3964
3965 certain operations will 'upgrade' their calculation and thus the result to
3966 the class Foo::Bar. Usually this is used in conjunction with Math::BigFloat:
3967
3968         use Math::BigInt upgrade => 'Math::BigFloat';
3969
3970 As a shortcut, you can use the module C<bignum>:
3971
3972         use bignum;
3973
3974 Also good for oneliners:
3975
3976         perl -Mbignum -le 'print 2 ** 255'
3977
3978 This makes it possible to mix arguments of different classes (as in 2.5 + 2)
3979 as well es preserve accuracy (as in sqrt(3)).
3980
3981 Beware: This feature is not fully implemented yet.
3982
3983 =head2 Auto-upgrade
3984
3985 The following methods upgrade themselves unconditionally; that is if upgrade
3986 is in effect, they will always hand up their work:
3987
3988 =over 2
3989
3990 =item bsqrt()
3991
3992 =item div()
3993
3994 =item blog()
3995
3996 =back
3997
3998 Beware: This list is not complete.
3999
4000 All other methods upgrade themselves only when one (or all) of their
4001 arguments are of the class mentioned in $upgrade (This might change in later
4002 versions to a more sophisticated scheme):
4003
4004 =head1 BUGS
4005
4006 =over 2
4007
4008 =item Out of Memory!
4009
4010 Under Perl prior to 5.6.0 having an C<use Math::BigInt ':constant';> and
4011 C<eval()> in your code will crash with "Out of memory". This is probably an
4012 overload/exporter bug. You can workaround by not having C<eval()>
4013 and ':constant' at the same time or upgrade your Perl to a newer version.
4014
4015 =item Fails to load Calc on Perl prior 5.6.0
4016
4017 Since eval(' use ...') can not be used in conjunction with ':constant', BigInt
4018 will fall back to eval { require ... } when loading the math lib on Perls
4019 prior to 5.6.0. This simple replaces '::' with '/' and thus might fail on
4020 filesystems using a different seperator.
4021
4022 =back
4023
4024 =head1 CAVEATS
4025
4026 Some things might not work as you expect them. Below is documented what is
4027 known to be troublesome:
4028
4029 =over 1
4030
4031 =item stringify, bstr(), bsstr() and 'cmp'
4032
4033 Both stringify and bstr() now drop the leading '+'. The old code would return
4034 '+3', the new returns '3'. This is to be consistent with Perl and to make
4035 cmp (especially with overloading) to work as you expect. It also solves
4036 problems with Test.pm, it's ok() uses 'eq' internally.
4037
4038 Mark said, when asked about to drop the '+' altogether, or make only cmp work:
4039
4040         I agree (with the first alternative), don't add the '+' on positive
4041         numbers.  It's not as important anymore with the new internal
4042         form for numbers.  It made doing things like abs and neg easier,
4043         but those have to be done differently now anyway.
4044
4045 So, the following examples will now work all as expected:
4046
4047         use Test;
4048         BEGIN { plan tests => 1 }
4049         use Math::BigInt;
4050
4051         my $x = new Math::BigInt 3*3;
4052         my $y = new Math::BigInt 3*3;
4053
4054         ok ($x,3*3);
4055         print "$x eq 9" if $x eq $y;
4056         print "$x eq 9" if $x eq '9';
4057         print "$x eq 9" if $x eq 3*3;
4058
4059 Additionally, the following still works:
4060
4061         print "$x == 9" if $x == $y;
4062         print "$x == 9" if $x == 9;
4063         print "$x == 9" if $x == 3*3;
4064
4065 There is now a C<bsstr()> method to get the string in scientific notation aka
4066 C<1e+2> instead of C<100>. Be advised that overloaded 'eq' always uses bstr()
4067 for comparisation, but Perl will represent some numbers as 100 and others
4068 as 1e+308. If in doubt, convert both arguments to Math::BigInt before doing eq:
4069
4070         use Test;
4071         BEGIN { plan tests => 3 }
4072         use Math::BigInt;
4073
4074         $x = Math::BigInt->new('1e56'); $y = 1e56;
4075         ok ($x,$y);                     # will fail
4076         ok ($x->bsstr(),$y);            # okay
4077         $y = Math::BigInt->new($y);
4078         ok ($x,$y);                     # okay
4079
4080 Alternatively, simple use <=> for comparisations, that will get it always
4081 right. There is not yet a way to get a number automatically represented as
4082 a string that matches exactly the way Perl represents it.
4083
4084 =item int()
4085
4086 C<int()> will return (at least for Perl v5.7.1 and up) another BigInt, not a
4087 Perl scalar:
4088
4089         $x = Math::BigInt->new(123);
4090         $y = int($x);                           # BigInt 123
4091         $x = Math::BigFloat->new(123.45);
4092         $y = int($x);                           # BigInt 123
4093
4094 In all Perl versions you can use C<as_number()> for the same effect:
4095
4096         $x = Math::BigFloat->new(123.45);
4097         $y = $x->as_number();                   # BigInt 123
4098
4099 This also works for other subclasses, like Math::String.
4100
4101 It is yet unlcear whether overloaded int() should return a scalar or a BigInt.
4102
4103 =item length
4104
4105 The following will probably not do what you expect:
4106
4107         $c = Math::BigInt->new(123);
4108         print $c->length(),"\n";                # prints 30
4109
4110 It prints both the number of digits in the number and in the fraction part
4111 since print calls C<length()> in list context. Use something like:
4112
4113         print scalar $c->length(),"\n";         # prints 3
4114
4115 =item bdiv
4116
4117 The following will probably not do what you expect:
4118
4119         print $c->bdiv(10000),"\n";
4120
4121 It prints both quotient and remainder since print calls C<bdiv()> in list
4122 context. Also, C<bdiv()> will modify $c, so be carefull. You probably want
4123 to use
4124
4125         print $c / 10000,"\n";
4126         print scalar $c->bdiv(10000),"\n";  # or if you want to modify $c
4127
4128 instead.
4129
4130 The quotient is always the greatest integer less than or equal to the
4131 real-valued quotient of the two operands, and the remainder (when it is
4132 nonzero) always has the same sign as the second operand; so, for
4133 example,
4134
4135           1 / 4  => ( 0, 1)
4136           1 / -4 => (-1,-3)
4137          -3 / 4  => (-1, 1)
4138          -3 / -4 => ( 0,-3)
4139         -11 / 2  => (-5,1)
4140          11 /-2  => (-5,-1)
4141
4142 As a consequence, the behavior of the operator % agrees with the
4143 behavior of Perl's built-in % operator (as documented in the perlop
4144 manpage), and the equation
4145
4146         $x == ($x / $y) * $y + ($x % $y)
4147
4148 holds true for any $x and $y, which justifies calling the two return
4149 values of bdiv() the quotient and remainder. The only exception to this rule
4150 are when $y == 0 and $x is negative, then the remainder will also be
4151 negative. See below under "infinity handling" for the reasoning behing this.
4152
4153 Perl's 'use integer;' changes the behaviour of % and / for scalars, but will
4154 not change BigInt's way to do things. This is because under 'use integer' Perl
4155 will do what the underlying C thinks is right and this is different for each
4156 system. If you need BigInt's behaving exactly like Perl's 'use integer', bug
4157 the author to implement it ;)
4158
4159 =item infinity handling
4160
4161 Here are some examples that explain the reasons why certain results occur while
4162 handling infinity:
4163
4164 The following table shows the result of the division and the remainder, so that
4165 the equation above holds true. Some "ordinary" cases are strewn in to show more
4166 clearly the reasoning:
4167
4168         A /  B  =   C,     R so that C *    B +    R =    A
4169      =========================================================
4170         5 /   8 =   0,     5         0 *    8 +    5 =    5
4171         0 /   8 =   0,     0         0 *    8 +    0 =    0
4172         0 / inf =   0,     0         0 *  inf +    0 =    0
4173         0 /-inf =   0,     0         0 * -inf +    0 =    0
4174         5 / inf =   0,     5         0 *  inf +    5 =    5
4175         5 /-inf =   0,     5         0 * -inf +    5 =    5
4176         -5/ inf =   0,    -5         0 *  inf +   -5 =   -5
4177         -5/-inf =   0,    -5         0 * -inf +   -5 =   -5
4178        inf/   5 =  inf,    0       inf *    5 +    0 =  inf
4179       -inf/   5 = -inf,    0      -inf *    5 +    0 = -inf
4180        inf/  -5 = -inf,    0      -inf *   -5 +    0 =  inf
4181       -inf/  -5 =  inf,    0       inf *   -5 +    0 = -inf
4182          5/   5 =    1,    0         1 *    5 +    0 =    5
4183         -5/  -5 =    1,    0         1 *   -5 +    0 =   -5
4184        inf/ inf =    1,    0         1 *  inf +    0 =  inf
4185       -inf/-inf =    1,    0         1 * -inf +    0 = -inf
4186        inf/-inf =   -1,    0        -1 * -inf +    0 =  inf
4187       -inf/ inf =   -1,    0         1 * -inf +    0 = -inf
4188          8/   0 =  inf,    8       inf *    0 +    8 =    8
4189        inf/   0 =  inf,  inf       inf *    0 +  inf =  inf
4190          0/   0 =  NaN
4191
4192 These cases below violate the "remainder has the sign of the second of the two
4193 arguments", since they wouldn't match up otherwise.
4194
4195         A /  B  =   C,     R so that C *    B +    R =    A
4196      ========================================================
4197       -inf/   0 = -inf, -inf      -inf *    0 +  inf = -inf
4198         -8/   0 = -inf,   -8      -inf *    0 +    8 = -8
4199
4200 =item Modifying and =
4201
4202 Beware of:
4203
4204         $x = Math::BigFloat->new(5);
4205         $y = $x;
4206
4207 It will not do what you think, e.g. making a copy of $x. Instead it just makes
4208 a second reference to the B<same> object and stores it in $y. Thus anything
4209 that modifies $x (except overloaded operators) will modify $y, and vice versa.
4210 Or in other words, C<=> is only safe if you modify your BigInts only via
4211 overloaded math. As soon as you use a method call it breaks:
4212
4213         $x->bmul(2);
4214         print "$x, $y\n";       # prints '10, 10'
4215
4216 If you want a true copy of $x, use:
4217
4218         $y = $x->copy();
4219
4220 You can also chain the calls like this, this will make first a copy and then
4221 multiply it by 2:
4222
4223         $y = $x->copy()->bmul(2);
4224
4225 See also the documentation for overload.pm regarding C<=>.
4226
4227 =item bpow
4228
4229 C<bpow()> (and the rounding functions) now modifies the first argument and
4230 returns it, unlike the old code which left it alone and only returned the
4231 result. This is to be consistent with C<badd()> etc. The first three will
4232 modify $x, the last one won't:
4233
4234         print bpow($x,$i),"\n";         # modify $x
4235         print $x->bpow($i),"\n";        # ditto
4236         print $x **= $i,"\n";           # the same
4237         print $x ** $i,"\n";            # leave $x alone
4238
4239 The form C<$x **= $y> is faster than C<$x = $x ** $y;>, though.
4240
4241 =item Overloading -$x
4242
4243 The following:
4244
4245         $x = -$x;
4246
4247 is slower than
4248
4249         $x->bneg();
4250
4251 since overload calls C<sub($x,0,1);> instead of C<neg($x)>. The first variant
4252 needs to preserve $x since it does not know that it later will get overwritten.
4253 This makes a copy of $x and takes O(N), but $x->bneg() is O(1).
4254
4255 With Copy-On-Write, this issue would be gone, but C-o-W is not implemented
4256 since it is slower for all other things.
4257
4258 =item Mixing different object types
4259
4260 In Perl you will get a floating point value if you do one of the following:
4261
4262         $float = 5.0 + 2;
4263         $float = 2 + 5.0;
4264         $float = 5 / 2;
4265
4266 With overloaded math, only the first two variants will result in a BigFloat:
4267
4268         use Math::BigInt;
4269         use Math::BigFloat;
4270
4271         $mbf = Math::BigFloat->new(5);
4272         $mbi2 = Math::BigInteger->new(5);
4273         $mbi = Math::BigInteger->new(2);
4274
4275                                         # what actually gets called:
4276         $float = $mbf + $mbi;           # $mbf->badd()
4277         $float = $mbf / $mbi;           # $mbf->bdiv()
4278         $integer = $mbi + $mbf;         # $mbi->badd()
4279         $integer = $mbi2 / $mbi;        # $mbi2->bdiv()
4280         $integer = $mbi2 / $mbf;        # $mbi2->bdiv()
4281
4282 This is because math with overloaded operators follows the first (dominating)
4283 operand, and the operation of that is called and returns thus the result. So,
4284 Math::BigInt::bdiv() will always return a Math::BigInt, regardless whether
4285 the result should be a Math::BigFloat or the second operant is one.
4286
4287 To get a Math::BigFloat you either need to call the operation manually,
4288 make sure the operands are already of the proper type or casted to that type
4289 via Math::BigFloat->new():
4290
4291         $float = Math::BigFloat->new($mbi2) / $mbi;     # = 2.5
4292
4293 Beware of simple "casting" the entire expression, this would only convert
4294 the already computed result:
4295
4296         $float = Math::BigFloat->new($mbi2 / $mbi);     # = 2.0 thus wrong!
4297
4298 Beware also of the order of more complicated expressions like:
4299
4300         $integer = ($mbi2 + $mbi) / $mbf;               # int / float => int
4301         $integer = $mbi2 / Math::BigFloat->new($mbi);   # ditto
4302
4303 If in doubt, break the expression into simpler terms, or cast all operands
4304 to the desired resulting type.
4305
4306 Scalar values are a bit different, since:
4307
4308         $float = 2 + $mbf;
4309         $float = $mbf + 2;
4310
4311 will both result in the proper type due to the way the overloaded math works.
4312
4313 This section also applies to other overloaded math packages, like Math::String.
4314
4315 One solution to you problem might be L<autoupgrading|upgrading>.
4316
4317 =item bsqrt()
4318
4319 C<bsqrt()> works only good if the result is a big integer, e.g. the square
4320 root of 144 is 12, but from 12 the square root is 3, regardless of rounding
4321 mode.
4322
4323 If you want a better approximation of the square root, then use:
4324
4325         $x = Math::BigFloat->new(12);
4326         Math::BigFloat->precision(0);
4327         Math::BigFloat->round_mode('even');
4328         print $x->copy->bsqrt(),"\n";           # 4
4329
4330         Math::BigFloat->precision(2);
4331         print $x->bsqrt(),"\n";                 # 3.46
4332         print $x->bsqrt(3),"\n";                # 3.464
4333
4334 =item brsft()
4335
4336 For negative numbers in base see also L<brsft|brsft>.
4337
4338 =back
4339
4340 =head1 LICENSE
4341
4342 This program is free software; you may redistribute it and/or modify it under
4343 the same terms as Perl itself.
4344
4345 =head1 SEE ALSO
4346
4347 L<Math::BigFloat> and L<Math::Big> as well as L<Math::BigInt::BitVect>,
4348 L<Math::BigInt::Pari> and  L<Math::BigInt::GMP>.
4349
4350 The package at
4351 L<http://search.cpan.org/search?mode=module&query=Math%3A%3ABigInt> contains
4352 more documentation including a full version history, testcases, empty
4353 subclass files and benchmarks.
4354
4355 =head1 AUTHORS
4356
4357 Original code by Mark Biggar, overloaded interface by Ilya Zakharevich.
4358 Completely rewritten by Tels http://bloodgate.com in late 2000, 2001.
4359
4360 =cut