sponsored links

Strassen算法专题

施特拉森算法

October 29
施特拉森算法
Strassen算法是个计算矩阵乘法的算法。 设A, B为域 F上的方矩阵。求两者的积C。 (一般矩阵可以填0的方法计算令它成为矩阵。) 将A, B, C分成相等大小的方块矩阵: 即 于是 引入新矩阵 可得: 其中M_{i,j}的计算也是使用Strassen算法求得。 评论 一般矩阵乘法的时间复杂度为,Strassen算法则是。但Str ...

矩阵乘法

September 19
矩阵乘法
... 上述三个分开的表示式只有在纯量体的乘法及加法是可交换(即纯量体为一可交换环)时会相同。 另见 Strassen算法(1969) Winograd算法(1980) Coppersmith–Winograd算法(1990) 逻辑矩阵 矩阵链乘积 逆矩阵 关系复合 BLAS 矩阵加法

Karatsuba算法

October 29
Karatsuba算法
... Karatsuba算法需要3 = 59,049次个位数乘法,而经典算法需要(2) = 1,048,576次。Toom–Cook算法是此算法更快速的泛型。对于充分大的n(n >> 1),Schönhage–Strassen algorithm算法甚至更快,算法的时间复杂度为 值得一提的是,Kar ...

平方根倒数速算法

September 12
平方根倒数速算法
... )是用于快速计算(即的平方根的倒数,在此需取符合IEEE 754标准格式的32位浮点数)的一种算法。此算法最早可能是于90年代前期由SGI所发明,后来则于1999年在《雷神之锤III竞技场》的源代码中应用,但 ... 形式被2所除。 “魔术数字” S(ign,符号) E(xponent,指数) M(antissa,尾数) 1 位 b位 (n-1-b)位 n位 对 ...

算法

September 12
算法
... 表示 int max(int *array, int size) { int mval = *array; int i; for (i = 1; i < size; i++) if (array[i] > mval) mval = array[i]; return mval; } 求最大公约数算法 求两个自然数的最大公约数 设两个变量M和N 如果M < N,则交换M和N M被 ...

算法

September 12
算法,是以不同的方法或简单的方法以较快的速度计算数学题,目的是快速而精确地计算出答案。速算法有很多种,当中比较知名的是珠心算和史丰收速算法。不同的速算法有不同的特点、计算方式和计算速度亦有所不同。

布斯乘法算法

September 12
布斯乘法算法
... 。一般地,和乘数一样,可以采用2的补码方式表达。也可以采用其他计数形式,只要支持加减法就行。这个算法从乘数的最低位执行到最高位,从 i = 0 开始,接下来和 2i 的乘法被累加器 P 的算术右移所取代。较低位 ... 的每一位都判断过后为结束 最后是结果,结果就是R0并上R1的值。比如R0=3,R1=25,结果就是325. 算法原理 考虑一个由若干个 0 包围 ...

杨辉算法

September 13
杨辉算法
... 纲目》,杨辉为学员制定的学习纲目和时间表,例如 “学相乘起例定位 功课一日”,“温习九归题目 一日”;“开方乃算法中大节目”,用两月演习题目等。 商用乘除算题;此卷详细叙述六种乘法和五种速算加法。 六种速 ... 减一位 减二位 重减 隔为减 卷中《乘除通变算宝》 叙述乘除通变算宝,和筹算速算法,包括加法乘、九归新括。 卷下《法算取用本末》 是前两卷所述各种方 ...

盘珠算法

September 13
盘珠算法
徐心鲁《盘珠算法》 《盘珠算法》,又名《新刊订正家传秘诀盘珠算士民利用》,是明代数学家徐心鲁在万历元年(1573年)刊行于福建的珠算普及著作。《盘珠算法》二卷,附有有大量插图,图中所示的明式算盘是上一珠,下五珠,可见“日式算盘”在明朝万历初年已经在福建流行了。 《盘珠算法》卷一讲珠算加、减、乘、除的运算及口诀和习题,先从最基本的“第一上法”开 ...

算法设计

September 14
... 计算方法的较浅近的版本。 基础概念 工程计算中误差的概念 误差的来源 模型误差 观测误差 截断误差 舍入误差(计算误差) 绝对误差 相对误差 有效数字 误差的传播 选用算法的若干问题 选用标准 优劣的比较 方程的单根近似解法 对分法 迭代法 牛顿法(切线法) 线性方程组的精确解法 高斯消去法 主元素消去法 三角分解法 线性方程组的迭代 ...

辐射度算法

September 14
辐射度算法
... )中引入的。 该理论在工程中早有应用,用以解决辐射热传导中的问题,始于约1950年。 突出的商用辐射度算法引擎包括Lightscape (现已集成到Autodesk 3D Studio Max的内部绘制引擎中),和更新的Next Limit的Maxwell~Renderer(麦克斯韦绘制器)。 视觉特点 辐射度算法的例子 辐射度在绘制过程中的引入经常对最后的场景 ...

算法状态机

September 14
算法状态机
... 的本质差异带来的:硬件数字电路的状态转移是根据定时器讯号来实现同步的,即每过一个时钟周期“步进”一个状态,因此算法状态机的状态转移隐含着时序的信息,相邻状态的转移所跨越的时间往往精确单个时间脉冲,而软件程序设计则一般不 ... 外形为一个菱形块,这个方块会标注上即将被测试的表达式,然后对应不同的测试结果,给出不同的处理路径。算法状态机的状态决定盒一般具有一个输入 ...

字串搜寻算法

September 15
... String searching algorithms,又译字符串搜索算法)又称字串比对算法(string matching algorithms)是一种搜索算法,是字串算法中的一类,用以试图在一长字符串或文章中,找出其是否包含某一个或多个字符串,以及其位置。 ... == nlen - 1) found = 1; }; }; return found; 上 ...

九章详注比类算法大全

September 15
九章详注比类算法大全
... 》,积功十年,才克脱稿 。 吴敬的时代是筹算和珠算并用的时代,《九章详注比类算法大全》的演算草图都用筹式算符,但有些题目的运算,必须依靠算盘来完成,因此有些学者认为此书是筹算 ... “部分题目,取自刘徽《海岛算经》、王孝通《缉古算经》、杨辉《详解九章算法》,朱世杰《四元玉鉴》等古算术;”比类“是应用题 。 版本 根据中算史家李俨考证,《九章详注比 ...

Paxos算法

September 23
... 违背了一致性的要求。一致性要求对应于法律条文只能有一个版本。议员和服务员的不确定性对应于节点和消息传递通道的不可靠性。 算法 算法的提出与证明 首先将议员的角色分为 proposers,acceptors,和 learners(允许身兼数职)。proposers 提出提案,提案信息 ... 。 另外还需要保证 progress。这一点以后再讨论。 作者通过不断加 ...

序列最小优化算法

September 25
序列最小优化算法
... 于1998年,目前被广泛使用于SVM的训练过程中,并在通行的SVM库libsvm中得到实现。 1998年,SMO算法发表在SVM研究领域内引起了轰动,因为先前可用的SVM训练方法必须使用复杂的方法,并需要昂贵的第三方二次规划工具。 ... 再根据SVM的定义计算出偏移量。对于误差项而言,可以根据、和的增量进行调整,而无需每次重新计算。具体的算法如下: 1 随机数 ...

Tomasulo算法

September 26
... 排列指令实际执行的顺序(乱序执行),提高时间利用效率。IBM System/360 Model 91处理器的浮点运算器中率先使用了这种算法。 该算法与之前同样用于实现指令流水线动态调度的计分板不同在于它使用了寄存器重命名机制。指令之间具有数据相关性(例如后条 ... 为真数据相关(true data dependence),而后两种冒险则并没有那么致命,它们可以 ...

Misra & Gries边着色算法

September 26
Misra & Gries边着色算法
... ,但从未被发表。 总体上来说,最优边着色问题是NP完全的,所以很可能并不存在多项式时间内的算法。同时也有指数级的算法给出了该问题的最优解。 扇 顶点v的一个扇 F=[x_1,x_2,x_3](虚线边代表未着色), ... c 或 d 中的一种颜色,而对于边上的其他节点,翻转操作只是交换了边的颜色,并未增加新颜色。 算法 输入: 图 G. 输出: ...

算法信息论

September 26
算法信息论(Algorithmic information theory)是使用理论计算机科学的工具,研究复杂性概念的学科领域。它是信息理论的一环,关注计算与信息之间的关系。按照Gregory Chaitin的说法,它是“把香农的信息论和图灵的可计算论放在调酒杯使劲摇晃的结果。”

排序算法

September 26
排序算法
... 空间 不稳定的排序 选择排序(selection sort)—O(n) 希尔排序(shell sort)—O(n log n)如果使用最佳的现在版本 Clover排序算法(Clover sort)—O(n)期望时间,O(n2/2)最坏情况 梳排序— O(n log n) 堆排序(heap sort)—O(n log ... (bead sort)— O(n) or O(√n) ...