Go教程

Segment 4:Introduction Number Theory——Arithmetic algorithms【算术算法】:

本文主要是介绍Segment 4:Introduction Number Theory——Arithmetic algorithms【算术算法】:,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

Segment 4:Introduction Number Theory——Arithmetic algorithms【算术算法】:链接

这是整个数论简介的内容,下面是这个的主目录如下,其链接为:https://blog.csdn.net/qq_43479839/article/details/119079620
在这里插入图片描述

Segment 4目录@xyi

  • Segment 4:Introduction Number Theory——Arithmetic algorithms【算术算法】:链接
    • 4.1 第一个问题:如何在计算机里表示大整数【Representing bignums】?
      • 1、看算术【Arithmetic】操作会花多少时间
      • 2、求幂的问题【Exponentiation】
      • 3、The repeated squaring alg.【重复平方算法】
      • 4、小结一下在ZN中n位加法减法,乘法,指数运算运行时间

这节我们会讨论质数模与合数模的加法、乘法个指数算法【addtion and multiplication and exponentiation alorithms, modulo primes and composites】

4.1 第一个问题:如何在计算机里表示大整数【Representing bignums】?

在这里插入图片描述
假设我们有一台64位的计算机,想在这64位的机器上表示一个n位大整数(如 n=2048);
1> 我们把想表示的大数进行分割,32位一组,然后我们就有n/32个分组,它们可以表示这个数,我们想把它存储在计算机上,【一般情况下你会使用长于32位的分组】,在这里使用32位,是因为想限制到32位,因为这样你可以把来个分组乘在一起而结果小于64位,
在这里插入图片描述

1、看算术【Arithmetic】操作会花多少时间

在这里插入图片描述
1、 Addition和Subtraction【加法和减法】:O(n);注意加法有进位,减法有借位;
2、 Multipication:O(n^2);不过Karatsuba发现其实乘法的运时间是O(n1.585);大致的想法如下,不过最好的算法时间可以降至位nlognD
在这里插入图片描述
3、 Division with remainder【带余除法】

2、求幂的问题【Exponentiation】

在这里插入图片描述
1> 假设我们有一个有限循环群【the finite cyclic group】,这意味着这个群是由生成元g的各个幂生成的;该群的阶数的幂记作为g^q;我们的目标是,给定这个生成元g以及某个指数x;我们的目标是计算gx;【一般x是一个很巨大的数,所以一个一个去乘显然不成熟】
2> 当x很大的时候,我们是否也能很快的计算出gx;显然是可以的;有一个算法叫做:重复平方算法【a repeated squaring algorithm】;算法的大概步骤如下:
在这里插入图片描述
g53通过5次平方,再加上4次乘法;所以通过9步乘法,就算出了它;

3、The repeated squaring alg.【重复平方算法】

在这里插入图片描述
1> 这个算法需要说明一下的是:我们需要俩个寄存器,y叫做平方运算的寄存器;z叫做累加寄存器
2> 其中这个算法循环的次数是log2X;【取决于x的位数】;但是时间复杂度如下:

4、小结一下在ZN中n位加法减法,乘法,指数运算运行时间

在这里插入图片描述
在这个里面只要提一个地方:就是对于指数,需要logX次循环,我们说过乘法的时间是n的平方,因为这个算法里面有俩个乘法,所以运行时间将会是n2logx【指数运算其实很慢】

这篇关于Segment 4:Introduction Number Theory——Arithmetic algorithms【算术算法】:的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!