Un desafío divertido.:)
Supongo que quieres enteros de longitud arbitraria. Sugiero el siguiente enfoque:
Considere la naturaleza binaria del tipo de datos "int". Piensa en usar operaciones binarias simples para emular lo que hacen los circuitos en tu CPU cuando agregan cosas. En caso de que esté interesado más en profundidad, considere leer this wikipedia article on half-adders and full-adders. Harás algo similar a eso, pero puedes bajar de nivel tan bajo como ese, pero al ser flojo, pensé que podría renunciar y encontrar una solución aún más simple.
Pero antes de entrar en cualquier detalle algorítmico sobre cómo sumar, restar, multiplicar, busquemos alguna estructura de datos. Una manera simple, por supuesto, es almacenar cosas en un std :: vector.
template< class BaseType >
class BigInt
{
typedef typename BaseType BT;
protected: std::vector<BaseType> value_;
};
Es posible que desee considerar si desea hacer el vector de un tamaño fijo y si una asignación previa a la misma. La razón es que para diversas operaciones, tendrá que pasar por cada elemento del vector - O (n). Es posible que desee saber de primera mano qué tan compleja será una operación y una n fija lo hace.
Pero ahora a algunos algoritmos para operar en los números. Podrías hacerlo en un nivel lógico, pero usaremos esa potencia mágica de CPU para calcular los resultados. Pero lo que haremos cargo de la lógica-ilustración de Half- y FullAdders es la forma en que maneja carry. Como ejemplo, considere cómo implementaría el operador + =. Para cada número en BigInt <> :: value_, debe agregar esos y ver si el resultado produce alguna forma de acarreo. No lo haremos por bits, sino que confiaremos en la naturaleza de nuestro BaseType (ya sea largo o int o corto o lo que sea): se desborda.
Seguramente, si agrega dos números, el resultado debe ser mayor que el mayor de esos números, ¿verdad? Si no es así, entonces el resultado se desbordó.
template< class BaseType >
BigInt<BaseType>& BigInt<BaseType>::operator += (BigInt<BaseType> const& operand)
{
BT count, carry = 0;
for (count = 0; count < std::max(value_.size(), operand.value_.size(); count++)
{
BT op0 = count < value_.size() ? value_.at(count) : 0,
op1 = count < operand.value_.size() ? operand.value_.at(count) : 0;
BT digits_result = op0 + op1 + carry;
if (digits_result-carry < std::max(op0, op1)
{
BT carry_old = carry;
carry = digits_result;
digits_result = (op0 + op1 + carry) >> sizeof(BT)*8; // NOTE [1]
}
else carry = 0;
}
return *this;
}
// NOTE 1: I did not test this code. And I am not sure if this will work; if it does
// not, then you must restrict BaseType to be the second biggest type
// available, i.e. a 32-bit int when you have a 64-bit long. Then use
// a temporary or a cast to the mightier type and retrieve the upper bits.
// Or you do it bitwise. ;-)
La otra operación aritmética es análoga. Diablos, incluso podría usar stl-functors std :: plus y std :: minus, std :: times y std :: divide, ..., pero tenga en cuenta el carry. :) También puede implementar la multiplicación y la división usando los operadores más y menos, pero eso es muy lento, porque eso recalcula los resultados que ya calculó en llamadas anteriores a más y menos en cada iteración. Hay muchos buenos algoritmos para esta simple tarea, usewikipedia o la web.
Y, por supuesto, se deben implementar los operadores estándar, tales como operator<< (simplemente cambiar cada valor en VALUE_ a la izquierda de n bits, empezando por el value_.size()-1 ... ah y recordar el equipaje :), operator< - incluso se puede optimice un poco aquí, primero verifique el número aproximado de dígitos con size(). Y así. Luego haz que tu clase sea útil, por befriendig std :: ostream operator<<.
Espero que este enfoque sea útil.
si se trata de un ejercicio de programación, comience a codificar. ¡De lo contrario no puedes hacer ningún ejercicio! –
Primero, las cadenas de dígitos están bien, pero piense en términos de base 2^32 (4 mil millones de dígitos distintos impares). Tal vez incluso base 2^64 en estos días. En segundo lugar, siempre trabaje con "dígitos" enteros sin signo. Puede hacer el complemento de dos para enteros grandes firmados usted mismo, pero si intenta hacer su manejo de desbordamiento, etc. con enteros con signo, se encontrará con problemas de comportamiento no definidos por las normas. – Steve314
En cuanto a los algoritmos: para una biblioteca básica, los que aprendió en la escuela son correctos. – Steve314