Odejmowanie - algorytm

0

Witam,
Czy ma ktoś jakiś algorytm (nawet rysunek), do odejmowanie ogromnie dużych liczb w języku C. Chodzi mi o odejmowanie liczb posiadających już ponad 100 cyfr. Algorytm na zasadzie odejmowanie charów. Podane mamy 2 tablice i zapisać wynik mamy do 3. Możliwe są przypadki, że liczby są ujemne/dodatnie. Ale tych przypadków nie trzeba. Chciałbym zerknąć tylko na najbardziej podstawowy algorytm, bo w Internecie nie mogę znaleźć.

Pozdrawiam.

1

To chyba nic prostszego niż szkolne odejmowanie pisemnie nie ma i myślę też, że nie ma potrzeby wymyślać czegoś bardziej skomplikowanego.

2
4853984
-457645

Zrób sobie takie działanie i pomyśl jak działa ten algorytm.

3

Zanim ktoś napisze, że jesteśmy niemili, dam podpowiedź.
Żeby zapisać działanie jak w szkole, robimy cztery tablice: dwie na parametry działania, jedna na wynik i jedna na przeniesienie wartości z jednego rzędu na drugi. Długość tablic to długość liczb.
Przykład dla liczb sześciocyfrowych:

int N = 6;
int p[N - 1], a[N], b[N], w[N];

indeks 0 1 2 3 4 5
p 0 1 1 0 0
a 1 2 3 4 5 6
b 0 0 5 5 5 5
w 1 1 7 9 0 1

Kroki działania
w[5] = (a[5] < b[5]) ? b[5] - a[5] : a[5] - b[5]
p[4] = (a[5] < b[5]) ? 1 : 0

//To można zapisać w pętli
w[4] = (a[4] < b[4]) ? b[4] - a[4] : a[4] - b[4]
p[3] = (a[4] < (b[4] - p[4])) ? 1 : 0

Dalej pinokio idzie sam. Algorytm nie jest trudny, wystarczy rozpisać kroki.
@TheKryszczynPL Napisz co już w tym temacie wymyśliłeś. Jeśli nic, to spróbuj z tym, co napisałem.

1

Można znaleźć, wystarczy poszukać.
https://www.geeksforgeeks.org/difference-of-two-large-numbers/

1

Imho można by zacząć od czegoś takiego:

#include <algorithm>
#include <iostream>
using namespace std;

int main() {
	string s1{"499"}, s2{"498"}, res{""};

    reverse(s1.begin(), s1.end());
    reverse(s2.begin(), s2.end());

    auto n2 = s2.begin();
    
    for(auto n1 : s1)
    {
       auto r = static_cast<int>(n1 - *n2);
       res += r ? to_string(r) : "";
       ++n2;
    }
    reverse(res.begin(), res.end());
    cout << res << endl;

	return 0;
}

edit: wklepanie tego na telefonie chwilę mi zajęło, ale algorytm kolegi powyżej to "kompletna" wersja tego mojego

3

W ogóle zacząłbym od tego, że algorytm bedzie uruchamial sie dopiero po przekroczeniu np max wartosci long inta, w innym wypadku korzystamy z wbudowanych dzialan i duzo problemow z glowy masz, typu co zrobic z 0 itd.

1 użytkowników online, w tym zalogowanych: 0, gości: 1