algorithm - Karatsuba multiplication java recursion code not working? -


i trying multiply 2 numbers using karatsuba multiplication. java code not working. have used string parameters , arguments can multiply 2 n digit numbers (n even). also, don't want use long or biginteger. please me figure out code mistake.

class karat{  public static string karatsuba(string first, string second){      if(first.length() <= 1 || second.length() <= 1)         return string.valueof(long.parselong(first)*long.parselong(second));      string = karatsuba(first.substring(0, first.length()/2), second.substring(0, second.length()/2));      string b = karatsuba(first.substring(first.length() - first.length()/2, first.length()), second.substring(second.length() - second.length()/2, second.length()));      string c = karatsuba(string.valueof(long.parselong(first.substring(0, first.length()/2)) + long.parselong(first.substring(first.length() - first.length()/2, first.length()))), string.valueof(long.parselong(second.substring(0, second.length()/2)) + long.parselong(second.substring(second.length() - second.length()/2, second.length()))));      string d = string.valueof(long.parselong(c) - long.parselong(b) - long.parselong(a));      return string.valueof(((int)math.pow(10, first.length()))*(long.parselong(a)) + (((int)math.pow(10, first.length()/2))*long.parselong(d)) + (long.parselong(c))); }  public static void main(string[] args){         string result = karatsuba("1234", "5678");         system.out.println(result); } }

can please refine code.

numbers passed multiplication - 1234 , 5678

output - 6655870 (incorrect)

output should - 7006652 (correct)

thank

interesting algorithm. 1 mistake in 

return string.valueof(((int)math.pow(10, first.length()))*(long.parselong(a)) + (((int)math.pow(10, first.length()/2))*long.parselong(d)) + (long.parselong(c)));

at end, should long.parselong(b) instead of long.parselong(c).

and in intermediate calculations, can happen 2 strings of different lengths. doesn't work correctly.

please, allow comments improve implementation. idea use strings seems allow big numbers, introduce things long.parselong() or (int)math.pow(10, first.length()), limiting long or int range.

if want big numbers, write own string-based addition , power-of-ten multiplication (that 1 being trivial appending zeroes).

and, try avoid names a, b, c, or d - it's easy forget mean, original mistake. e.g. names wikipedia little bit better (using z0, z1 , z2), still not perfect...


Comments

Post a Comment

Popular posts from this blog

python - Operations inside variables -

this question has answer here: evaluating mathematical expression in string 12 answers i want make python script finds maximum possible output using 2 operations. problem says there syntax error @ 2nd last line, in b in there. how can fix it? x = 0 = int(input("1st number:")) c = int(input("2nd number:" )) e = int(input("3rd number:" )) in range(4): if == 0: b = "+" elif == 1: b = "-" elif == 2: b = "/" else: b = "*" j in range(4): if j == 0: d = "+" elif j == 1: d = "-" elif j == 2: d = "/" else: d = "*" k = b c d e print(k) if you're after variables e on single line, couldn...
Read more

Generic Map Parameter java -

i having lot of methods of type: public static list<eduusers> getdetails(class c, map<string, integer> params) { list<eduusers> details = null; session session = hibernateutil.getsessionfactory().opensession(); transaction tx = null; try { tx = session.begintransaction(); criteria cr = session.createcriteria(c); (map.entry<string, integer> entry : params.entryset()) { cr.add(restrictions.eq(entry.getkey(), entry.getvalue())); } details = cr.list(); tx.commit(); } catch (exception asd) { log.debug(asd.getmessage()); if (tx != null) { tx.commit(); } } { session.close(); } return details; } i trying have generic method them , have written far: public static <t> list<t> getdetails(class<t> c, class<t> b) { l...
Read more

arrays - What causes a java.lang.ArrayIndexOutOfBoundsException and how do I prevent it? -

what arrayindexoutofboundsexception mean , how rid of it? here code sample triggers exception: string[] name = {"tom", "dick", "harry"}; for(int = 0; i<=name.length; i++) { system.out.print(name[i] +'\n'); } your first port of call should documentation explains reasonably clearly: thrown indicate array has been accessed illegal index. index either negative or greater or equal size of array. so example: int[] array = new int[5]; int boom = array[10]; // throws exception as how avoid it... um, don't that. careful array indexes. one problem people run thinking arrays 1-indexed, e.g. int[] array = new int[5]; // ... populate array here ... (int index = 1; index <= array.length; index++) { system.out.println(array[index]); } that miss out first element (index 0) , throw exception when index 5. valid indexes here 0-4 inclusive. correct, idiomatic for statement here be: for (int index = 0; index <...
Read more