// /*-------------------------------------------------------------------*\
// | Concrete Template : Natural_Arithmetic_Plus_1
// \*-------------------------------------------------------------------*/
#ifndef CT_NATURAL_ARITHMETIC_PLUS_1
#define CT_NATURAL_ARITHMETIC_PLUS_1 1
///------------------------------------------------------------------------
/// Global Context --------------------------------------------------------
///------------------------------------------------------------------------
#include "AT/Natural/Arithmetic.h"
#include "AT/General/Copy_To.h"
#include "AT/General/Is_Equal_To.h"
/*!
#include "AI/Natural/Kernel.h"
!*/
///------------------------------------------------------------------------
/// Interface -------------------------------------------------------------
///------------------------------------------------------------------------
concrete_template <
concrete_instance class Natural_Base
/*!
implements
abstract_instance Natural_Kernel
!*/
>
class Natural_Arithmetic_Plus_1 :
implements
abstract_instance Natural_Arithmetic <
Natural_Arithmetic_Plus_1 <Natural_Base>
>,
implements
abstract_instance General_Copy_To <
Natural_Base,
Natural_Arithmetic_Plus_1 <Natural_Base>
>,
implements
abstract_instance General_Is_Equal_To <
Natural_Base,
Natural_Arithmetic_Plus_1 <Natural_Base>
>,
extends
concrete_instance Natural_Base
{
private:
procedure_body Multiply_By_Integer (
alters Natural_Arithmetic_Plus_1& n,
preserves Integer k
)
/*!
ensures
n = #n * k
!*/
{
// Algorithm: n * k = (nh * RADIX + nl) * k
// = nh * k * RADIX + nl * k
// = nh * k * RADIX + ((nl * k) / RADIX) * RADIX +
// (nl * k) % RADIX
if (n.Discrete_Log () > 0)
{
object Integer n_low_digit;
object Natural_Arithmetic_Plus_1 temp;
n.Divide_By_Radix (n_low_digit);
Multiply_By_Integer (n, k);
n.Multiply_By_Radix (0);
n_low_digit *= k;
temp.Multiply_By_Radix (n_low_digit / n.Radix ());
temp.Multiply_By_Radix (n_low_digit mod n.Radix ());
n.Add (temp);
}
}
public:
procedure_body Convert_From_Integer (
preserves Integer i
)
{
if (i == 0)
{
self.Clear ();
}
else
{
object Integer i_low_digit;
i_low_digit = i mod self.Radix ();
self.Convert_From_Integer (i / self.Radix ());
self.Multiply_By_Radix (i_low_digit);
}
}
procedure_body Increment ()
{
object Integer low_digit;
self.Divide_By_Radix (low_digit);
if (low_digit < self.Radix () - 1)
{
low_digit++;
}
else
{
low_digit = 0;
self.Increment ();
}
self.Multiply_By_Radix (low_digit);
}
procedure_body Decrement ()
{
object Integer low_digit;
self.Divide_By_Radix (low_digit);
if (low_digit > 0)
{
low_digit--;
}
else
{
low_digit = self.Radix () - 1;
self.Decrement ();
}
self.Multiply_By_Radix (low_digit);
}
function_body Integer Compare (
preserves Natural_Arithmetic_Plus_1& n
)
{
object Integer log_self, log_n;
log_self = self.Discrete_Log ();
log_n = n.Discrete_Log ();
if (log_self < log_n)
{
return -1;
}
else if (log_self > log_n)
{
return 1;
}
else if (log_n == 0) // log_n = log_self = 0
{
return 0;
}
else // log_n = log_self > 0
{
object Integer self_low_digit, n_low_digit, result;
self.Divide_By_Radix (self_low_digit);
n.Divide_By_Radix (n_low_digit);
result = self.Compare (n);
if (result == 0)
{
if (self_low_digit < n_low_digit)
{
result = -1;
}
else if (self_low_digit > n_low_digit)
{
result = 1;
}
}
self.Multiply_By_Radix (self_low_digit);
n.Multiply_By_Radix (n_low_digit);
return result;
}
}
procedure_body Add (
preserves Natural_Arithmetic_Plus_1& n
)
{
object Integer self_low_digit, n_low_digit;
self.Divide_By_Radix (self_low_digit);
n.Divide_By_Radix (n_low_digit);
self_low_digit += n_low_digit;
if (self_low_digit >= self.Radix ())
{
self_low_digit -= self.Radix ();
self.Increment ();
}
if (n.Discrete_Log () > 0)
{
self.Add (n);
}
self.Multiply_By_Radix (self_low_digit);
n.Multiply_By_Radix (n_low_digit);
}
procedure_body Subtract (
preserves Natural_Arithmetic_Plus_1& n
)
{
object Integer self_low_digit, n_low_digit;
self.Divide_By_Radix (self_low_digit);
n.Divide_By_Radix (n_low_digit);
self_low_digit -= n_low_digit;
if (self_low_digit < 0)
{
self_low_digit += self.Radix ();
self.Decrement ();
}
if (n.Discrete_Log () > 0)
{
self.Subtract (n);
}
self.Multiply_By_Radix (self_low_digit);
n.Multiply_By_Radix (n_low_digit);
}
procedure_body Multiply (
preserves Natural_Arithmetic_Plus_1& n
)
{
// Algorithm: self * n = (sh * RADIX + sl) * n
// = sh * n * RADIX + sl * n
if (self.Discrete_Log () > 0)
{
object Integer self_low_digit;
object Natural_Arithmetic_Plus_1 temp;
self.Divide_By_Radix (self_low_digit);
self.Multiply (n);
self.Multiply_By_Radix (0);
n.Copy_To (temp);
Multiply_By_Integer (temp, self_low_digit);
self.Add (temp);
}
}
procedure_body Divide (
preserves Natural_Arithmetic_Plus_1& n,
produces Natural_Arithmetic_Plus_1& rem
)
{
// Easy special cases: self = 0, single-digit self and n; else by
// induction on number of digits in n
if (self.Discrete_Log () == 0)
{
rem.Clear ();
}
else if ((self.Discrete_Log () == 1) and (n.Discrete_Log () == 1))
{
object Integer self_low_digit, n_low_digit, rem_low_digit;
self.Divide_By_Radix (self_low_digit);
n.Divide_By_Radix (n_low_digit);
rem_low_digit = self_low_digit mod n_low_digit;
self_low_digit /= n_low_digit;
rem.Clear ();
rem.Multiply_By_Radix (rem_low_digit);
self.Multiply_By_Radix (self_low_digit);
n.Multiply_By_Radix (n_low_digit);
}
else
{
object Integer order;
order = self.Compare (n);
if (order < 0)
{
rem &= self;
self.Clear ();
}
else if (order == 0)
{
self.Clear ();
self.Increment ();
rem.Clear ();
}
else
{
object Integer self_low_digit;
object Natural_Arithmetic_Plus_1 temp;
self.Divide_By_Radix (self_low_digit);
if (self.Compare (n) < 0)
{
object Integer high_digit;
self.Multiply_By_Radix (self_low_digit);
// Find self_low_digit by binary search in [0..10)
self_low_digit = 0;
high_digit = 10;
while (true)
/*!
preserves self, n
alters self_low_digit, high_digit
maintains
self = #self and
n = #n and
self_low_digit * n <= self < high_digit * n
!*/
{
object Integer mid_digit;
object Natural_Arithmetic_Plus_1 test_value;
mid_digit = (self_low_digit + high_digit) / 2;
if (self_low_digit == mid_digit)
{
break;
}
test_value.Multiply_By_Radix (mid_digit);
test_value.Multiply (n);
if (self.Compare (test_value) < 0)
{
high_digit = mid_digit;
}
else
{
self_low_digit = mid_digit;
}
} // while (true)
self &= rem;
self.Clear ();
self.Multiply_By_Radix (self_low_digit);
self.Copy_To (temp);
temp.Multiply (n);
rem.Subtract (temp);
} // if (self.Compare (n) < 0)
else
{
self.Divide (n, temp);
temp.Multiply_By_Radix (self_low_digit);
temp.Divide (n, rem);
self.Multiply_By_Radix (0);
self.Add (temp);
}
}
}
}
procedure_body Copy_To (
produces Natural_Arithmetic_Plus_1& lhs
)
{
if (self.Discrete_Log () == 0)
{
lhs.Clear ();
}
else
{
object Integer self_low_digit;
self.Divide_By_Radix (self_low_digit);
self.Copy_To (lhs);
self.Multiply_By_Radix (self_low_digit);
lhs.Multiply_By_Radix (self_low_digit);
}
}
function_body Boolean Is_Equal_To (
preserves Natural_Arithmetic_Plus_1& x
)
{
return self.Compare (x) == 0;
}
};
#endif // CT_NATURAL_ARITHMETIC_PLUS_1
Last modified: Thu Jan 11 17:05:57 EST 2007
