自定义大数类划分的问题 (C++)

Question

我正在为大数字类（单个数字的无限长度）编写自定义算术，

当 A 远大于 B 时，使用多个递减数字 A 除以 B 会失败。 我正在尝试实施书面除法，但我发现它对我的情况来说太复杂了。

我无法将数字存储在字符串中（这是该项目的主要限制），因此我将它们以 4 位数字为一组存储在 int 列表中。 我试图将其视为整个 4 位数字结构是流行的书面除法中的单个数字，但我在实现过程中通过重载 / 运算符迷失了方向。

我想得到一个提示，如果我正在做除法的最后一个主要部分，是否正确？如果在这个类中划分，我该如何改进方法？

struct Node{
    int value;
    Node* next,*prev;
};

class number {

public:

Node* head;

number();   //konstruktor domyślny
~number();  //destruktor
void addNode(string str); //dodanie nowego wezla na poczatek liczby
void addNode(int str); //dodanie nowego wezla na poczatek liczby (z wartosci int)
number& operator+(number& licz); //operator dodawania
number& operator-(number& licz); //operator odejmowania
bool operator>(number& licz); //operator porównania (czy a > b)
bool operator<(number& licz); //operator porównania (a mniejsze od b)
bool operator==(number&  licz); //operator porównania (czy a równe b)
number& operator=(const number& licz); //operator przypisania
number& operator-(); //operator zamiany liczby na przeciwną
friend istream& operator>>(istream& input,number& li);  //operator pobierania liczby
friend ostream& operator<<(ostream& s,number& li); //operator wypisania
void validate(); //funkcja usuwajaca zera z poczatku liczby
number& operator/(number& licz);  //dzielenie calkowitoliczbowe
number& operator*(number& licz); //mnożenie
void pushNode(int str);

};

number& number::operator/(number& licz)
{
/////////cases of dividing//////

if (this->head->value<0 && licz.head->value<0) {
    return (-(*this))/(-licz);
}
if (this->head->value<0 && licz.head->value>0) {
    return -((-(*this))/licz);
}
if (this->head->value>0 && licz.head->value<0) {
    return -(*this/(-licz));
}

number tmp_this=*this;
number tmp_licz=licz;
number zero;
zero.addNode(0);

//dividing by zero//
if (licz==zero) {
    cout<<"dividing by zero"<<endl;  
    number* t=new number;
    t->addNode(0);
    return *t;
}

//dividing zero by sth ///
if (*this==zero) {
    number* t=new number;
    t->addNode(0);
    return *t;
}

number i,jeden;
i.addNode(0);
jeden.addNode(1);

if (licz == jeden) {
    return *this;
}

/// here real mess start///
string pl="";

number* tmp=new number;
Node* p=this->head,*q=licz.head;
tmp->pushNode(q->value);
while (p && *tmp  < licz) {
    p=p->next;
    tmp->pushNode(p->value);
}
number* wynik=new number;
wynik=tmp;
int j;
while (*wynik > zero || *wynik==zero) {
    *wynik=*wynik-tmp_licz;
    j++;
}
char* str;
sprintf(str, "%d", j);

///end od mess///
};

Answer 1

我想这里有一个问题，也没有问号。

您尝试同时解决两个复杂的任务（这可能会失败 - 或者已经失败）。拆分这两个任务：

• 安全地管理免费存储中的列表项（使用 std::list 或 std::vector；如果不这样做，仅用于练习目的）
• 进行多精度算术运算（尤其是除法很复杂，即使我们学会了它）在学校）

为了存储“4字节数字”， std::vector 似乎更好。当将它们存储在列表节点中时，每个数字使用 4 个字节，而不是 8 个或更多字节。当数字变大（a += b）时， std::vector 可以增长，并且如果需要的话可以缩小。

对于算术，您还可以将加号/减号分开并首先对非负数进行运算。

加法、减法和乘法相对简单。对于除法，我必须看 Donald Knuth 的《计算机编程艺术》第 2 卷（半数值算法），并花了两周的时间来解决它。也许我在这一点上还不是特别擅长。

请考虑到，当 2 字节数相乘时，您会得到 4 字节数。否则整数溢出会破坏你的结果。另一种方法是除法。

如果您想查看我在同一教育任务上的结果，请在谷歌上搜索我的姓氏和“Ganzzahl”。但要注意，它没有经过严格的测试，用德语编写，而且自从我几年前编写以来，我不再认为它是编写良好的代码...

如果您正在寻找生产代码解决方案，请尝试使用像 GNU 这样的库改为多精度整数。