0


There are two arrays in java :

int[] a = new int[]{1,2,3,4};
int[] b = new int[]{4,0,5};

Is there any good algorithm for for multiplying each digit number in array?
I mean if I multiply a with b, then result should be like: 

int[] result => {4,9,9,7,7,0}

(because 1234*405 = 499770)
I can only think about elementary school version of multiplying.. but it not only requires me a lot of time and not a effective way in programming.
I want to know a way that calculate array itself, not change it to 'int' variable because I have to treat very very big number over than size of int.
Thanks for you advices in advance :)

  • No use "BigInteger"
Déjà vu
  • 28,223
  • 6
  • 72
  • 100
user3595632
  • 5,380
  • 10
  • 55
  • 111
  • Your array is initialized wrong doing '1' is actual the ascii value of the character 1 which is actually the number 49 and so forth. – Gary Kaizer Mar 20 '15 at 00:35
  • What about converting it to BigInteger and back? – kraskevich Mar 20 '15 at 00:39
  • 5
    No use "BigInteger"......Why not? – Amir Afghani Mar 20 '15 at 00:48
  • You could use Karatsuba multiplication to do this. It's not exactly linear, but it's a bit faster than the grade school algorithm. – Asad Saeeduddin Mar 20 '15 at 00:52
  • 1
    Roughly how many digits do you have in your inputs? This will dictate what the best multiplication algorithm is. – Asad Saeeduddin Mar 20 '15 at 01:02
  • Yes, there is. Do you remember how to multiply by hand? If yes: write that down as Java code. – user253751 Mar 20 '15 at 01:08
  • 1
    The elementary school version seems to be the way to go. Just don't convert the array to an integer in the meantime. – Teepeemm Mar 20 '15 at 01:11
  • @Teepeemm OP has already said they're not happy with the performance of grade school multiplication. Presumably they have a lot of digits and n^2 isn't good enough. – Asad Saeeduddin Mar 20 '15 at 03:34
  • @Asad The rest of OP's question gave me the impression that he was doing something like converting each array to an integer (possibly via `String`) and then multiplying before converting back to an integer array. – Teepeemm Mar 21 '15 at 00:13

0 Answers0