Problem16

package com.shui.mu.yao.io.algorithm;
/**
 * 
 * @author shuimuqinghua77 @date 2012-12-02
 *
 */

public class Problem16 {
	public static void main(String[] args) throws Exception {

		
		byte[] seed=new byte[]{2};/**如果是{1,0,2,4}*/
		seed=getDigit(seed);/**那么转化后得到{4,2,0,1}便于乘法*/
		byte[] result=new byte[]{1};
		for(int i=0;i<1000;i++){
			result = multiply(seed, result);
		}
		int sum=0;
		for(int i=0;i<result.length;i++){
			sum+=result[i];
		}
		System.out.println(sum);
		
	}

	private static byte[] multiply(byte[] multiplicand/**被乘数**/, byte[] multiplier) throws Exception {
		if(multiplicand.length==0||multiplier.length==0)
		{
			throw new Exception("被乘数/乘数为空！！！");
		}
		if(multiplicand.length<multiplier.length){
			byte[] temp=multiplier;
			multiplier=multiplicand;
			multiplicand=temp;
		}
		byte[] result=new byte[multiplicand.length+multiplier.length];
		for(int i=0;i<multiplier.length;i++){
			for(int j=0;j<multiplicand.length;j++){
				result[i+j]+=(byte) (multiplier[i] * multiplicand[j]);
			}
			/**[29]->[9][2]进位**/
			carry(result,1+multiplicand.length,i);
		}
		if(result[result.length-1]==0){
			byte[] resultDest=new byte[result.length-1];
			System.arraycopy(result, 0, resultDest, 0, result.length-1);
			return resultDest;
		}
		
		return result;
	}

	private static void carry(byte[] result,int length,int base) {
		for(int i=base;i<length+base;i++){
			byte decade=(byte) (result[i]/10);
			if(decade>=1){
				result[i+1]+=decade;
				result[i]=(byte) (result[i]%10);
			}
		}
		
	}

	private static byte[] getDigit(byte[] original) {
		byte[] render = new byte[original.length];
		for (int i = 0; i < original.length; i++) {
			render[original.length - 1 - i] = original[i];
		}
		return render;
	}

}