web analytics

睡前一小时数学系列之从零开始的快速乘法。

睡前一小时数学系列之从零开始的快速乘法。

当我们遇到大数相乘的时候情不自禁可以想到高精度。但是如果遇到 形如 a*b%c 的运算的时候。数也就是long long级别(2^61-1)但是没有办法的是这样数如果相乘会超long long级,再一模,hhhh肯定会炸。所以既然要提高乘法的效率而且保证精度。采用快速乘法。主要思想就是对数进行二进制拆分,运用乘法分配律把拆分结果加起来,嗯就好了。

举个栗子 23*123   123的二进制是(1111011)2 那么我们就可将这个结果拆成 23*2^0 +  23*2^1 +  23*2^3 + 23*2^4 + 23*2^5  + 23*2^6 。分开计算。每次将123右移一位还将23左移一位(同*2)。判断它二进制 第 t 位是不是1,能不能将23加入答案。

全程都可以用位运算来优化,这样速度又提升了一个次元。发一段快速乘法的程序。

观察这段代码可以发现,这里的取模运算是直接相减。这段代码已经交代的很完全了。

附加内容:

快速幂:

这个内容其实跟乘法很像 。因为这里乘法是对乘数进行拆分,而快速幂就是对幂进行拆分。

举个栗子: 23^123  123的二进制是(1111011)2 那么我们就可以将这个结果拆成23^2^0 +  23^2^1 +  23^2^3 + 23^2^4 + 23^2^5  + 23^2^6 . 那么我们每次就不是将23左移一位了。直接就进行乘方运算。而这里的乘方,也可以用到上面的快速乘法#手动滑稽。。这个又要比乘法又快了一步。

继续发一段这个的程序:

这两个东西的道理其实都很一样。但是这个原理在处理一些丧心病狂的数据的时候就是很快,可以拿(骗)到更多的分。

Post a Comment

You must be logged in to post a comment.