implementing multiplication algorithm in java -
i have following multiplication algorithm, trying implement using java:
m: number of digits
n: b number of digits
β: base
this java function implments algorithm:
public biginteger prodbigbig(biginteger a, biginteger b, integer base ){ arraylist<integer> lista = new arraylist<integer>(); arraylist<integer> listb = new arraylist<integer>(); arraylist<integer> listc = new arraylist<integer>(); int m = a.tostring().length(); int n = b.tostring().length(); integer carry, temp; biginteger result = biginteger.zero; for(int = 0; < a.tostring().length(); i++){ lista.add(character.getnumericvalue( a.tostring().charat(i))); } for(int = 0; < b.tostring().length(); i++){ listb.add((character.getnumericvalue( b.tostring().charat(i)))); } for(int i= 0; <= m - 1; i++){ listc.add(0); } for(int k = 0; k <= n - 1 ; k++) { carry = 0; for(int = 0; <= m - 1; i++){ temp = (lista.get(i) * listb.get(k)) + listc.get(i + k) + carry; listc.add(i+k,temp % base); carry = temp / base; } listc.add(k + m,carry); } for(int = 0; < m + n; i++) { result = result.add(biginteger.valueof((long) (listc.get(i)*(math.pow(base, i))))); } return result; }
but don't know why not getting correct result, until not able detect fails.
listc.add(i+k,temp % base);
that should be
listc.set(i+k,temp % base);
and final transformation biginteger overflow sufficiently large numbers. rid of arraylists
altogether , use arrays of int
, , convert byte[]
@ end , feed directly constructor biginteger.
Comments
Post a Comment