大数相乘——分治法（lua版）

首先，什么是大数相乘？大数相乘通过字面的意思也能知道，就是量很大的相乘。他的解法有很多种，想穷举，分治法等等。但是如果是通过穷举法来解决大数相乘，他的时间复杂度是n的平方。但是，如果使用分治法，它的时间复杂度就降低很多。

在这里，我们不讲怎么用穷举法来实现大数相乘。这个方法的原理很简单，就是利用的是乘法的规则来实现。

使用分治法来实现大数相乘他的原理，这个每一本算法书上都有，就不在这里写了。

这里直接上实现代码。

编译环境 win7+sublime+Lua

function mult(tx,ty,n)
	-- body
	print("n=",n)
	if n==1 then
		--todo
		return tx[1]*ty[1]
	else
		--todo
		local a,b,c,d={},{},{}--
		local mid=math.floor(n/2)
		print("mid=",mid)
		--划分
		for i=1,mid do
			table.insert(a,tx[i])
			table.insert(c,ty[i])
		end
		for j=mid+1,n do
			table.insert(b,tx[j])
			table.insert(d,ty[j])
		end
		print("=======a=======")
		for i,v in ipairs(a) do
			print(i,v)
		end

		print("=======b=======")
		for i,v in ipairs(b) do
			print(i,v)
		end
		print("=======c=======")
		for i,v in ipairs(c) do
			print(i,v)
		end
		print("=======d=======")
		for i,v in ipairs(d) do
			print(i,v)
		end
		print("===============")
		local temp1,temp2={},{}
		
		local len=table.maxn(b)
		--print("len",len)
		for k=1,len do
			table.insert(temp1,a[k]-b[k])
			table.insert(temp2,d[k]-c[k])
		end
		print("=======temp1=======")
		for i,v in ipairs(temp1) do
			print(i,v)
		end
		print("=======temp2=======")
		for i,v in ipairs(temp2) do
			print(i,v)
		end
		print("==================")
		local m1=mult(a,mid)
		print("m1=",m1)
		local m2=mult(temp1,temp2,mid)
		print("m2=",m2)
		local m3=mult(b,d,mid)
		print("m3=",m3)
		s=1
		local exp1,exp2=math.pow(10,n),math.pow(10,math.floor(n/2))
		print("exp1",exp1,"exp2",exp2)
		--s=s*(m1*math.pow(10,n)+(m1+m2+m3)*math.pow(10,math.floor(n/2))+m3)
		print("结果1：",m1*exp1)
		print("结果2：",(m1+m2+m3)*exp2)
		print("结果3：",m3)
		s=s*(m1*exp1+(m1+m2+m3)*exp2+m3)
		print("s=",s)
		return s
	end
end
function MainScene:ctor()
	x={1,2,3,4,5,6,7,8}
	y={8,1}
	n=table.maxn(x)
	m=mult(x,y,n)
	print(m)
end

1.这个代码是用Lua实现的，不会Lua的，还是先学学Lua吧，挺简单的。

2.主要体现分治法的思想和一个实现的过程，这个算法的细节还是有点不完善的。例如，最后返回的其实应该是一个table更好点，还有就是在返回m1这些值得时候，也应该函数的是table等等，这些都还没有实现。

3.在使用Lua编写的时候，一定要注意变量的作用域，少使用全局变量。

4.这是Lua版，后面我们还有结合着个算法来讲解C++函数中的数组做参数，STL容器做函数参数，函数返回值问题，都是结合这个算法来讲解的。