java - Arbitrary precision multiplication, Knuth 4.3.1 leading zero elimination -

i working basic knuth 4.3.1 algorithm m arbitrary precision multiplication on natural numbers. implementation in java below. problem is generating leading zeroes, seemingly side effect of algorithm not knowing whether given result has 2 places or one. example, 2 x 3 = 6 (one digit), 4 x 7 = 28 (two digits). algorithm seems reserve 2 digits results in leading zeroes.

my question two-fold: (1) algorithm correct implementation of m, or doing wrong unnecessarily creating leading zeroes, , (2) if unavoidable side effect of m produces leading zeroes, how can adjust or use improved algorithm avoid leading zeroes.

// knuth m algorithm 4.3.1 final public static void multiplydecimals( int[] decimalm1, int[] decimaln1, int[] result, int radix ){     arrays.fill( result, 0 );     int lenm = decimalm1[0];     int lenn = decimaln1[0];     result[0] = lenm + lenn;      int istepm = lenm;     while( istepm > 0 ){         int istepn = lenn;         int icarry = 0;         while( istepn > 0 ){             int ipartial = decimalm1[istepm] * decimaln1[istepn] + result[istepm + istepn] + icarry;             result[istepm + istepn] = ipartial % radix;             icarry = ipartial / radix;             istepn--;         }         result[istepm] = icarry;         istepm--;     }     return; } 

output of algorithm showing factorials being generated shows leading zeroes.

1 01 2 002 3 0006 4 00024 5 000120 6 0000720 7 00005040 8 000040320 9 0000362880 10 000003628800 11 00000039916800 12 0000000479001600 13 000000006227020800 14 00000000087178291200 15 0000000001307674368000 16 000000000020922789888000 17 00000000000355687428096000 18 0000000000006402373705728000 19 000000000000121645100408832000 20 00000000000002432902008176640000 

the algorithm isn't allocating leading zeros @ all. are. you're providing output array, , filling zeros too. knuth algorithm m doesn't that.

in addition:

1. you should skip leading zeros in both numbers. can have massive effect on performance, it's o(mn) algorithm. sum of final m , n correct number of output digits; final step after multiplication remove possibly 1 leading zero.

2. you can skip inner loop if current m digit zero. knuth's step m2. note 0 digit occurs more in numbers in nature 1/10: there's law says each digit 1,2,3,5,6,7,8,9 successively less likely.