subtraction considered fail

[ghost]

I write this code:

#include"bigint.h"
#include<iostream>
using namespace std;
using namespace Dodecahedron;
int main(){
    Bigint a,b;
    cin>>a>>b;
    a-=b;
    cout<<a<<'\n'<<-1%10;
    return 0;
}

I get this output after #9 #ab6c858

IN:
5 6
OUT:
-999999999
-1

Before #9 at #1b840c7, everything is right

IN:
5 6
OUT:
-1
-1

So may "subtraction fix" make subtraction fail?

[kasparsklavins]

I'll look into it

[ghost]

I write this code

#include"bigint.h"
#include<iostream>
using namespace std;
using namespace Dodecahedron;
int main(){
    Bigint a,b;
    cin>>a>>b;
    cout<<a+b<<' '<<a-b;
    return 0;
}

And this test script ( I believe python's bigint ) in Python3

import subprocess
class Runner:
    def __init__(self, args):
        self.__process = subprocess.Popen(args, universal_newlines=True, stdin=subprocess.PIPE, stdout=subprocess.PIPE, stderr=subprocess.STDOUT)

    def run(self, input):
        self.__output=self.__process.communicate(input)[0]

    def get_output(self):
        return self.__output

from random import randint
infs = ['1']
for i in range(10000):
    infs.append('0')
lo = eval('-'+''.join(infs))
hi = eval(''.join(infs))
while True:
    a = randint(lo,hi)
    b = randint(lo,hi)
    apb = a+b
    asb = a-b
    inp = str(a)+' '+str(b)
    print(inp)
    run = Runner("./a")
    run.run(inp)
    opt = run.get_output()
    sta = str(apb) + ' ' + str(asb)
    print(opt)
    print(sta)
    if opt!=sta:
        break

Then I found subtraction almost wrong both before #9 and after #9, that means, subtraction is wrong before long, and never ever works.

I tried to fix it. Now it runs perfectly and pass the test script. My fix is at #07ed28b. Here is the core patch for #1b840c7

diff --git a/src/bigint.cpp b/src/bigint.cpp
index 2d47625..8fcc1af 100644
--- a/src/bigint.cpp
+++ b/src/bigint.cpp
@@ -174,20 +174,31 @@ Bigint &Bigint::operator-=(Bigint const &b)
         if (it1 != number.end()) {
             dif += *it1;
             ++it1;
+        } else {
+            number.push_back(0);
+            it1 = number.end();
         }
         if (it2 != b.number.end()) {
             dif -= *it2;
             ++it2;
         }
         if (dif < 0) {
-            *(it1 - 1) = (dif * (-1)) % base;
+            *(it1 - 1) = (dif + base) % base;
             dif = -1;
         } else {
             *(it1 - 1) = dif % base;
             dif /= base;
         }
     }
-    if (dif < 0) positive = false;
+    if (dif < 0) {
+        std::string newstr("1");
+        int c_seg = number.size();
+        while(c_seg--)
+            for(int i=1; i<base; i*=10)
+                newstr += "0";
+        *this = Bigint(newstr) - *this;
+        positive = false;
+    }

     return *this;
 }

I worked for long, when right result comes I just feel fly :)

There are 3 main points:

1. tell the positive before operation
2. push zero back when a is not large enough
3. temply use complement number when result is negative, turn back before finish operation

[ghost]

Please have a look at my testsuit at branch:test and test on travis ci. As you will see addition & subtraction now run well but multiplication is broken (maybe my changes broke it, I haven't considered leading zero)

[ghost]

I had a look at #9 and now I have known what is "leading-zero bug" means, that can be fix for #07ed28b like this

diff --git a/src/bigint.cpp b/src/bigint.cpp
index 8fcc1af..74b0c9a 100644
--- a/src/bigint.cpp
+++ b/src/bigint.cpp
@@ -199,6 +199,8 @@ Bigint &Bigint::operator-=(Bigint const &b)
         *this = Bigint(newstr) - *this;
         positive = false;
     }
+    while (!number.back())
+        number.pop_back();

     return *this;
 }

[kasparsklavins]

Can you do a PR for this?

[ghost]

I will try

[ghost]

19