my $mask = $AND_MASK;  my $x1 = $x;  my $y1 = _copy($c,$y);			# make copy  $x = _zero();  my ($b,$xrr,$yrr);  use integer;  while (!_is_zero($c,$x1) && !_is_zero($c,$y1))    {    ($x1, $xr) = _div($c,$x1,$mask);    ($y1, $yr) = _div($c,$y1,$mask);    # make ints() from $xr, $yr    # this is when the AND_BITS are greater tahn $BASE and is slower for    # small (<256 bits) numbers, but faster for large numbers. Disabled    # due to KISS principle#    $b = 1; $xrr = 0; foreach (@$xr) { $xrr += $_ * $b; $b *= $BASE; }#    $b = 1; $yrr = 0; foreach (@$yr) { $yrr += $_ * $b; $b *= $BASE; }#    _add($c,$x, _mul($c, _new( $c, \($xrr & $yrr) ), $m) );        # 0+ due to '&' doesn't work in strings    _add($c,$x, _mul($c, [ 0+$xr->[0] & 0+$yr->[0] ], $m) );    _mul($c,$m,$mask);    }  $x;  }sub _xor  {  my ($c,$x,$y) = @_;  return _zero() if _acmp($c,$x,$y) == 0;	# shortcut (see -and)  my $m = _one(); my ($xr,$yr);  my $mask = $XOR_MASK;  my $x1 = $x;  my $y1 = _copy($c,$y);			# make copy  $x = _zero();  my ($b,$xrr,$yrr);  use integer;  while (!_is_zero($c,$x1) && !_is_zero($c,$y1))    {    ($x1, $xr) = _div($c,$x1,$mask);    ($y1, $yr) = _div($c,$y1,$mask);    # make ints() from $xr, $yr (see _and())    #$b = 1; $xrr = 0; foreach (@$xr) { $xrr += $_ * $b; $b *= $BASE; }    #$b = 1; $yrr = 0; foreach (@$yr) { $yrr += $_ * $b; $b *= $BASE; }    #_add($c,$x, _mul($c, _new( $c, \($xrr ^ $yrr) ), $m) );    # 0+ due to '^' doesn't work in strings    _add($c,$x, _mul($c, [ 0+$xr->[0] ^ 0+$yr->[0] ], $m) );    _mul($c,$m,$mask);    }  # the loop stops when the shorter of the two numbers is exhausted  # the remainder of the longer one will survive bit-by-bit, so we simple  # multiply-add it in  _add($c,$x, _mul($c, $x1, $m) ) if !_is_zero($c,$x1);  _add($c,$x, _mul($c, $y1, $m) ) if !_is_zero($c,$y1);    $x;  }sub _or  {  my ($c,$x,$y) = @_;  return $x if _acmp($c,$x,$y) == 0;		# shortcut (see _and)  my $m = _one(); my ($xr,$yr);  my $mask = $OR_MASK;  my $x1 = $x;  my $y1 = _copy($c,$y);			# make copy  $x = _zero();  my ($b,$xrr,$yrr);  use integer;  while (!_is_zero($c,$x1) && !_is_zero($c,$y1))    {    ($x1, $xr) = _div($c,$x1,$mask);    ($y1, $yr) = _div($c,$y1,$mask);    # make ints() from $xr, $yr (see _and())#    $b = 1; $xrr = 0; foreach (@$xr) { $xrr += $_ * $b; $b *= $BASE; }#    $b = 1; $yrr = 0; foreach (@$yr) { $yrr += $_ * $b; $b *= $BASE; }#    _add($c,$x, _mul($c, _new( $c, \($xrr | $yrr) ), $m) );        # 0+ due to '|' doesn't work in strings    _add($c,$x, _mul($c, [ 0+$xr->[0] | 0+$yr->[0] ], $m) );    _mul($c,$m,$mask);    }  # the loop stops when the shorter of the two numbers is exhausted  # the remainder of the longer one will survive bit-by-bit, so we simple  # multiply-add it in  _add($c,$x, _mul($c, $x1, $m) ) if !_is_zero($c,$x1);  _add($c,$x, _mul($c, $y1, $m) ) if !_is_zero($c,$y1);    $x;  }sub _as_hex  {  # convert a decimal number to hex (ref to array, return ref to string)  my ($c,$x) = @_;  my $x1 = _copy($c,$x);  my $es = '';  my ($xr, $h, $x10000);  if ($] >= 5.006)    {    $x10000 = [ 0x10000 ]; $h = 'h4';    }  else    {    $x10000 = [ 0x1000 ]; $h = 'h3';    }  while (! _is_zero($c,$x1))    {    ($x1, $xr) = _div($c,$x1,$x10000);    $es .= unpack($h,pack('v',$xr->[0]));    }  $es = reverse $es;  $es =~ s/^[0]+//;   # strip leading zeros  $es = '0x' . $es;  \$es;  }sub _as_bin  {  # convert a decimal number to bin (ref to array, return ref to string)  my ($c,$x) = @_;  my $x1 = _copy($c,$x);  my $es = '';  my ($xr, $b, $x10000);  if ($] >= 5.006)    {    $x10000 = [ 0x10000 ]; $b = 'b16';    }  else    {    $x10000 = [ 0x1000 ]; $b = 'b12';    }  while (! _is_zero($c,$x1))    {    ($x1, $xr) = _div($c,$x1,$x10000);    $es .= unpack($b,pack('v',$xr->[0]));    }  $es = reverse $es;  $es =~ s/^[0]+//;   # strip leading zeros  $es = '0b' . $es;  \$es;  }sub _from_hex  {  # convert a hex number to decimal (ref to string, return ref to array)  my ($c,$hs) = @_;  my $mul = _one();  my $m = [ 0x10000 ];				# 16 bit at a time  my $x = _zero();  my $len = length($$hs)-2;  $len = int($len/4);				# 4-digit parts, w/o '0x'  my $val; my $i = -4;  while ($len >= 0)    {    $val = substr($$hs,$i,4);    $val =~ s/^[+-]?0x// if $len == 0;		# for last part only because    $val = hex($val);				# hex does not like wrong chars    $i -= 4; $len --;    _add ($c, $x, _mul ($c, [ $val ], $mul ) ) if $val != 0;    _mul ($c, $mul, $m ) if $len >= 0; 		# skip last mul    }  $x;  }sub _from_bin  {  # convert a hex number to decimal (ref to string, return ref to array)  my ($c,$bs) = @_;  # instead of converting 8 bit at a time, it is faster to convert the  # number to hex, and then call _from_hex.  my $hs = $$bs;  $hs =~ s/^[+-]?0b//;					# remove sign and 0b  my $l = length($hs);					# bits  $hs = '0' x (8-($l % 8)) . $hs if ($l % 8) != 0;	# padd left side w/ 0  my $h = unpack('H*', pack ('B*', $hs));		# repack as hex  return $c->_from_hex(\('0x'.$h));   my $mul = _one();  my $m = [ 0x100 ];				# 8 bit at a time  my $x = _zero();  my $len = length($$bs)-2;  $len = int($len/8);				# 4-digit parts, w/o '0x'  my $val; my $i = -8;  while ($len >= 0)    {    $val = substr($$bs,$i,8);    $val =~ s/^[+-]?0b// if $len == 0;		# for last part only    $val = ord(pack('B8',substr('00000000'.$val,-8,8)));     $i -= 8; $len --;    _add ($c, $x, _mul ($c, [ $val ], $mul ) ) if $val != 0;    _mul ($c, $mul, $m ) if $len >= 0; 		# skip last mul    }  $x;  }############################################################################### special modulus functionssub _modinv  {  # modular inverse  my ($c,$x,$y) = @_;  my $u = _zero($c); my $u1 = _one($c);  my $a = _copy($c,$y); my $b = _copy($c,$x);  # Euclid's Algorithm for bgcd(), only that we calc bgcd() ($a) and the  # result ($u) at the same time. See comments in BigInt for why this works.  my $q;  ($a, $q, $b) = ($b, _div($c,$a,$b));		# step 1  my $sign = 1;  while (!_is_zero($c,$b))    {    my $t = _add($c, 				# step 2:       _mul($c,_copy($c,$u1), $q) ,		#  t =  u1 * q       $u );					#     + u    $u = $u1;					#  u = u1, u1 = t    $u1 = $t;    $sign = -$sign;    ($a, $q, $b) = ($b, _div($c,$a,$b));	# step 1    }  # if the gcd is not 1, then return NaN  return (undef,undef) unless _is_one($c,$a);   $sign = $sign == 1 ? '+' : '-';  ($u1,$sign);  }sub _modpow  {  # modulus of power ($x ** $y) % $z  my ($c,$num,$exp,$mod) = @_;  # in the trivial case,  if (_is_one($c,$mod))    {    splice @$num,0,1; $num->[0] = 0;    return $num;    }  if ((scalar @$num == 1) && (($num->[0] == 0) || ($num->[0] == 1)))    {    $num->[0] = 1;    return $num;    }#  $num = _mod($c,$num,$mod);	# this does not make it faster  my $acc = _copy($c,$num); my $t = _one();  my $expbin = ${_as_bin($c,$exp)}; $expbin =~ s/^0b//;  my $len = length($expbin);  while (--$len >= 0)    {    if ( substr($expbin,$len,1) eq '1')			# is_odd      {      _mul($c,$t,$acc);      $t = _mod($c,$t,$mod);      }    _mul($c,$acc,$acc);    $acc = _mod($c,$acc,$mod);    }  @$num = @$t;  $num;  }############################################################################################################################################################1;__END__=head1 NAMEMath::BigInt::Calc - Pure Perl module to support Math::BigInt=head1 SYNOPSISProvides support for big integer calculations. Not intended to be used by othermodules (except Math::BigInt::Cached). Other modules which sport the samefunctions can also be used to support Math::Bigint, like Math::BigInt::Pari.=head1 DESCRIPTIONIn order to allow for multiple big integer libraries, Math::BigInt wasrewritten to use library modules for core math routines. Any module whichfollows the same API as this can be used instead by using the following:	use Math::BigInt lib => 'libname';'libname' is either the long name ('Math::BigInt::Pari'), or only the shortversion like 'Pari'.=head1 EXPORTThe following functions MUST be defined in order to support the use byMath::BigInt:	_new(string)	return ref to new object from ref to decimal string	_zero()		return a new object with value 0	_one()		return a new object with value 1	_str(obj)	return ref to a string representing the object	_num(obj)	returns a Perl integer/floating point number			NOTE: because of Perl numeric notation defaults,			the _num'ified obj may lose accuracy due to 			machine-dependend floating point size limitations                    	_add(obj,obj)	Simple addition of two objects	_mul(obj,obj)	Multiplication of two objects	_div(obj,obj)	Division of the 1st object by the 2nd			In list context, returns (result,remainder).			NOTE: this is integer math, so no			fractional part will be returned.	_sub(obj,obj)	Simple subtraction of 1 object from another			a third, optional parameter indicates that the params			are swapped. In this case, the first param needs to			be preserved, while you can destroy the second.			sub (x,y,1) => return x - y and keep x intact!	_dec(obj)	decrement object by one (input is garant. to be > 0)	_inc(obj)	increment object by one	_acmp(obj,obj)	<=> operator for objects (return -1, 0 or 1)	_len(obj)	returns count of the decimal digits of the object	_digit(obj,n)	returns the n'th decimal digit of object	_is_one(obj)	return true if argument is +1	_is_zero(obj)	return true if argument is 0	_is_even(obj)	return true if argument is even (0,2,4,6..)	_is_odd(obj)	return true if argument is odd (1,3,5,7..)	_copy		return a ref to a true copy of the object	_check(obj)	check whether internal representation is still intact			return 0 for ok, otherwise error message as stringThe following functions are optional, and can be defined if the underlying libhas a fast way to do them. If undefined, Math::BigInt will use pure Perl (henceslow) fallback routines to emulate these:	_from_hex(str)	return ref to new object from ref to hexadecimal string	_from_bin(str)	return ref to new object from ref to binary string		_as_hex(str)	return ref to scalar string containing the value as			unsigned hex string, with the '0x' prepended.			Leading zeros must be stripped.	_as_bin(str)	Like as_hex, only as binary string containing only			zeros and ones. Leading zeros must be stripped and a			'0b' must be prepended.		_rsft(obj,N,B)	shift object in base B by N 'digits' right			For unsupported bases B, return undef to signal failure	_lsft(obj,N,B)	shift object in base B by N 'digits' left			For unsupported bases B, return undef to signal failure		_xor(obj1,obj2)	XOR (bit-wise) object 1 with object 2			Note: XOR, AND and OR pad with zeros if size mismatches	_and(obj1,obj2)	AND (bit-wise) object 1 with object 2	_or(obj1,obj2)	OR (bit-wise) object 1 with object 2	_mod(obj,obj)	Return remainder of div of the 1st by the 2nd object	_sqrt(obj)	return the square root of object (truncate to int)	_fac(obj)	return factorial of object 1 (1*2*3*4..)	_pow(obj,obj)	return object 1 to the power of object 2	_gcd(obj,obj)	return Greatest Common Divisor of two objects		_zeros(obj)	return number of trailing decimal zeros	_modinv		return inverse modulus	_modpow		return modulus of power ($x ** $y) % $zInput strings come in as unsigned but with prefix (i.e. as '123', '0xabc'or '0b1101').Testing of input parameter validity is done by the caller, so you need notworry about underflow (f.i. in C<_sub()>, C<_dec()>) nor about division byzero or similar cases.The first parameter can be modified, that includes the possibility that youreturn a reference to a completely different object instead. Although keepingthe reference and just changing it's contents is prefered over creating andreturning a different reference.Return values are always references to objects or strings. Exceptions areC<_lsft()> and C<_rsft()>, which return undef if they can not shift theargument. This is used to delegate shifting of bases different than the oneyou can support back to Math::BigInt, which will use some generic code tocalculate the result.=head1 WRAP YOUR OWNIf you want to port your own favourite c-lib for big numbers to theMath::BigInt interface, you can take any of the already existing modules asa rough guideline. You should really wrap up the latest BigInt and BigFloattestsuites with your module, and replace in them any of the following:	use Math::BigInt;by this:	use Math::BigInt lib => 'yourlib';This way you ensure that your library really works 100% within Math::BigInt.=head1 LICENSE This program is free software; you may redistribute it and/or modify it underthe same terms as Perl itself. =head1 AUTHORSOriginal math code by Mark Biggar, rewritten by Tels L<http://bloodgate.com/>in late 2000, 2001.Seperated from BigInt and shaped API with the help of John Peacock.=head1 SEE ALSOL<Math::BigInt>, L<Math::BigFloat>, L<Math::BigInt::BitVect>,L<Math::BigInt::GMP>, L<Math::BigInt::Cached> and L<Math::BigInt::Pari>.=cut