当前位置:首页 > C++知识 > 正文内容

【数论】快速乘

亿万年的星光2年前 (2023-02-04)C++知识18567

上一篇文章简单说了龟速乘的问题,有人觉得龟速乘还是太慢了,有没有什么办法再快一点,实际是有的,就是我们今天介绍的 快速乘

快速乘的原理和龟速乘不同,快速乘并不是基于二进制和位运算,严格来说,快速乘是利用了一个bug才实现的功能。

这个bug 就是 long double 和long long 的定义范围不同。因为long double的范围比long long 大一些。

它来源于下面这篇文章:

什么意思呢?

简单来说,就是就是在原地爆炸的边缘疯狂试探,把本来存进long long会炸掉的值先进行计算,用long double暂时存下,然后再把差值——一个不会超过long long的数字塞回去,再特判一下精度问题,就大功告成了。

int QuickMult(long long a,long long b,long long mod) {
	long long d=(long double)a/mod*b;
	long long ans=(unsigned long long)a*b-(unsigned long long)d*p;
	return (ans+mod)%mod;
}

但是它就是可以算出正确答案来。因为它其实很巧妙的运用了自动溢出这个操作,我们的代码中的z就表示 所以我们要求的就变成了 ,虽然这两个部分都是会溢出的,但(unsigned)保证了它们溢出后的差值基本不变,所以即使它会溢出也不会影响最终结果的!


优点与缺点:

优点就是代码简短高效,缺点就是容易丢失精度。

扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:
返回列表

上一篇:【数论】龟速乘

下一篇:unsigned

相关文章

最小生成树(1)

最小生成树(1)

一、定义一个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的最少的边。最小生成树可以用kruskal(克鲁斯卡尔)算法或prim(普里姆)算法求出...

编写第一个C++程序

编写第一个C++程序

前面的文章介绍了Dev-C++的下载安装:【入门篇】>>> DEVC++下载、安装、简单使用 - 青少年编程知识记录 (codecoming.com)今天讲一下如何使用Dev-C++...

NOIP2013年普及组初赛题目及答案分析

NOIP2013年普及组初赛题目及答案分析

一、单项选择题1. 一个 32 位整型变量占用( A )个字节。 A. 4    B. 8      C. 32     &nbs...

常见的数据范围

一、总结名称字节位数(二进制)最小值最大值位数(十进制)bool18011char18shrot 216    (-2^15  到2^15  -1)-...

【题解】采药的最短路径

【题目描述】少年李逍遥的婶婶病了,王小虎介绍他去一趟仙灵岛,向仙女姐姐要仙丹救婶婶。孝顺的李逍遥闯进了仙灵岛,克服了千险万难来到岛的中心,发现仙药摆在了迷阵的深处。迷阵由M×N个方格组成,有的方格内有...

C++中双冒号(::)的用法

一、作用域符号前面一般是类名称,后面一般是该类的成员名称,C++为例避免不同的类有名称相同的成员而采用作用域的方式进行区分如:A,B表示两个类,在A,B中都有成员member。那么A::member就...